Invert Binary Tree
Problem
Given the root of a binary tree, invert the tree and return its root such that the left and right children of all nodes are swapped.
- The number of nodes in the tree is in the range [0, 100].
- −100 ≤ Node.val ≤ 100
Example
root = [4,2,7,1,3,6,9][4,7,2,9,6,3,1]Starting at the root node with value 4, the algorithm swaps its left child (2) and right child (7). Then it recursively inverts the left subtree rooted at 7 and the right subtree rooted at 2. For node 7, its children 6 and 9 are swapped. For node 2, its children 1 and 3 are swapped. This process continues recursively until all nodes have their children swapped, resulting in the inverted tree.
Approach
Straightforward Solution
A brute-force approach might attempt to collect all nodes and then swap children iteratively, but this requires extra space and complicates traversal order. Alternatively, a level-order traversal could be used, but it is more complex and less natural for this problem.
Core Observation
Inverting a binary tree is a structural transformation where each node's left and right children are swapped. This operation must be applied recursively to every node in the tree to achieve a full inversion.
Path to Optimal
The key insight is that the inversion operation is naturally recursive: inverting a tree is equivalent to swapping the children of the root and then recursively inverting the left and right subtrees. This leads directly to a depth-first traversal approach where the swap happens at each node before recursing.
Optimal Approach
Use a recursive DFS approach. For each node, swap its left and right children, then recursively call the inversion function on the new left and right children. The recursion naturally terminates at leaf nodes or null children. This approach is simple, elegant, and runs in O(n) time with O(h) space due to recursion stack, where h is the tree height.
Time
O(n)
Each node is visited exactly once to perform the swap operation, resulting in linear time proportional to the number of nodes.
Space
O(h)
The recursion stack depth is proportional to the height of the tree, which is O(h). This is the auxiliary space used, excluding the input and output tree structures.
Pattern Spotlight
DFS (Recursive Tree Traversal)
When a problem requires applying a transformation to every node in a tree, a recursive DFS that processes the current node and then recurses on children is the most natural and efficient approach.
Solution
| 1 | class Solution:
|
| 2 | def invertTree(self, root: TreeNode) -> TreeNode:
|
| 3 | if not root:
|
| 4 | return None
|
| 5 |
|
| 6 | root.left, root.right = root.right, root.left
|
| 7 |
|
| 8 | self.invertTree(root.left)
|
| 9 | self.invertTree(root.right)
|
| 10 |
|
| 11 | return root |
| 1 | class Solution { |
| 2 | public TreeNode invertTree(TreeNode root) { |
| 3 | if (root == null) { |
| 4 | return null; |
| 5 | } |
| 6 | |
| 7 | TreeNode temp = root.left; |
| 8 | root.left = root.right; |
| 9 | root.right = temp; |
| 10 | |
| 11 | invertTree(root.left); |
| 12 | invertTree(root.right); |
| 13 | |
| 14 | return root; |
| 15 | } |
| 16 | } |
Step-by-Step Solution
Return None for Empty Tree to Handle Base Case
| 3 | if not root:
|
| 4 | return None
|
Objective
To immediately return None when the current node is null, terminating recursion at leaf boundaries.
Key Insight
The base case of the recursion is critical to prevent infinite recursion and to correctly handle empty subtrees. Returning None when the node is null ensures that leaf nodes' children are handled gracefully and recursion unwinds properly.
Interview Quick-Check
Core Logic
The base case check `if not root: return None` prevents further recursion and correctly handles empty subtrees.
State & Boundaries
This base case defines the recursion boundary, ensuring the algorithm terminates at leaf nodes.
Swap Left and Right Children to Invert Current Node
| 6 | root.left, root.right = root.right, root.left
|
Objective
To invert the current node by swapping its left and right child pointers.
Key Insight
Swapping the children at the current node is the fundamental operation that inverts the tree structure. This local swap, combined with recursive inversion of subtrees, ensures the entire tree is inverted.
Interview Quick-Check
Core Logic
Swapping `root.left` and `root.right` in place inverts the current node's immediate children.
Common Pitfalls & Bugs
Failing to swap children before recursive calls can lead to incorrect inversion or redundant operations.
Recursively Invert Left and Right Subtrees After Swap
| 8 | self.invertTree(root.left)
|
| 9 | self.invertTree(root.right)
|
Objective
To recursively apply the inversion operation to the subtrees rooted at the swapped children.
Key Insight
After swapping, the left and right subtrees are inverted recursively. This ensures the inversion propagates down the entire tree, not just the root node. The recursion naturally handles all nodes in a depth-first manner.
Interview Quick-Check
Core Logic
Recursive calls on `root.left` and `root.right` invert the subtrees after the swap, completing the full tree inversion.
State & Boundaries
Recursion terminates at leaf nodes due to the base case check for null nodes.
Return Root to Provide Inverted Tree to Caller
| 11 | return root |
Objective
To return the root node of the inverted subtree to the caller, enabling reconstruction of the full inverted tree.
Key Insight
Returning the root after inversion allows the recursive calls to assemble the inverted tree correctly. This return value propagates up the call stack, ultimately returning the fully inverted tree to the initial caller.
Interview Quick-Check
Core Logic
Returning `root` after inversion ensures the caller receives the correctly inverted subtree.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
root.left, root.right = root.right, root.leftSwap the left and right children of the current node.
This in-place swap is the fundamental operation that inverts the tree structure at the current node, enabling the recursive inversion to propagate correctly.
if not root:Check if the current node is null to handle the base case.
This base case prevents infinite recursion by terminating the traversal when a leaf's child is reached, which is essential for correctness.
self.invertTree(root.left)Recursively invert the left subtree after swapping.
Recursing on the swapped left child ensures the entire left subtree is inverted, maintaining the correctness of the full inversion.
self.invertTree(root.right)Recursively invert the right subtree after swapping.
Recursing on the swapped right child completes the inversion of the right subtree, ensuring the entire tree is processed.
return NoneReturn None for null nodes to end recursion.
Returning None here correctly represents an empty subtree and allows the recursion to unwind properly.
return rootReturn the root node of the inverted subtree.
Returning the root allows the recursive calls to reconstruct the inverted tree correctly and provides the final inverted tree to the initial caller.
Test Your Understanding
Why does swapping the children before the recursive calls not affect the correctness of the inversion?
Because after swapping, the recursive calls invert the subtrees rooted at the swapped children, ensuring the entire tree is inverted correctly. The order of recursion does not matter as long as both subtrees are inverted.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Invert Binary Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Invert Binary Tree drill