Leetcode considers this question to be easy, but it was a bit more complicated than that at first for me. Let’s try solving it three different ways:

Whenever I can, I always try to do BFS. It seems much more natural.

BFS - 1st solution

func isSymmetricBFS(_ root: TreeNode?) -> Bool {
    var queue: [TreeNode?] = []

    queue.append(root)

    while !queue.isEmpty {
        let temp = queue
        queue.removeAll()
        
        // 🔑 to make sure you don't expand on `nil` nodes — otherwise it would be endless
        for node in temp where node != nil {
            queue.append(node?.left)
            queue.append(node?.right)
        }

        if isSymmetric(temp) == false { 
            return false 
        }
    }

    return true
}

BFS feels very natural because you traverse layer by layer. Here we have the logic broken down nicely:

  • Add a layer into the queue.
  • Then just check if each layer is palindrome.

DFS

func isSymmetricDFS(_ root: TreeNode?) -> Bool {
    return isSymmetric(root?.left, root?.right)
}

func isSymmetric(_ rootA: TreeNode?, rootB: TreeNode?) -> Bool {
    // - IDEA
    // All "subtrees" must be matching symmteric

    // STEPS
    
    // 1. PROCESS CURRENT STRATE
    // Current state is maded up from TWO subtrees. 

    // 1.1 process base case: exit
    if rootA?.val == nil && rootB?.val == nil { 
        return true
    }

    // 1.2 process another base case: exit
    if rootA?.val != rootB?.val { 
        return false 
    }

    // 2. RECURSE
    // Each Level doubles the number of comparisons.
    return isSymmetric(rootA?.left, rootB?.right) && isSymmetric(rootA?.right, rootB?.left)
}

A more sophisticated BFS approach:

BFS - 2nd solution

func isSymmetric(_ root: TreeNode?) -> Bool {
    guard let root = root else { return true }

    var queue: [(TreeNode?, TreeNode?)] = [(root.left, root.right)]

    while !queue.isEmpty {

        let (left, right) = queue.removeFirst()

        // 1. PROCESS CURRENT STATE

        // early exits 
        guard left?.val == right?.val else { return false }
        
        // not a base case, but a stop on traversal <-- this bit of a unique question since the algorithm adds in pairs — which restricts you from _not_ adding nil nodes. Hence the extra check. Typically you don't add nil nodes and don't have to do this check. 

        if left?.val == nil { continue } // could have just checked against the right node. Doesn't matter since the previous line checks if thye're identical. 

        // 2. RECURSE

        // every two nodes you compare, will have a max of 4 children. you must add them _symmterically_ into your queue. Then compare them 
        queue.append((left?.left, right?.right))
        queue.append((left?.right, right?.left))
    }

    return true 
}