arcbjorn

thoughtbook

Saturday, March 4, 2023

Symmetric tree

Leetcode 101 problem.

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Go

  • Time complexity: O(n)O(n) - n is a height of a tree
  • Auxiliary space: O(log(n))O(log(n)) - n is a number of recusrsive calls in the stack
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 
func isSymmetric(root *TreeNode) bool {
    return isEqual(root, root)
}

func isEqual(left *TreeNode, right *TreeNode) bool {
    if left == nil && right == nil {
        return true
    }

    if left == nil || right == nil {
        return false
    }

    isCurrentEqual := left.Val == right.Val

    isSymmetricLeft := isEqual(left.Left, right.Right)
    isAsymmetricRight := isEqual(left.Right, right.Left)

    return isCurrentEqual && isSymmetricLeft && isAsymmetricRight
}
Creative Commons Licence