Skip to content

076 — Invert Binary Tree

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

76 — Invert Binary Tree

LeetCode 226 · Easy. Given the root of a binary tree, invert the tree, and return its root.

🍽️ Intuition

Hold the tree up to a mirror. Every node's left child becomes its right child, and every node's right child becomes its left child — not just at the root, but at every single node, all the way down. A family tree where every person's "oldest child" and "youngest child" seats got swapped, recursively, for every person in the family. Swap the two seats at the root, then walk down and do the exact same swap at every descendant.

🚩 Pattern-Recognition Cue

"Invert" / "mirror" a tree is a direct cue for recursive DFS: solve it for the left subtree, solve it for the right subtree, and combine by swapping the two results at the current node. There's no searching or comparing values involved — just a structural rewiring of left/right pointers, applied node by node.

🐢 Brute Force

Walk the tree once with a queue (BFS) to collect every node into a flat array — extra O(n) storage — then make a second pass over that array swapping each node's left and right children.

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { self.val = val }
}

func invertTreeBruteForce(_ root: TreeNode?) -> TreeNode? {
    guard let root = root else { return nil }

    var allNodes: [TreeNode] = []
    var queue: [TreeNode] = [root]
    while !queue.isEmpty {
        let node = queue.removeFirst()
        allNodes.append(node)
        if let left = node.left { queue.append(left) }
        if let right = node.right { queue.append(right) }
    }

    for node in allNodes {
        let temp = node.left
        node.left = node.right
        node.right = temp
    }

    return root
}

// smoke test:      4                  4
//               /     \            /     \
//              2       7    ->    7       2
//             / \     / \        / \     / \
//            1   3   6   9      9   6   3   1
let bfRoot = TreeNode(4)
bfRoot.left = TreeNode(2); bfRoot.right = TreeNode(7)
bfRoot.left?.left = TreeNode(1); bfRoot.left?.right = TreeNode(3)
bfRoot.right?.left = TreeNode(6); bfRoot.right?.right = TreeNode(9)
let bfInverted = invertTreeBruteForce(bfRoot)
print(bfInverted?.left?.val ?? -1, bfInverted?.right?.val ?? -1)   // 7 2

Big-O: O(n) time — every node is visited once to collect, once to swap. O(n) extra space for the queue and the flat array holding every node reference at once.

🚀 Optimal

Swap a node's two children, then recurse into both — no separate storage needed, the call stack does the bookkeeping.

func invertTree(_ root: TreeNode?) -> TreeNode? {
    guard let root = root else { return nil }

    let temp = root.left
    root.left = root.right
    root.right = temp

    invertTree(root.left)
    invertTree(root.right)

    return root
}

// smoke test: same tree as above
let root = TreeNode(4)
root.left = TreeNode(2); root.right = TreeNode(7)
root.left?.left = TreeNode(1); root.left?.right = TreeNode(3)
root.right?.left = TreeNode(6); root.right?.right = TreeNode(9)
let inverted = invertTree(root)
print(inverted?.left?.val ?? -1, inverted?.left?.left?.val ?? -1, inverted?.left?.right?.val ?? -1)   // 7 9 6
print(inverted?.right?.val ?? -1, inverted?.right?.left?.val ?? -1, inverted?.right?.right?.val ?? -1) // 2 3 1

print(invertTree(nil) == nil)   // true — empty tree stays nil

Big-O: O(n) time — each node's children are swapped exactly once. O(h) extra space for the recursion call stack, where h is the tree's height — O(log n) for a balanced tree, O(n) worst case for a completely skewed one.

🔑 The Key Insight

Both approaches touch every node exactly once — there's no asymptotic time gap here. The real saving is space: the brute force needs an explicit O(n) structure (the queue plus the flat array) to remember every node before it can start swapping, while the recursive version swaps a node's children before descending into them, so nothing needs to be remembered beyond "the node I'm currently on and the ancestors above it" — exactly what the call stack already tracks for free. That collapses O(n) bookkeeping down to O(h).

🔗 Related Chapters

  • Binary Trees — the underlying structure; this problem is pure left/right pointer rewiring.
  • DFS and Backtracking — the recursive shape here is the canonical "solve the left subtree, solve the right subtree, combine" pattern, just with "combine" meaning "swap."
  • Queues & Deques — the queue driving the brute force's level-by-level collection pass.

🧸 Memory Sentence

Invert Binary Tree is holding the tree up to a mirror — swap left and right at every node, and the reflection is the answer.

✅ Check Your Understanding

Trace the optimal algorithm on the tree 4 -> (2 -> (1, 3), 7 -> (6, 9)). Write out the tree's shape after each of the three recursive calls (root, then left subtree, then right subtree) completes its own swap, and explain why swapping a node's children before recursing into them (rather than after) still produces the correct final tree.

⬅️ Previous: Reverse Nodes in k-Group · Next: Maximum Depth of Binary Tree ➡️

Clone this wiki locally