Invert Binary Tree: Multiple Solutions and Complexity Analysis

Understanding Binary Tree Inversion

Inverting a binary tree—often called mirroring—transforms a tree so that every left child becomes a right child and vice versa, recursively through all levels. Visually, it's like holding a physical tree up to a mirror: the entire structure flips horizontally while preserving node values and the overall shape.

This operation gained internet fame when Google engineer Max Howell tweeted that an interviewer rejected him for failing to invert a binary tree on a whiteboard. Beyond interview lore, tree inversion underpins practical tasks like creating symmetric views in graphics engines, reversing hierarchical data representations, and transforming recursive data structures in functional programming.

Core Definition

Given a binary tree with root node r, an inverted version swaps the left and right subtrees for every node in the tree. Formally, for any node n:

invert(n):
    swap(n.left, n.right)
    invert(n.left)
    invert(n.right)

The operation is total—every node participates. Leaf nodes simply swap two null children, which is a no-op, acting as the natural base case for recursion.

Solution 1: Recursive Depth-First Search (DFS)

The recursive approach mirrors the mathematical definition directly. It's elegant, compact, and often the first solution developers reach for.

Algorithm Walkthrough

• Base case: If the current node is null, return immediately—nothing to invert.
• Recursive step: Swap the left and right child pointers of the current node.
• Recurse: Call the function on the new left child (originally right) and the new right child (originally left).
• Return: Finally, return the current node so calls can chain upward.

Python Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def invert_tree_recursive(root: TreeNode) -> TreeNode:
    """
    Invert a binary tree using recursive DFS.
    Returns the root of the inverted tree.
    """
    if root is None:
        return None
    
    # Swap left and right children
    root.left, root.right = root.right, root.left
    
    # Recurse on both new children
    invert_tree_recursive(root.left)
    invert_tree_recursive(root.right)
    
    return root

Alternative: Single-Return Recursion

Some developers prefer building the inverted structure in one expression. This version is popular in functional-style code:

def invert_tree_functional(root: TreeNode) -> TreeNode:
    if root is None:
        return None
    
    # Construct a new mirrored node
    return TreeNode(
        val=root.val,
        left=invert_tree_functional(root.right),
        right=invert_tree_functional(root.left)
    )

This creates new nodes rather than mutating the original tree, making it useful when immutability matters.

Solution 2: Iterative Stack-Based DFS

An iterative DFS using an explicit stack eliminates recursion overhead and avoids stack overflow on extremely deep trees (though such trees are rare in practice with balanced structures).

Algorithm Walkthrough

• Initialize a stack with the root node.
• While the stack is non-empty, pop a node.
• Swap its left and right children.
• Push non-null children onto the stack (order doesn't matter since we process each node independently).
• Continue until the stack empties.

Python Implementation

def invert_tree_iterative_stack(root: TreeNode) -> TreeNode:
    """
    Invert a binary tree using an explicit stack (iterative DFS).
    """
    if root is None:
        return None
    
    stack = [root]
    
    while stack:
        node = stack.pop()
        
        # Swap children
        node.left, node.right = node.right, node.left
        
        # Push non-null children for further processing
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    
    return root

This approach visits nodes in a depth-first order driven by LIFO stack semantics. The maximum stack size equals the maximum depth of the tree, which is O(h) where h is the height.

Solution 3: Iterative Breadth-First Search (BFS) Using a Queue

BFS processes nodes level by level, which can be more intuitive when you want to visualize the transformation happening top-down.

Algorithm Walkthrough

• Initialize a queue (FIFO) with the root node.
• Dequeue a node, swap its children.
• Enqueue non-null children.
• Repeat until the queue is empty.

Python Implementation

from collections import deque

def invert_tree_bfs(root: TreeNode) -> TreeNode:
    """
    Invert a binary tree using BFS (level-order traversal).
    """
    if root is None:
        return None
    
    queue = deque([root])
    
    while queue:
        node = queue.popleft()  # FIFO: remove from front
        
        # Swap children
        node.left, node.right = node.right, node.left
        
        # Enqueue non-null children for level-by-level processing
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return root

BFS processes nodes in level order, which can make debugging easier because the tree's levels invert in a visually sequential manner.

Complexity Analysis Across All Solutions

Time Complexity

All three solutions run in O(n) time, where n is the number of nodes in the tree. Each node is visited exactly once, and the work performed per node—a pointer swap—is constant-time O(1). There is no way to beat O(n) because every node must have its children reversed.

Space Complexity

Space usage differs meaningfully between approaches:

• Recursive DFS: O(h) space on the call stack, where h is the tree height. In the worst case of a completely skewed tree (essentially a linked list), h = n, giving O(n) space. For a balanced tree, h = log₂(n), yielding O(log n) space.
• Iterative Stack DFS: Also O(h) space, determined by the maximum depth of nodes simultaneously on the stack. Same worst-case O(n) for skewed trees, O(log n) for balanced trees.
• Iterative Queue BFS: O(w) space, where w is the maximum width of the tree. In a balanced tree, the widest level contains roughly n/2 nodes, giving O(n) space. For a skewed tree, the width is always 1, giving O(1) space.

This creates an interesting tradeoff: BFS uses more space on wide, balanced trees but excels on narrow, deep trees. Recursive and stack-based DFS perform well on balanced trees but risk stack overflow on degenerate trees.

Summary Table

| Approach            | Time  | Space (Balanced) | Space (Skewed) | Risk Factor        |
|---------------------|-------|------------------|----------------|--------------------|
| Recursive DFS       | O(n)  | O(log n)         | O(n)           | Stack overflow     |
| Iterative Stack DFS | O(n)  | O(log n)         | O(n)           | None (heap memory) |
| Iterative Queue BFS | O(n)  | O(n)             | O(1)           | None (heap memory) |

Edge Cases and Robustness

• Empty tree (root is null): All three solutions handle this gracefully with an early null check, returning null immediately.
• Single-node tree: The swap operation exchanges two null children, effectively a no-op. The tree remains unchanged.
• Skewed tree (all nodes lean left or right): The inversion flips the direction of the skew. Recursive and stack solutions use O(n) space; BFS uses O(1) space.
• Very large trees: Iterative approaches avoid call-stack limits. Python's default recursion limit is ~1000 frames, so trees deeper than that will crash the recursive solution unless sys.setrecursionlimit is adjusted.
• Mutability requirements: The first recursive version and both iterative versions mutate the original tree in-place. The functional recursive version builds a new tree, preserving the original.

Visual Testing Helper

To verify correctness, use a level-order printer that shows the tree before and after inversion. Here's a utility function that returns a list of lists representing each level:

def level_order_traversal(root: TreeNode) -> list:
    """
    Returns a list of lists, where each inner list contains
    node values for one level of the tree.
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val if node else None)
            if node:
                queue.append(node.left)
                queue.append(node.right)
        
        result.append(current_level)
    
    return result

# Example usage
root = TreeNode(4,
    TreeNode(2, TreeNode(1), TreeNode(3)),
    TreeNode(7, TreeNode(6), TreeNode(9))
)
print("Original:", level_order_traversal(root))
# Output: [[4], [2, 7], [1, 3, 6, 9]]

inverted = invert_tree_recursive(root)
print("Inverted:", level_order_traversal(inverted))
# Output: [[4], [7, 2], [9, 6, 3, 1]]

This printer helps confirm that every level's order has been reversed correctly.

Language Variants

JavaScript (Recursive)

function invertTree(root) {
    if (root === null) {
        return null;
    }
    
    // Destructuring swap
    [root.left, root.right] = [root.right, root.left];
    
    invertTree(root.left);
    invertTree(root.right);
    
    return root;
}

Java (Iterative Stack)

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        
        // Swap children
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    
    return root;
}

Best Practices and Recommendations

• Prefer the recursive solution for interviews when tree depth is reasonable. It's concise, communicates intent clearly, and demonstrates comfort with recursion.
• Switch to iterative stack DFS in production when tree depth is unknown or potentially large. It retains O(h) space efficiency on balanced trees without risking stack overflow.
• Use BFS only when level-order processing is explicitly required or when you're dealing with extremely skewed trees where BFS gives O(1) space.
• Always handle the null root case at the top of your function. It's a one-line guard that prevents crashes and demonstrates attention to edge cases.
• Consider immutability needs: If the original tree must be preserved, use the functional approach that builds new nodes. If memory is tight, mutate in-place.
• Test with a variety of tree shapes: balanced, skewed, empty, single-node, and trees with only left or only right children.

Conclusion

Inverting a binary tree is a deceptively simple operation that reveals deep understanding of tree traversal strategies. The recursive DFS solution remains the canonical answer—elegant, compact, and intuitive. Iterative stack and queue variants offer practical alternatives when call-stack limits or specific traversal orders matter. All solutions converge on O(n) time complexity, with space complexity varying from O(log n) to O(n) depending on tree shape and traversal method. Mastering multiple approaches to this fundamental problem equips you with a versatile toolkit for manipulating tree structures in real-world applications, from rendering engines to compiler intermediate representations and beyond.