Invert Binary Tree Algorithm Solution

Inverting a binary tree requires swapping each node's left and right children recursively or iteratively. This solution presents both approaches with detailed complexity analysis and practical implementation considerations for FAANG-level interviews.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can we mutate the input tree, or do we need to create a new tree?
2. What is the expected time complexity constraint? O(n) is acceptable, but are we aiming for better?
3. Are there any constraints on the tree size (e.g., max depth, node count)?
4. Should we handle null inputs gracefully or assume valid tree nodes?
5. Do we need to preserve the original tree structure in any way?

Restatement of problem: Given the root of a binary tree, invert the tree by swapping all left and right child nodes recursively or iteratively. The inverted tree should have the same structure but with all children mirrored.

Input and Output specification:

• Input: Root node of a binary tree (TreeNode type with left, right, and val fields)
• Output: Root node of the inverted binary tree
• Constraints: Tree can have 0 to 100 nodes, node values are in [-100, 100]

Assumptions:

• The TreeNode class is already defined with proper fields (val, left, right)
• We can modify the tree in-place if needed
• The input is a valid binary tree structure

Data shape and hidden structure: The problem involves a hierarchical tree structure where each node has at most two children. The key insight is that we need to perform a symmetric transformation across the entire tree structure, which suggests a recursive or level-by-level traversal approach. The hidden structure is that this operation can be viewed as applying a "mirror" transformation to the entire tree's node relationships.

The problem is asking for a structural transformation rather than value manipulation, which makes it a classic tree traversal and modification problem with clear invariants around node relationships.

2. Pattern Recognition

The problem asks us to invert a binary tree, which means swapping every node's left and right children recursively throughout the tree.

Most likely patterns:

1. Tree Traversal Pattern - This is fundamentally about visiting every node in a tree structure and performing an operation (swapping children)
2. Recursive Tree Manipulation - The operation needs to be applied consistently across all nodes in a hierarchical manner
3. Symmetric Operation Pattern - Swapping left and right children creates a symmetric transformation

Wording that signals the pattern:

• "Invert" - suggests a symmetric or mirrored operation
• "Binary tree" - indicates hierarchical structure with left/right children
• "Every node" - implies traversal through all nodes

Why this fits the pattern: This problem requires applying a consistent transformation (swapping) to every node in a tree structure. The key insight is that this operation must be applied recursively or iteratively to every node in the tree, maintaining the hierarchical relationship while flipping the directional structure.

Core insight: The solution requires a traversal that visits each node and swaps its left and right children. This can be done with any tree traversal method (preorder, inorder, postorder), but preorder is most intuitive since we process the current node before its children.

The pattern is that this is a tree transformation problem where each node needs to be visited once and modified in-place, making it ideal for recursive or iterative traversal approaches with O(n) time complexity.

3. Approach Evolution

My first instinct is to think about how I would manually invert a binary tree - I'd start from the root and swap its left and right children, then recursively do the same for each child. This suggests a recursive approach that's O(n) time complexity, which is optimal since we need to visit every node at least once.

But let me think about this more carefully. If I do a simple recursive approach where I swap left and right children at each node, that's straightforward but let me consider if there are any edge cases I'm missing. Actually, wait - what happens if the tree is empty? Or if it has only one node?

Let me think about how to optimize this. The brute force approach would be to create a completely new tree by copying all nodes and placing them in inverted positions, but that's wasteful - we're not leveraging the fact that we can just swap references in place.

I notice that if I maintain the invariant that at each node, I've already processed its children before processing the current node, I can do this iteratively with a stack or queue. But since we're doing a tree traversal, the recursive approach naturally maintains this invariant.

Actually, let me think about whether I can do better than O(n) - no, that's impossible since we must visit each node to invert it. So O(n) is optimal for both time and space complexity.

The key insight here is that we want to do a pre-order traversal (or any traversal) and swap the left and right children at each node. The recursive approach is cleanest and most intuitive.

The brute force approach would be to create a new tree with the same structure but inverted, which is O(n) time and O(n) space. But this is wasteful because we're not reusing the existing nodes.

The improved approach is to do in-place swapping using recursion, which gives us O(n) time and O(h) space where h is the height of the tree due to the recursion stack.

The final approach I'll use is a clean recursive solution that swaps left and right children at each node, ensuring we process all nodes exactly once.

The important invariants that must hold:

1. At each node, we have already processed its children before swapping
2. We don't lose references to nodes during the swap operation
3. The recursion properly handles base cases (null nodes)
4. We maintain the tree structure while only swapping child pointers

4. Data Structure Choice

For inverting a binary tree, the primary data structure is the TreeNode class itself, which represents the nodes in the binary tree. Each node contains:

• An integer value (val)
• References to left and right child nodes (left and right)

The TreeNode class is essential because it defines the structure of our input data and provides the necessary fields to perform the inversion operation.

Why TreeNode is needed:

• It represents the fundamental unit of our problem (each node needs to have its left and right children swapped)
• It provides the hierarchical structure that makes tree traversal possible
• It's the input/output format for this problem

Time and space impact:

• Time complexity is not affected by the choice of data structure since we must visit each node at least once
• Space complexity is O(h) where h is the height of the tree due to recursion stack depth (in worst case for skewed trees, this becomes O(n))

Helper structures:

• No additional helper data structures are needed for the core algorithm
• The recursive approach naturally uses the call stack as our "helper" structure
• An iterative solution could use a Stack<TreeNode> or Queue<TreeNode> but the recursive approach is more intuitive for this problem

The choice of TreeNode as our primary data structure is optimal because it directly models the input and output requirements without introducing unnecessary complexity or overhead. The problem's nature as a tree traversal and modification makes this the natural and efficient data structure choice.

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;
    }
}

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Consider this binary 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: left = 2, right = 7
• After: left = 7, right = 2

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

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

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

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

Step 4: Continue recursively to the leaf nodes.

• For node 6: no children, so nothing to swap
• For node 9: no children, so nothing to swap
• For node 1: no children, so nothing to swap
• For node 3: no children, so nothing to swap

Final result:

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

The algorithm correctly inverts the tree by recursively swapping each node's left and right children, processing from root to leaves. The key insight is that we must process each node exactly once and maintain the invariant that for any node, its children are swapped before we proceed to their subtrees.

Edge cases are handled naturally:

• Empty tree (null root): returns null immediately
• Single node: no children to swap, so returns the same node
• Skewed trees: still processes all nodes in the correct order

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. For each node, we swap its left and right children, then recursively apply the same process to both subtrees. The base case handles null nodes, ensuring we don't attempt operations on non-existent nodes.

The implementation is clean and follows the natural recursive structure of tree problems. We're modifying the tree in-place by swapping references rather than creating new nodes, which makes it memory efficient. The solution handles all edge cases including empty trees and single-node trees naturally through the base case.

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 single pass through all nodes, making it linear in the size of the input tree.

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 matches the tree height, which determines the maximum call stack size
• The algorithm does not use any additional data structures that scale with input size beyond the recursion stack

This solution is optimal for the problem since we must examine each node at least once to invert its children, making O(n) time complexity unavoidable. The space complexity is also optimal for the recursive approach, as we cannot avoid using stack space proportional to the tree height.

The solution is near-optimal in terms of both time and space complexity for this recursive inversion problem, with no better approach existing that would reduce either complexity class.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty tree: The solution must handle root == null gracefully, returning null without any operations
• Single node: A tree with only root node should return the same node (inverted tree is identical)
• Null left/right children: When a node has null children, the inversion should not cause null pointer exceptions

Duplicate Values and Repeated States

• Duplicate values in tree: The algorithm works identically regardless of whether values are duplicated, since we're only swapping references
• Balanced vs unbalanced trees: The algorithm handles all tree structures uniformly without special handling for balance

Boundary Conditions

• Deeply nested trees: The recursive approach works but could cause stack overflow for very deep trees (though this is more of a system limitation than an algorithmic issue)
• Perfect binary tree: Should work correctly with all nodes having exactly 0 or 2 children
• Skewed trees: Left-skewed or right-skewed trees should be handled properly

Common Implementation Mistakes

• Incorrect reference swapping: Swapping values instead of node references leads to wrong structure
• Missing null checks: Not checking for null children before accessing .left or .right properties
• Infinite recursion: Not properly terminating the recursive calls when reaching leaf nodes
• Modifying input incorrectly: Some candidates attempt to modify the original tree in-place but don't properly handle the reference updates, leading to incorrect structure

Implementation-specific Pitfalls

// WRONG: Swapping values instead of references
TreeNode temp = root.left;
root.left = root.right;
root.right = temp; // This modifies the actual values, not node structure

// CORRECT: Swapping references properly
TreeNode temp = root.left;
root.left = root.right;
root.right = temp; // This correctly swaps node references

The solution must ensure that we're swapping the actual TreeNode objects, not just their values, to properly invert the tree structure.

9. Alternative Approaches

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

1. Iterative BFS/Level-order Traversal Instead of recursion, we can use a queue to process nodes level by level. For each node dequeued, we swap its left and right children and enqueue the children for processing. This approach avoids potential stack overflow issues with very deep trees and uses explicit queue management.

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        // Swap left and right children
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    
    return root;
}

2. Morris Traversal (Space-Optimized) For a true O(1) space solution, we could theoretically use Morris traversal to do in-order or pre-order traversal without recursion or stack. However, this is complex and not practical for tree inversion since we need to process nodes in a specific order that makes the Morris approach unwieldy.

3. Post-order Traversal with Stack We can simulate post-order traversal using a stack where we process nodes in reverse post-order (right, left, root). For each node popped from stack, we swap its children. This approach is more complex than the simple recursive solution and doesn't provide significant benefits.

Trade-offs:

• The iterative BFS approach trades stack space for queue space and handles deep trees better
• The recursive approach is cleaner, more readable, and has the same O(n) time complexity but with O(h) space where h is height
• The Morris approach would save space but adds significant complexity and isn't practical for this problem

The recursive solution is preferred because it's the most readable, intuitive, and performs well in practice. The iterative BFS approach is a reasonable alternative when stack overflow is a concern or when the interviewer specifically asks for an iterative solution.

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 (null root)
• Left-skewed tree to verify traversal direction handling
• Complete binary tree to ensure all nodes are processed correctly

Each test case validates different aspects of the inversion logic and helps confirm correctness across various tree structures.

11. Final Summary

The core idea is to systematically swap left and right children of every node in a binary tree using either recursive DFS or iterative BFS approaches. This solution works because it leverages the fundamental property that inverting a tree requires reversing the direction of all child relationships while maintaining the structural hierarchy.

The efficiency comes from processing each node exactly once with O(n) time complexity and O(h) space complexity where h is the tree height, making it optimal for this problem. The recursive approach is clean and intuitive, while the iterative approach avoids potential stack overflow issues in very deep trees. Both solutions handle all edge cases including empty trees, single nodes, and completely unbalanced structures.

The key insight is that this problem is fundamentally about tree traversal with a simple transformation at each node - swapping references rather than restructuring the entire tree, which makes it an ideal candidate for both recursive and iterative solutions with clear trade-offs between code readability and memory usage.