Check symmetric binary tree

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.

• [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.

Binary trees are already defined with this struct:

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

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

Bread First Search using queue

• 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
}

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
}