Invert Binary Tree
Description
Given the root of a binary tree, invert the tree and return its root.
Inverting a binary tree means swapping the left and right children of every node in the tree. After the inversion, what was originally the left subtree of any node becomes its right subtree, and vice versa. The structure of the tree is preserved — only the positions of children are mirrored.
This operation is sometimes referred to as creating the "mirror image" of the tree. If you imagine placing a mirror along the root, the reflected tree is the inverted version.
Examples
Example 1
Input: root = [4, 2, 7, 1, 3, 6, 9]
Output: [4, 7, 2, 9, 6, 3, 1]
Explanation: The root node 4 stays in place. Its left child 2 and right child 7 are swapped. Then, for node 7 (now left child), its children 6 and 9 are swapped. Similarly, for node 2 (now right child), its children 1 and 3 are swapped. The final tree has every pair of siblings in reversed positions compared to the original.
Example 2
Input: root = [2, 1, 3]
Output: [2, 3, 1]
Explanation: The root 2 remains unchanged. Its left child 1 and right child 3 are swapped. Since both children are leaf nodes with no further children, no additional swaps are needed.
Example 3
Input: root = []
Output: []
Explanation: An empty tree has no nodes to invert. We simply return null.
Constraints
- The number of nodes in the tree is in the range [0, 100]
- -100 ≤ Node.val ≤ 100
Editorial
Brute Force
Intuition
The most straightforward way to invert a binary tree is to use recursion. Think about what inverting means at a single node: you simply swap its left child and its right child. If you do this for every node in the tree, the entire tree gets inverted.
Imagine you are rearranging a family photo. At each generation level, you ask every pair of siblings to switch positions — the one on the left moves to the right, and vice versa. If you start from the bottom and work your way up (or from the top going down), eventually the entire photo is mirrored.
Recursion naturally fits here because the problem has a self-similar structure: inverting a tree is the same as inverting its left subtree, inverting its right subtree, and then swapping them. The base case is when the node is null — there is nothing to invert.
Step-by-Step Explanation
Let's trace through with root = [4, 2, 7, 1, 3, 6, 9]:
The tree looks like:
4
/ \
2 7
/ \ / \
1 3 6 9
Step 1: Call invertTree(4). We need to invert the left subtree rooted at 2 and the right subtree rooted at 7 first.
Step 2: Call invertTree(2). We need to invert node 2's children. Call invertTree(1).
Step 3: Call invertTree(1). Node 1 has no children (both null). Return node 1 unchanged.
Step 4: Call invertTree(3). Node 3 has no children. Return node 3 unchanged.
Step 5: Back at node 2: both subtrees are inverted (both were leaves, so no change). Now swap node 2's left (1) and right (3). Node 2 now has left=3, right=1.
Step 6: Call invertTree(7). We need to invert node 7's children. Call invertTree(6).
Step 7: Call invertTree(6). Node 6 has no children. Return node 6 unchanged.
Step 8: Call invertTree(9). Node 9 has no children. Return node 9 unchanged.
Step 9: Back at node 7: swap left (6) and right (9). Node 7 now has left=9, right=6.
Step 10: Back at node 4: swap left (now-modified 2) and right (now-modified 7). Node 4 now has left=7, right=2.
Result:
4
/ \
7 2
/ \ / \
9 6 3 1
Recursive Tree Inversion — DFS Post-Order — Watch how recursion visits each node bottom-up, swapping left and right children at every level to produce the mirror image of the original tree.
Algorithm
- If the root is null, return null (base case)
- Recursively call invertTree on the left child
- Recursively call invertTree on the right child
- Swap the left and right children of the current node
- Return the current node
Code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
invertTree(root->left);
invertTree(root->right);
swap(root->left, root->right);
return root;
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return None
self.invertTree(root.left)
self.invertTree(root.right)
root.left, root.right = root.right, root.left
return root/**
* 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) {
if (root == null) {
return null;
}
invertTree(root.left);
invertTree(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
return root;
}
}Complexity Analysis
Time Complexity: O(n)
We visit every node in the tree exactly once to perform the swap operation. Since each node requires O(1) work (just a pointer swap), the total time is proportional to the number of nodes, giving us O(n).
Space Complexity: O(h) where h is the height of the tree
The space is consumed by the recursion call stack. In the worst case (a completely skewed tree), the height h equals n, making the space O(n). For a balanced tree, h = log n, so the space would be O(log n). On average for random trees, this is O(log n).
Why This Approach Is Not Efficient
The recursive approach works correctly and has optimal O(n) time complexity — we cannot do better than visiting every node since every node needs its children swapped. However, the recursion uses the call stack, which can be a problem for extremely deep or skewed trees.
If the tree is highly unbalanced (like a linked list), the recursion depth becomes O(n), which could cause a stack overflow for very large inputs. While the constraints for this problem (n ≤ 100) make this unlikely, in production scenarios with larger trees, an iterative approach using an explicit queue or stack gives us more control over memory usage and avoids the risk of stack overflow.
The key insight for the iterative approach is: we do not need to process nodes in any particular order. Since we swap children at every node regardless of what its children look like, we can use a simple level-order traversal (BFS) to visit all nodes and swap as we go.
Optimal Approach - Iterative BFS
Intuition
Instead of using the implicit call stack through recursion, we can use a queue to process nodes level by level. At each node we visit, we simply swap its left and right children, then add both children to the queue for future processing.
Think of it like giving instructions to workers on each floor of a building. You start at the top floor (root). You tell the person there: "swap your two assistants' desks." Then you go to the next floor and give the same instruction to everyone there. You continue floor by floor until you have visited every person. The order in which you process floors does not matter — the instruction is the same everywhere.
This iterative approach achieves the same result as recursion but gives us explicit control over the traversal queue, avoiding any risk of stack overflow.
Step-by-Step Explanation
Let's trace through with root = [4, 2, 7, 1, 3, 6, 9]:
Step 1: Initialize a queue and add the root node 4. Queue: [4]
Step 2: Dequeue node 4. Swap its children: left was 2, right was 7. Now left=7, right=2. Add both children (7 and 2) to the queue. Queue: [7, 2]
Step 3: Dequeue node 7. Swap its children: left was 9 (after parent swap), right was 6. Now left=6, right=9. Wait — at this point, 7's original children were 6 and 9. After the parent (4) swapped, 7 is now on the left. But 7's own children are still 6 (left) and 9 (right). Swap them: left=9, right=6. Add both to queue. Queue: [2, 9, 6]
Step 4: Dequeue node 2. Its children are 1 (left) and 3 (right). Swap: left=3, right=1. Add both to queue. Queue: [9, 6, 3, 1]
Step 5: Dequeue node 9. It is a leaf — no children to swap. Queue: [6, 3, 1]
Step 6: Dequeue node 6. It is a leaf — no children to swap. Queue: [3, 1]
Step 7: Dequeue node 3. It is a leaf — no children to swap. Queue: [1]
Step 8: Dequeue node 1. It is a leaf — no children to swap. Queue: []
Step 9: Queue is empty. Return the root.
Result: [4, 7, 2, 9, 6, 3, 1]
Iterative BFS Inversion — Level-Order Traversal — Watch how BFS processes nodes level by level using a queue, swapping each node's children as it is dequeued. The tree progressively mirrors itself from top to bottom.
Algorithm
- If root is null, return null
- Create a queue and enqueue the root node
- While the queue is not empty:
a. Dequeue the front node
b. Swap its left and right children
c. If the left child exists (after swap), enqueue it
d. If the right child exists (after swap), enqueue it - Return the root
Code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* curr = q.front();
q.pop();
swap(curr->left, curr->right);
if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
}
return root;
}
};# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from collections import deque
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return None
queue = deque([root])
while queue:
curr = queue.popleft()
curr.left, curr.right = curr.right, curr.left
if curr.left:
queue.append(curr.left)
if curr.right:
queue.append(curr.right)
return root/**
* 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) {
if (root == null) {
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode curr = queue.poll();
TreeNode temp = curr.left;
curr.left = curr.right;
curr.right = temp;
if (curr.left != null) queue.add(curr.left);
if (curr.right != null) queue.add(curr.right);
}
return root;
}
}Complexity Analysis
Time Complexity: O(n)
We visit every node in the tree exactly once. At each node, we perform a constant-time swap operation. Therefore, the total time is O(n), where n is the number of nodes in the tree.
Space Complexity: O(n)
The queue holds at most one level of the tree at a time. In the worst case (a complete binary tree), the widest level has approximately n/2 nodes, so the queue uses O(n) space. For a skewed tree, the queue holds at most 1 node at a time, giving O(1) space. However, the worst case remains O(n).
Compared to the recursive approach where space is O(h) (height of tree), the iterative BFS approach trades stack depth for queue width. Both are O(n) in the worst case, but the iterative approach avoids stack overflow risk for deep trees.