Published on

# Check symmetric binary tree

Authors
• Name
Moch Lutfi
@kaptenupi

## Problem

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

Example

• For

`_29t = {_29 "value": 1,_29 "left": {_29 "value": 2,_29 "left": {_29 "value": 3,_29 "left": null,_29 "right": null_29 },_29 "right": {_29 "value": 4,_29 "left": null,_29 "right": null_29 }_29 },_29 "right": {_29 "value": 2,_29 "left": {_29 "value": 4,_29 "left": null,_29 "right": null_29 },_29 "right": {_29 "value": 3,_29 "left": null,_29 "right": null_29 }_29 }_29}`

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

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

`_5 1_5 / \_5 2 2_5 / \ / \_53 4 4 3`

As you can see, it is symmetric.

• For

`_21t = {_21 "value": 1,_21 "left": {_21 "value": 2,_21 "left": null,_21 "right": {_21 "value": 4,_21 "left": null,_21 "right": null_21 }_21 },_21 "right": {_21 "value": 2,_21 "left": null,_21 "right": {_21 "value": 4,_21 "left": null,_21 "right": null_21 }_21 }_21}`

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

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

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

As you can see, it is not symmetric.

## 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.

## Solution

Binary trees are already defined with this struct:

`_5type Tree struct {_5 Value interface{}_5 Left *Tree_5 Right *Tree_5}`

### 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`.

recursion.go
`_16func solution(root *Tree) bool {_16 if root == nil {_16 return true_16 }_16 return isMirror(root.Left, root.Right)_16}_16_16func isMirror(left, right *Tree) bool {_16 if left == nil && right == nil {_16 return true_16 }_16 if left == nil || right == nil || left.Value != right.Value {_16 return false_16 }_16 return isMirror(left.Left, right.Right) && isMirror(left.Right, right.Left)_16}`

### 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.
bfs.go
`_24func solution(t *Tree) bool {_24 if t==nil{_24 return true_24 }_24 _24 q:=[]*Tree{t.Left, t.Right}_24 _24 for len(q)>0{_24 left, right:= q, q_24 q=q[2:]_24 _24 if left==nil && right==nil{_24 continue_24 }_24 _24 if left == nil || right == nil || left.Value != right.Value{_24 return false_24 }_24 _24 q = append(q, left.Left, right.Right, right.Left, left.Right)_24 }_24 _24 return true_24}`

### DFS

Deep First Search using stack

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

dfs.go
`_18func solution(t *Tree) bool {_18 if t == nil {_18 return true_18 }_18 stack := []*Tree{t.Left, t.Right}_18 for len(stack) > 0 {_18 left, right := stack[len(stack)-2], stack[len(stack)-1]_18 stack = stack[:len(stack)-2]_18 if left == nil && right == nil {_18 continue_18 }_18 if left == nil || right == nil || left.Value != right.Value {_18 return false_18 }_18 stack = append(stack, left.Left, right.Right, left.Right, right.Left)_18 }_18 return true_18}`