Invert Binary Tree — Solution in Python, Java & C++
Invert Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Invert Binary Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, invert it — swap the left and right children of every node, producing the tree's mirror image — and return its root.
Example 1
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Explanation: Every level now reads right to left.
Example 2
Input: root = [2,1]
Output: [2,null,1]
Explanation: The single left child becomes a right child.
Example 3
Input: root = []
Output: []
Constraints
The number of nodes in the tree is in the range [0, 100]-100 <= Node.val <= 100
Hints for Invert Binary Tree
Hint 1
Inverting a tree means inverting both subtrees and then swapping them.
Hint 2
Write it as a recursion whose base case is the empty tree.
Hint 3
Any traversal order works as long as every node has its two child pointers swapped exactly once — a BFS queue does it iteratively.
How to solve Invert Binary Tree
The mirror of a tree is its root with the mirror of the right subtree on the left and the mirror of the left subtree on the right. Swapping the two child pointers at every node, in any order, builds exactly that.
Approach
- If
rootis null, return null. - Invert the left and right subtrees recursively.
- Assign the inverted right subtree to
root.leftand the inverted left subtree toroot.right. - Return
root.
Why it works
By induction on height: the recursive calls return mirrored subtrees, and placing them on the opposite sides mirrors the whole tree. Each node is visited once and its pointers swapped once, so nothing is swapped back.
Complexity
- Time —
O(n) - Space —
O(h) recursion depth
Pitfalls
- Overwriting
root.leftbefore saving it loses the left subtree — keep one side in a temporary. - Swapping a node's pointers twice (for example, once on the way down and once on the way up) undoes the inversion.
Reference solution
Python
from typing import Optional
def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return None
root.left, root.right = invertTree(root.right), invertTree(root.left)
return rootJava
public static TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode l = invertTree(root.left);
root.left = invertTree(root.right);
root.right = l;
return root;
}C++
TreeNode* invertTree(TreeNode* root) {
if (!root) return nullptr;
TreeNode* l = invertTree(root->left);
root->left = invertTree(root->right);
root->right = l;
return root;
}JavaScript
var invertTree = function(root) {
if (root === null) return null;
var l = invertTree(root.left);
root.left = invertTree(root.right);
root.right = l;
return root;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)