Invert Binary Tree
Understanding the Problem
We need to mirror a binary tree around its vertical axis. Every node's left child becomes its right child, and vice versa. This swap happens at every node, not just the root.
Swapping only the root's children is not enough. Inversion is recursive: when the left and right subtrees of the root are swapped, the subtrees themselves must also be inverted internally. The node in the bottom-left corner of the original tree should end up in the bottom-right corner of the inverted tree.
The structure of the problem is recursive. To invert a tree rooted at some node, invert the left subtree, invert the right subtree, then swap the two. This maps directly to a recursive algorithm.
Key Constraints:
Number of nodes in [0, 100]-- Every node's children must be swapped, so any correct solution visits all n nodes. O(n) time is the target.-100 <= Node.val <= 100-- Node values do not affect the algorithm. The work rearranges structure, not values.0 nodesis valid -- The empty tree (null root) must be handled. Returning null covers it.
Approach 1: DFS Recursive
Intuition
Inverting a tree rooted at a node takes three steps: invert the left subtree, invert the right subtree, then swap the left and right children of the current node.
The base case is the null node. There is nothing to invert, so the function returns null.
This maps to a post-order DFS traversal: descend into the left subtree and invert it, descend into the right subtree and invert it, then swap the two children at the current node. By the time the swap runs at any node, both of its subtrees are already inverted.
The order of operations is flexible. Swapping first and then recursing (pre-order) works just as well as recursing first and then swapping (post-order). The swap at a node does not depend on whether the subtrees have been inverted yet, so any traversal that visits every node and swaps its children produces the correct result.
Algorithm
- If the root is null, return null.
- Recursively invert the left subtree.
- Recursively invert the right subtree.
- Swap the left and right children of the current node.
- Return the current node.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node in the tree exactly once, doing O(1) work (a swap) at each node.
- Space Complexity: O(h), where h is the tree height. The recursion stack goes as deep as the height. For a balanced tree, h = O(log n). For a skewed tree, h = O(n).
The recursive approach is optimal in time but relies on the implicit call stack. The next approach replaces that stack with an explicit queue and visits nodes iteratively.
Approach 2: BFS Iterative (Level-Order)
Intuition
An explicit queue can replace recursion and process the tree level by level. BFS visits every node, and at each node it swaps the left and right children.
The order of visits does not matter, because the inversion at any node is independent of any other node. Visiting top-down, bottom-up, left-to-right, or level-by-level all produce the same result as long as every node's children are swapped. BFS is one iterative way to guarantee every node is visited.
Algorithm
- If the root is null, return null.
- Create a queue and add the root to it.
- While the queue is not empty: dequeue a node, swap its left and right children, and enqueue any non-null children.
- Return the root.
Example Walkthrough
Code
- Time Complexity: O(n). Every node is enqueued and dequeued exactly once. The swap at each node is O(1).
- Space Complexity: O(n). In the worst case, the queue holds all nodes at the widest level. For a complete binary tree, the last level has roughly n/2 nodes.
The BFS queue can hold up to O(n) nodes for a wide tree. Swapping the queue for a stack keeps the traversal iterative while bounding the auxiliary space to the tree height.
Approach 3: DFS Iterative (Using Stack)
Intuition
Replacing the queue from the previous approach with a stack changes the traversal order from breadth-first to depth-first while keeping the per-node logic the same: pop a node, swap its children, push the non-null children. This is iterative, so it carries no risk of a deep recursion overflowing the call stack, and the stack holds at most one root-to-leaf path at a time.
The last-in-first-out order is what bounds the space. After a node is popped and its children are pushed, the next pop takes one of those children and descends further before the sibling is processed. The stack therefore tracks a single downward path plus the un-popped siblings along it, which is O(h) rather than the O(n) a queue can reach on a wide level.
Algorithm
- If the root is null, return null.
- Create a stack and push the root onto it.
- While the stack is not empty: pop a node, swap its left and right children, and push any non-null children onto the stack.
- Return the root.
Example Walkthrough
Code
- Time Complexity: O(n). Every node is pushed and popped exactly once. The swap at each node is O(1).
- Space Complexity: O(h), where h is the tree height. The stack holds at most one root-to-leaf path. For a balanced tree, this is O(log n). For a skewed tree, this is O(n).