Invert Binary Tree
EasyPrompt
Given the root of a binary tree, invert the tree, and return its root.
Example 1:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]Example 2:
Input: root = [2,1,3]
Output: [2,3,1]Example 3:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
We can solve this problem using a recursive approach where we swap the left and right children of each node recursively.
Algorithm
- Check if root is null, return null if true
- Store left child in temporary variable
- Assign right child to left child
- Assign temporary variable (original left child) to right child
- Recursively call invertTree on left child
- Recursively call invertTree on right child
- Return root
Walkthrough
The recursive approach works by traversing the binary tree and swapping the left and right children of each node. For each node:
- First check if the root is null, if yes return null
- Swap the left and right children of the current node
- Recursively invert the left subtree
- Recursively invert the right subtree
- Return the root node
Here's the implementation:
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 root is null, return null if (root == null) { return null; } // Swap the 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; }}Complexity
Time
O(n) where n is the number of nodes in the tree as we need to visit each node once
Space
O(h) where h is the height of the tree due to the recursive call stack. In worst case (skewed tree) it can be O(n)
Trade-offs
Pros
Simple and easy to understand
Clean and concise code
Uses less space compared to iterative approach
Cons
Can cause stack overflow for very deep trees
Recursive calls may have overhead
We can solve this problem iteratively using a queue to perform level order traversal and swap the children of each node.
Algorithm
- If root is null, return null
- Create a queue and add root to it
- While queue is not empty:
- Poll node from queue
- Swap left and right children
- Add non-null left child to queue
- Add non-null right child to queue
- Return root
Walkthrough
The iterative approach uses a queue to perform a level-order traversal of the tree. For each node we encounter:
- Remove the node from the queue
- Swap its left and right children
- Add the non-null children to the queue
- Continue until the queue is empty
Here's the implementation:
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.offer(root); while (!queue.isEmpty()) { TreeNode current = queue.poll(); // Swap the children TreeNode temp = current.left; current.left = current.right; current.right = temp; // Add non-null children to queue if (current.left != null) { queue.offer(current.left); } if (current.right != null) { queue.offer(current.right); } } return root; }}Complexity
Time
O(n) where n is the number of nodes in the tree as we need to visit each node once
Space
O(w) where w is the maximum width of the tree. In worst case (complete binary tree) it can be O(n/2) ≈ O(n)
Trade-offs
Pros
Avoids recursion stack overflow
More intuitive for level-order processing
Better for very deep trees
Cons
Uses more space than recursive approach for most cases
Slightly more complex implementation
Additional data structure (queue) needed
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public TreeNode InvertTree ( TreeNode root ) { if ( root == null ) { return null ; } TreeNode l = InvertTree ( root . left ); TreeNode r = InvertTree ( root . right ); root . left = r ; root . right = l ; 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 ) { dfs ( root ); return root ; } private void dfs ( TreeNode root ) { if ( root == null ) { return ; } TreeNode t = root . left ; root . left = root . right ; root . right = t ; dfs ( root . left ); dfs ( root . right ); } }/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {TreeNode} */ var invertTree = function (root) { const dfs = (root) => { if (!root) { return; } [root.left, root.right] = [root.right, root.left]; dfs(root.left); dfs(root.right); }; dfs(root); return root; };/** * 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 ) { function < void ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) { if ( ! root ) { return ; } swap ( root -> left , root -> right ); dfs ( root -> left ); dfs ( root -> right ); }; dfs ( root ); 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 ]: def dfs ( root ): if root is None : return root . left , root . right = root . right , root . left dfs ( root . left ) dfs ( root . right ) dfs ( root ) return rootVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.