Leetcode #101: Symmetric Tree

Recursive solution: two tree are a mirror reflection of each other, if

1. Their roots have the same value
2. The right subtree is the mirror reflection of the left subtree

Time complexity: O(n), because we traverse the entire input tree once, where n is the number of nodes.

Space complexity: The number of recursive calls is bound by the height of the tree. In the worst case, the tree is linear and the height is in O(n)

func isSymmetric(_ root: TreeNode?) -> Bool {
    return isMirror(node1: root, node2: root)
}

func isMirror(node1: TreeNode?, node2: TreeNode?) -> Bool {
    if node1 == nil && node2 == nil {
        return true
    } else if node1 == nil || node2 == nil {
        return false
    } else {
        return node1!.val == node2!.val && 
               isMirror(node1: node1!.left, node2: node2!.right) &&
               isMirror(node1: node1!.right, node2: node2!.left)
    }
}

Iterative solution:

Time Complexity: O(n), because we traverse the entire input tree once, where n is the number of nodes.

Space Complexity: There is additional space required for the search queue. In the worst case, we have to insert O(n) nodes.

func isSymmetric(_ root: TreeNode?) -> Bool {
    var queue = [TreeNode?]()
    queue.append(root)
    queue.append(root)
    while !queue.isEmpty {
        let node1 = queue.remove(at: 0)
        let node2 = queue.remove(at: 0)
        if node1 == nil && node2 == nil {
            continue
        }
        if node1 == nil || node2 == nil {
            return false
        }
        if node1!.val != node2!.val {
            return false
        }
        queue.append(node1!.left)
        queue.append(node2!.right)
        queue.append(node1!.right)
        queue.append(node2!.left)
    }
    return true
}