Invert Binary Tree

LeetCode 226: Invert Binary Tree Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a recursive Depth-First Search (DFS) traversal to visit every node and swap its left and right child pointers in place.

The Invert Binary Tree problem requires us to take a binary tree and create its mirror image. For every node in the tree, its left child becomes its right child, and its right child becomes its left child. This transformation must apply recursively to all subtrees. This is a fundamental interview question that tests understanding of tree manipulation and recursion.

The LeetCode 226 Solution relies on traversing the entire tree structure. Since every node must be visited to perform the swap, the efficiency is bound by the number of nodes in the tree.

Brute Force Approach for Invert Binary Tree

A common naive approach (often considered "brute force" in terms of space complexity) involves creating a completely new binary tree rather than modifying the existing tree in place.

In this approach, the algorithm traverses the original tree and, for each node encountered, allocates a new TreeNode in memory. It then assigns the inverted children of the original node to this new node.

Pseudo-code:

function invertTreeCopy(root):
    if root is null: return null
    
    newNode = new TreeNode(root.val)
    newNode.left = invertTreeCopy(root.right)  // Assign inverted right to left
    newNode.right = invertTreeCopy(root.left)  // Assign inverted left to right
    
    return newNode

Complexity Analysis:

• Time Complexity: $O(N)$, where $N$ is the number of nodes. We still visit every node once.
• Space Complexity: $O(N)$. Unlike the optimal solution which only uses stack space, this approach allocates $N$ new nodes, doubling the memory footprint required for the tree structure.

Why it fails: While this solution is logically correct and produces the right output, it is suboptimal for interviews. It fails to utilize the existing memory structure. In systems with limited memory or extremely large trees, allocating a duplicate tree is wasteful. The problem implies returning the root of the modified tree, suggesting an in-place mutation is preferred.

Algorithm Strategy: Tree DFS - Recursive Preorder Traversal

The strategy employs a standard recursive DFS structure. We utilize the call stack to manage traversal, eliminating the need for auxiliary data structures like queues.

1. Base Case: If the current root node is null, there is nothing to invert. Return null.
2. Process Node (Preorder Step):
   • Store the reference to the current node's left child in a temporary variable.
   • Assign the current node's right child to its left pointer.
   • Assign the stored temporary variable (original left child) to its right pointer.
3. Recursive Step:
   • Recursively call the invert function on the current node's new left child.
   • Recursively call the invert function on the current node's new right child.
4. Return: Return the current root to satisfy the function signature and allow the parent to link to this inverted subtree.

Note: While Postorder traversal (recurse first, then swap) also works, Preorder is intuitive because it structurally mirrors the definition: "Swap here, then go fix the children."

Execution Flow

Let's trace the execution for root = [4, 2, 7].

1. Call invertTree(4):

   • root is not null.
   • Swap: 4.left becomes 7, 4.right becomes 2.
   • Current state: Root 4 has left child 7, right child 2.
   • Recurse Left: Call invertTree(7).

2. Call invertTree(7) (Left child of 4):

   • root is not null.
   • Swap: 7.left (null) and 7.right (null) are swapped. No visible change.
   • Recurse Left: Call invertTree(null). Returns null.
   • Recurse Right: Call invertTree(null). Returns null.
   • Return node 7.

3. Back in invertTree(4):

   • Left recursion complete.
   • Recurse Right: Call invertTree(2).

4. Call invertTree(2) (Right child of 4):

   • root is not null.
   • Swap: 2.left (null) and 2.right (null) are swapped.
   • Recurse Left: Call invertTree(null). Returns null.
   • Recurse Right: Call invertTree(null). Returns null.
   • Return node 2.

5. Back in invertTree(4):

   • Right recursion complete.
   • Return node 4.

Final Tree: Root 4, Left 7, Right 2. The tree is inverted.

Proof of Correctness

We prove correctness via structural induction:

1. Base Case: An empty tree (root == null) is its own inversion. The algorithm correctly returns null.
2. Inductive Hypothesis: Assume the algorithm correctly inverts any binary tree with height $k$.
3. Inductive Step: Consider a tree of height $k+1$ rooted at $R$.
   • The algorithm swaps $R.left$ and $R.right$. Now, the left pointer points to the original right subtree, and the right pointer points to the original left subtree.
   • The algorithm recursively calls itself on these subtrees. Since these subtrees have height $\le k$, by the hypothesis, they are inverted correctly.
   • Since the root's children are swapped and the subtrees themselves are inverted, the entire tree rooted at $R$ is inverted.

Thus, the algorithm is correct for all binary trees.

Pattern Reuse Notes

The Tree DFS pattern is versatile. Understanding how to visit every node and modify state allows you to solve several related problems:

• LeetCode 100: Same Tree - Instead of swapping, you compare nodes from two trees simultaneously using DFS.
• LeetCode 101: Symmetric Tree - Similar to Invert Binary Tree, but checks if the left subtree is the mirror inversion of the right subtree.
• LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal - Uses Preorder traversal logic to identify root nodes and partition subtrees.
• LeetCode 114: Flatten Binary Tree to Linked List - Uses DFS (often Postorder or reverse Preorder) to rewire pointers in place, similar to the pointer manipulation in Invert Binary Tree.

Reference Implementation

C++ Solution for LeetCode 226

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    TreeNode* invertTree(TreeNode* root) {
15        // Base case: if the node is null, return null
16        if (root == nullptr) {
17            return nullptr;
18        }
19        
20        // Preorder processing: Swap the left and right children
21        TreeNode* temp = root->left;
22        root->left = root->right;
23        root->right = temp;
24        
25        // Recurse on the new left and right children
26        invertTree(root->left);
27        invertTree(root->right);
28        
29        return root;
30    }
31};

Java Solution for LeetCode 226

1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode() {}
8 *     TreeNode(int val) { this.val = val; }
9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16class Solution {
17    public TreeNode invertTree(TreeNode root) {
18        // Base case: if the node is null, return null
19        if (root == null) {
20            return null;
21        }
22        
23        // Preorder processing: Swap the left and right pointers
24        TreeNode temp = root.left;
25        root.left = root.right;
26        root.right = temp;
27        
28        // Recursive calls on the subtrees
29        invertTree(root.left);
30        invertTree(root.right);
31        
32        return root;
33    }
34}

Python Solution for LeetCode 226

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
9        # Base case: if tree is empty, return None
10        if not root:
11            return None
12        
13        # Preorder processing: Swap children
14        # Python allows tuple unpacking for swapping without a temp variable
15        root.left, root.right = root.right, root.left
16        
17        # Recurse on subtrees
18        self.invertTree(root.left)
19        self.invertTree(root.right)
20        
21        return root