Invert Binary Tree - Solution & Explanation

Problem Overview: You’re given the root of a binary tree. The task is to invert the tree by swapping the left and right child of every node. After inversion, nodes that were originally on the left move to the right and vice versa across the entire tree.

Approach 1: Recursive Depth-First Search (O(n) time, O(h) space)

This approach uses recursion with Depth-First Search. For each node, swap its left and right pointers, then recursively process both children. The key insight is that inversion is a local operation—once a node’s children are swapped, the same rule applies independently to its subtrees. Each node is visited exactly once, giving O(n) time complexity where n is the number of nodes. The recursion stack uses O(h) space, where h is the tree height. For balanced trees this is O(log n), but in the worst case (skewed tree) it becomes O(n). This method is concise and maps directly to the recursive structure of a Binary Tree.

The algorithm is straightforward: if the current node is null, return immediately. Otherwise swap its children, then recursively call the same function on the new left and right children. Because the swap happens before recursion, every subtree ends up inverted correctly. This is the most common implementation you’ll see in interviews and editorials.

Approach 2: Iterative BFS Using a Queue (O(n) time, O(w) space)

This version performs a level-order traversal using Breadth-First Search. Start by pushing the root node into a queue. While the queue is not empty, pop the front node, swap its left and right children, and then enqueue the children if they exist. The queue ensures nodes are processed level by level.

Each node is dequeued exactly once and swapped once, so the total runtime is O(n). Space complexity depends on the maximum width of the tree. In the worst case, the queue holds up to O(w) nodes, where w is the maximum number of nodes in any level (up to O(n) for a complete tree).

The BFS approach avoids recursion and stack depth concerns. It’s a good choice when working in environments where recursion depth might cause stack overflow or when you want an explicit iterative traversal.

Recommended for interviews: The recursive DFS solution is typically expected because it directly reflects the structure of the tree and requires minimal code. Interviewers often accept the BFS queue solution as well, especially if you explain the traversal tradeoffs. Showing both approaches demonstrates strong understanding of tree traversal patterns.