Invert Binary Tree Algorithm Solution

The invert binary tree problem requires flipping a binary tree such that left and right children are swapped at every node. This fundamental tree manipulation problem tests understanding of recursion, tree traversal, and algorithmic thinking in FAANG interviews.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Can we mutate the input tree, or do we need to create a new tree structure?
2. What is the expected time complexity target for the solution? O(n) is the baseline, but are we aiming for optimal or near-optimal?
3. Are there any constraints on the maximum depth or size of the tree?
4. Should we handle null inputs gracefully, or can we assume a valid binary tree?
5. Is there a preference for iterative vs recursive approach?

Restatement of the pattern in my own words: The invert binary tree problem asks us to flip a binary tree such that the left and right children of every node are swapped recursively. This is a canonical tree traversal problem where we need to modify the structure of the tree in-place by reversing the direction of all links.

Signal words and constraint shape that point to this pattern:

• "Invert", "flip", "mirror" - these terms indicate a structural reversal operation
• "Binary tree" - suggests we're dealing with a hierarchical data structure where each node has at most two children
• "Each node's left and right children" - signals that we need to process nodes in a way that swaps their child relationships

Assumptions I am making:

• The input is a valid binary tree (not a graph or multi-way tree)
• We can safely mutate the input structure in-place
• The tree nodes have standard left/right child pointers (no parent references needed)
• We're working with a complete binary tree structure where nodes may have zero, one, or two children

Pattern suitability for scenario types: This pattern is best suited for static scenarios where the entire tree structure is available upfront. It's not naturally suited for streaming data because we need to know the full tree structure before inverting. It's also not an online pattern since there's no incremental processing involved - we must traverse the entire tree to ensure all nodes have their children swapped.

The pattern represents a fundamental tree manipulation operation that serves as a building block for more complex tree algorithms and is often used in technical interviews to assess understanding of recursive thinking and tree traversal patterns.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Invert", "mirror", "flip" — direct indicators of tree transformation
• "Binary tree" — establishes the tree structure with at most two children per node
• "All nodes" — implies a complete traversal is required, not just subset operations
• "Return the root" — suggests the operation modifies in-place or returns a new tree structure

Why this pattern fits better than alternatives: This is fundamentally a tree traversal and transformation problem. Compared to other patterns like graph traversal or array manipulation, it requires specific handling of tree node relationships where each node's left and right children must be swapped. Unlike sorting or searching patterns, this is a structural transformation rather than data organization.

When variations apply:

• For general tree (not just binary) inversion, the same approach applies but with more children to swap
• For streaming tree data, a different pattern like lazy evaluation or incremental updates would be more appropriate
• For non-tree structures (graphs), a different approach like graph traversal with state tracking would be needed

Core insight: The key insight is that inverting a binary tree requires swapping the left and right children of every node in the tree. This can be done recursively or iteratively using a queue, and the operation is symmetric — each node's children are swapped once and only once. The recursive approach naturally handles the tree structure, while iterative approaches can be more memory-efficient for very deep trees.

This pattern is most effective when the entire tree structure needs to be transformed rather than just values being rearranged or filtered.

3. Approach Evolution

Interview communication script:

My first instinct is to think about how I would manually invert a binary tree - I'd start from the root and swap left and right children, then recursively apply the same logic to each subtree. But let me think about this more carefully.

If I do a naive recursive approach where I swap the left and right children at each node, that's actually quite clean and intuitive. But I should consider whether this is O(n) time complexity - yes, because I need to visit each node once. The space complexity would be O(h) where h is the height due to recursion stack.

Let me think about whether I could do this iteratively with a queue or stack. That's definitely possible and might be preferred in some environments where recursion depth is a concern.

Actually, let me reframe this more precisely. The key insight is that I want to traverse the tree and for every node, swap its left and right children. The order of traversal doesn't fundamentally change the solution - I could do pre-order, in-order, or post-order traversal. But since I'm just swapping children regardless of order, any traversal works.

The brute force approach would be to create a completely new tree with inverted structure. But that's wasteful - I should just modify the existing nodes in-place.

The key optimization here is not really about reducing time complexity, but rather ensuring that I'm doing the minimum necessary work. Since every node needs to have its children swapped, and I must process all nodes, O(n) time is optimal. The space complexity can be reduced to O(1) if I do it iteratively with a queue.

My approach will be recursive, as it's clean and intuitive. I'll traverse the tree in pre-order fashion, swap left and right children at each node, then recursively process both subtrees. This maintains the invariant that every node's children are properly swapped before I move to its descendants.

Brute-force approach and why it is not ideal:

The brute force approach would be to create a completely new binary tree with inverted structure. This involves:

1. Traversing the original tree once to collect all nodes
2. Creating new nodes with swapped values
3. Building the inverted tree structure from scratch

This is inefficient because it requires O(n) extra space for the new tree and O(n) time to build it. It's also unnecessarily complex - we don't need to create a new structure, just modify the existing one in-place.

Improved approach and the key optimization:

The improved approach is to do an in-place modification of the existing tree structure. The key optimization is recognizing that we only need to swap left and right children at each node, and we can do this recursively or iteratively without creating new nodes.

The key insight is that the problem asks for inverting the tree structure, not reorganizing values - so we can simply swap references to left and right children at each node.

Final approach with step-by-step reasoning:

1. Start from the root node
2. If current node is null, return (base case)
3. Swap the left and right children of current node
4. Recursively invert the left subtree (which was originally right)
5. Recursively invert the right subtree (which was originally left)
6. Return the root node

Important invariants that must hold:

• At each step, we have a valid binary tree structure
• After swapping, the left child becomes what was originally the right child and vice versa
• The recursive structure ensures we process every node exactly once
• The tree remains connected throughout the operation

Edge case considerations:

• Empty tree (root is null) - should return null
• Single node tree - no children to swap, but operation completes correctly
• Complete binary tree vs skewed tree - same algorithm works, just different traversal patterns

4. Data Structure Choice

Primary data structures used

• Binary Tree Node: The core data structure representing each node in the binary tree
• Stack/Queue: For iterative traversal (optional but commonly used for clean implementation)

Why each data structure is needed

• Binary Tree Node: Essential for representing the tree structure with left and right children pointers, and node value storage
• Stack/Queue: Used for iterative approaches to avoid recursion stack overflow and provide explicit control over traversal order

Time and space impact of each choice

• Binary Tree Node: O(1) time for node operations, O(n) space for n nodes in the tree
• Stack/Queue: O(n) space worst-case for iterative approaches (when tree is completely unbalanced), O(log n) best-case for balanced trees

Helper structure usage

• No helper structures needed: The solution can be implemented using only the standard tree node structure and basic traversal mechanisms
• Recursive approach: Uses call stack implicitly, requiring no additional data structures beyond the natural recursion mechanism

The choice of iterative vs. recursive approach depends on system constraints (stack overflow risk) and preference for clean code structure, but both use the same fundamental tree node representation.

5. Algorithm Walkthrough

Let me trace through the invert binary tree algorithm using a concrete example.

Consider this input tree:

    4
   / \
  2   7
 / \ / \
1  3 6  9

Step 1: Start with root node 4. We need to swap its left and right children.

• Before swap: left=2, right=7
• After swap: left=7, right=2

Step 2: Now process the left subtree rooted at node 2.

• Node 2 has left=1 and right=3
• After swap: left=3, right=1

Step 3: Process the right subtree rooted at node 7.

• Node 7 has left=6 and right=9
• After swap: left=9, right=6

Step 4: Continue recursively to the leaf nodes.

• Node 1: No children, so no swap needed
• Node 3: No children, so no swap needed
• Node 6: No children, so no swap needed
• Node 9: No children, so no swap needed

Final result:

    4
   / \
  7   2
 / \ / \
9  6 3  1

The algorithm terminates correctly because:

1. Each node is visited exactly once
2. For each node, we swap its left and right children before recursively processing them
3. Base case (null node) prevents stack overflow
4. The recursive structure ensures all nodes are processed in bottom-up fashion

Edge cases handled:

• Empty tree (null root) returns null
• Single node tree returns same node
• Complete binary tree processes all levels properly

6. Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        // Base case: if node is null, return null
        if (root == null) {
            return null;
        }
        
        // Swap left and right children
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        // Recursively invert left and right subtrees
        invertTree(root.left);
        invertTree(root.right);
        
        return root;
    }
}

This solution uses a recursive approach to invert the binary tree. At each node, we swap its left and right children, then recursively process both subtrees. The base case handles null nodes, ensuring we don't attempt to access properties of null references. The in-place modification avoids additional space overhead for storing new nodes, making it memory efficient while maintaining clean code structure.

7. Complexity Analysis

Time Complexity: O(n) where n is the number of nodes in the binary tree. Each node is visited exactly once during the traversal, and the inversion operation at each node takes constant time O(1). The algorithm performs a complete tree traversal, making it linear in terms of the number of nodes.

Space Complexity: O(h) where h is the height of the binary tree. This space is used by the call stack during the recursive traversal. In the worst case (skewed tree), h = n, making space complexity O(n). In the best case (balanced tree), h = log n, resulting in O(log n) space complexity.

The bounds are correct because:

• Every node is processed exactly once, ensuring linear time
• The recursion depth equals the tree height, which determines the maximum call stack size
• For a balanced binary tree, the depth is logarithmic, providing optimal space usage

This solution is optimal for the problem as it achieves the best possible time complexity O(n) and space complexity O(h) for a recursive approach. Any iterative solution would have the same asymptotic bounds but with potentially more complex implementation due to explicit stack management.

The solution is near-optimal because:

1. We cannot do better than O(n) time since we must examine each node at least once to determine its inverted state
2. We cannot do better than O(h) space for the recursive approach due to the call stack requirements
3. Any alternative traversal method (BFS with queue) would also require O(w) space where w is the maximum width, which in worst case is O(n) - but this is still bounded by O(n) and the recursive approach is more intuitive for tree problems

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty tree: The solution must handle null root gracefully, returning null without any operations
• Single node: A tree with only a root node should return the same node (inverted tree is identical)
• Null left/right children: When a node has null left or right child, we must still process the non-null child

Duplicate Values and Repeated States

• The algorithm works correctly with duplicate values in nodes since inversion is a structural operation, not value-dependent
• The same tree structure with repeated values should produce the same inverted result

Boundary Conditions

• Deep unbalanced trees: The solution must handle very deep left/right skewed trees without stack overflow (though recursion depth is acceptable for this problem)
• Complete binary trees: Should invert all nodes properly maintaining the mirror symmetry

Common Implementation Mistakes

• Incorrect pointer swapping: Swapping values instead of references, which doesn't actually invert the tree structure
• Missing null checks: Not checking if left/right nodes are null before recursive calls, leading to NullPointerException
• Inefficient recursion: Using a recursive approach that unnecessarily rebuilds nodes rather than in-place swapping
• Incorrect base case handling: Forgetting to return null for null input, or not properly handling leaf nodes

// Example of incorrect approach:
// TreeNode temp = node.left;  // This copies the reference, not the structure
// node.left = node.right;
// node.right = temp;

// Correct approach:
// TreeNode temp = node.left;  // This swaps references correctly
// node.left = node.right;
// node.right = temp;

The key pitfall is assuming that value swapping is sufficient for tree inversion, when in fact we must swap the actual node references to achieve structural mirroring.

9. Alternative Approaches

There are several alternative approaches to inverting a binary tree, each with different trade-offs:

Iterative BFS/Level-order Traversal: Instead of recursion, we can use a queue to process nodes level by level. This approach avoids potential stack overflow for very deep trees and uses explicit queue management. The logic remains the same - for each node, swap its left and right children and add them to the queue.

Morris Traversal: For a space-optimized solution that uses O(1) extra space (excluding recursion stack), we could theoretically adapt Morris traversal to process nodes in-order. However, this is more complex and less intuitive for the inversion problem, as it requires careful handling of threading.

Post-order Iteration: We could process nodes in post-order (left, right, root) and swap children during the traversal. This requires more careful state management but avoids the need for a separate queue or recursion stack.

Custom Stack Implementation: Rather than using the call stack, we could implement our own stack with explicit node tracking. This gives us more control over the traversal but adds complexity.

The chosen recursive approach is preferred because:

1. It's more readable and intuitive
2. The problem naturally fits a recursive pattern (invert left subtree, invert right subtree, swap current node)
3. The space complexity is acceptable for most practical inputs (O(h) where h is height)
4. It's easier to reason about and debug

The iterative approaches are more complex to implement correctly and don't provide significant advantages for this specific problem. The recursive solution is clean, maintainable, and performs well in typical scenarios.

10. Test Cases

// Test case 1: Basic binary tree
//     4
//    / \
//   2   7
//  / \ / \
// 1  3 6  9
TreeNode root1 = new TreeNode(4);
root1.left = new TreeNode(2);
root1.right = new TreeNode(7);
root1.left.left = new TreeNode(1);
root1.left.right = new TreeNode(3);
root1.right.left = new TreeNode(6);
root1.right.right = new TreeNode(9);

// Test case 2: Single node
TreeNode root2 = new TreeNode(1);

// Test case 3: Empty tree
TreeNode root3 = null;

// Test case 4: Skewed tree (left skewed)
//   1
//    \
//     2
//      \
//       3
TreeNode root4 = new TreeNode(1);
root4.right = new TreeNode(2);
root4.right.right = new TreeNode(3);

// Test case 5: Complete binary tree
//     1
//    / \
//   2   3
//  / \ / \
// 4  5 6  7
TreeNode root5 = new TreeNode(1);
root5.left = new TreeNode(2);
root5.right = new TreeNode(3);
root5.left.left = new TreeNode(4);
root5.left.right = new TreeNode(5);
root5.right.left = new TreeNode(6);
root5.right.right = new TreeNode(7);

The test cases cover:

• A typical balanced binary tree with multiple levels
• Edge case of single node (degenerate case)
• Empty input scenario
• Left-skewed tree to test boundary conditions
• Complete binary tree for comprehensive validation

Each test case should produce the expected inverted structure when passed through the invertTree method. The solution should handle all these cases correctly, maintaining proper tree structure and node relationships after inversion.

11. Final Summary

The core idea is to swap left and right children of every node in a binary tree using recursive DFS traversal. This solution works because each node's children are processed independently, and the inversion is naturally propagated down to all descendants. The approach is optimal with O(n) time complexity where n is the number of nodes, and O(h) space complexity where h is the height due to the recursion stack. The solution elegantly handles all edge cases including empty trees and single-node trees through base case checks, making it both clean and efficient for the invert binary tree problem.