# Check symmetric binary tree

📚 3 min read Tweet this post
Section titled Problem

## Problem

Determine whether binary tree is symmetric around its center, i.e. each side mirrors the other.

Example

• For

``````t = {
"value": 1,
"left": {
"value": 2,
"left": {
"value": 3,
"left": null,
"right": null
},
"right": {
"value": 4,
"left": null,
"right": null
}
},
"right": {
"value": 2,
"left": {
"value": 4,
"left": null,
"right": null
},
"right": {
"value": 3,
"left": null,
"right": null
}
}
}``````

the output should be `solution(t) = true`.

Here’s what the tree in this example looks like:

``````    1
/ \
2   2
/ \ / \
3  4 4  3``````

As you can see, it is symmetric.

• For

``````t = {
"value": 1,
"left": {
"value": 2,
"left": null,
"right": {
"value": 4,
"left": null,
"right": null
}
},
"right": {
"value": 2,
"left": null,
"right": {
"value": 4,
"left": null,
"right": null
}
}
}``````

the output should be `solution(t) = false`.

Here’s what the tree in this example looks like:

``````    1
/ \
2   2
\   \
4    4``````

As you can see, it is not symmetric.

Section titled Input/Output

## Input/Output

• [execution time limit] 4 seconds (go)

• [input] tree.integer t

A binary tree of integers.

Guaranteed constraints:
`0 ≤ tree size < 50000`,
`-1000 ≤ node value ≤ 1000`.

• [output] boolean

Return `true` if `t` is symmetric and `false` otherwise.

Section titled Solution

## Solution

Binary trees are already defined with this struct:

``````type Tree struct {
Value interface{}
Left *Tree
Right *Tree
}``````
Section titled Recursion

### Recursion

The `solution` function first checks if the root is `nil`. If it is, it returns `true`, because an empty tree is considered symmetric. If the root is not `nil`, it calls `isMirror` with the root’s left and right children.

The `isMirror` function compares two trees, `left` and `right`, and returns `true` if they are mirror images of each other, and `false` otherwise. If both trees are `nil`, the function returns `true`. If one of the trees is `nil` while the other is not, the function returns `false`, because they cannot be mirror images of each other. If both trees are not `nil` but have different values, the function returns `false`. Finally, if both trees are not `nil` and have the same value, the function returns the result of calling `isMirror` with their left and right children, and their right and left children, respectively. This recursive call will continue until either one of the trees is `nil` or the values of the nodes differ, at which point the function will return `false`, or until both trees have been fully traversed and their values are equal, at which point the function will return `true`.

``````func solution(root *Tree) bool {
if root == nil {
return true
}
return isMirror(root.Left, root.Right)
}

func isMirror(left, right *Tree) bool {
if left == nil && right == nil {
return true
}
if left == nil || right == nil || left.Value != right.Value {
return false
}
return isMirror(left.Left, right.Right) && isMirror(left.Right, right.Left)
}``````
Section titled BFS

### BFS

• Use a queue to traverse the tree level by level
• comparing the values of each node’s left and right children at each level to check if they mirror each other.
• If at any point the values of the left and right children do not match, the tree is not symmetric and the function can return false.
• If the end of the tree is reached and all pairs of left and right children have matching values, the tree is symmetric and the function can return true.
``````func solution(t *Tree) bool {
if t==nil{
return true
}

q:=[]*Tree{t.Left, t.Right}

for len(q)>0{
left, right:= q[0], q[1]
q=q[2:]

if left==nil && right==nil{
continue
}

if left == nil || right == nil || left.Value != right.Value{
return false
}

q = append(q, left.Left, right.Right, right.Left, left.Right)
}

return true
}``````
Section titled DFS

### DFS

Deep First Search using stack

Similar with BFS but using stack instead of queue to traverse the tree level by level.

``````func solution(t *Tree) bool {
if t == nil {
return true
}
stack := []*Tree{t.Left, t.Right}
for len(stack) > 0 {
left, right := stack[len(stack)-2], stack[len(stack)-1]
stack = stack[:len(stack)-2]
if left == nil && right == nil {
continue
}
if left == nil || right == nil || left.Value != right.Value {
return false
}
stack = append(stack, left.Left, right.Right, left.Right, right.Left)
}
return true
}``````
go data-structure tree