Invert Binary Tree - Video Solutions

Problem Overview: You are given the root of a binary tree. The task is to invert the tree by swapping the left and right children of every node. After inversion, all left pointers become right pointers and vice versa across the entire structure.

Approach 1: Recursive DFS (O(n) time, O(h) space)

This approach uses recursion with Depth-First Search. Starting from the root, swap its left and right children, then recursively apply the same operation to both subtrees. The key insight is that every node can be processed independently once you reach it. Because each node is visited exactly once, the time complexity is O(n), where n is the number of nodes. The recursion stack uses O(h) space, where h is the tree height (worst case O(n) for a skewed tree, O(log n) for balanced trees). This approach is short, readable, and commonly expected in interviews.

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

This version processes the tree level by level using Breadth-First Search. Push the root into a queue. While the queue is not empty, pop the current node, swap its left and right pointers, then push the children back into the queue. Each node is visited once, so the runtime remains O(n). The queue can hold up to the maximum number of nodes at a level, which leads to O(w) auxiliary space where w is the maximum width of the tree.

Both strategies operate directly on the structure of a binary tree. The recursive DFS version focuses on subtree transformations, while the BFS version processes nodes in level order. Neither approach requires extra data structures beyond the recursion stack or queue.

Recommended for interviews: The recursive DFS solution is the most common answer. It demonstrates clear understanding of tree traversal and requires only a few lines of code. The BFS queue approach is equally valid and useful if you prefer iterative logic or want to avoid recursion depth limits. Showing both approaches signals strong mastery of tree traversal patterns.