Check symmetric binary tree

# Check symmetric binary tree

January 29, 2023

Name
Moch Lutfi
@kaptenupi

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

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

`type Tree struct { Value interface{} Left *Tree Right *Tree}`

### 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
`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)}`

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

### DFS

Deep First Search using stack

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

dfs.go
`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}`