Approach Summary
Recursively swap left and right children at every node. Post-order or pre-order both work.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Recursive Post-Order Swap (Optimal) | O(n) | O(h) call stack | Recursively invert both children and swap left and right pointers. |
| 2 Approach 2: Iterative BFS Level Order Swap | O(n) | O(w) | Traverse using a queue, swapping left and right children for each dequeued node. |
Step 1: Baseline
Approach 1: Recursive Post-Order Swap (Optimal)
Time: O(n)
Space: O(h) call stack
If root is null, return null. Recursively invert root.left and root.right. Then swap root.left and root.right using a temporary variable, and return root.
Approach 1: Recursive Post-Order Swap (Optimal) Implementation
Approach 1: Recursive Post-Order Swap (Optimal)
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
}
}class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (!root) return NULL;
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return rootfunction invertTree(root) {
if (!root) return null;
const temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
} Step 2: Most Optimized
Approach 2: Iterative BFS Level Order Swap
Time: O(n)
Space: O(w)
Add root to a queue. While the queue is not empty, dequeue a node, swap its left and right children, and enqueue any non-null children. This avoids recursion limits on deeply skewed trees.
Approach 2: Iterative BFS Level Order Swap Implementation
Approach 2: Iterative BFS Level Order Swap
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
TreeNode node = q.poll();
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
if (node.left != null) q.add(node.left);
if (node.right != null) q.add(node.right);
}
return root;
}
}class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (!root) return NULL;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front(); q.pop();
swap(node->left, node->right);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
return root;
}
};from collections import deque
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
q = deque([root])
while q:
node = q.popleft()
node.left, node.right = node.right, node.left
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return rootfunction invertTree(root) {
if (!root) return null;
const q = [root];
while (q.length > 0) {
const node = q.shift();
const temp = node.left;
node.left = node.right;
node.right = temp;
if (node.left) q.push(node.left);
if (node.right) q.push(node.right);
}
return root;
}Edge Cases to Watch
- Empty tree (root is null; returns null)
- Single node (returns root unchanged)
- Asymmetric tree (mirrors correctly into opposite shape)
Algorithmic Pattern
View Pattern Guide →
Master the Trees / DFS Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Trees / DFS pattern.
Framework: Trees / DFS • Interview Prep: Tested at FAANG •
Explore all Trees / DFS problems & invariants →
How to Recognize This Pattern
- Mirror a tree
- Swap children at every node
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(h)
Tags
Tree DFS BFS
Frequently Asked Questions
What is the optimal time and space complexity for Invert Binary Tree?
The optimal solution for Invert Binary Tree achieves O(n) runtime complexity and requires O(h) auxiliary space. Time complexity is O(n) because every node is visited once and has its child pointers swapped in O(1) time. Space complexity is O(h) for recursion or O(w) for the BFS queue.
How do I identify that Invert Binary Tree requires the Trees / DFS pattern?
In technical interviews, look for key problem signals: Mirror a tree; Swap children at every node. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Trees / DFS strategy.
What critical edge cases must be handled in Invert Binary Tree?
Essential edge cases to verify include: Empty tree (root is null; returns null); Single node (returns root unchanged); Asymmetric tree (mirrors correctly into opposite shape). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Invert Binary Tree?
Invert Binary Tree is a Easy-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Apple, Google.