Given the root of a binary tree, invert it — swap the left and right child of every node — and return the new root.
Inverting is a mirror operation: the resulting tree is the reflection of the original across a vertical line through the root.
The tree is given as a level-order array where null marks a missing child: [2, 1, 3] is root 2 with children 1 and 3.
Example
Each node's children swap: 2↔7, 1↔3, 6↔9.
Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
Intuition
Inverting a tree means swapping every node's two children, so the result is the mirror image of the input. The most direct way to picture it is level by level: at each node, exchange its left and right subtrees, then do the same inside each subtree.
function invertTree(root) {
if (!root) return null;
const queue = [root];
while (queue.length) {
const node = queue.shift();
// Swap this node's two children.
const tmp = node.left;
node.left = node.right;
node.right = tmp;
// Visit the children to swap their children too.
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return root;
}That works and is already O(n), but the explicit queue and the temp-swap obscure how simple the idea is. The key observation: inverting a tree is inverting its left subtree, inverting its right subtree, and then swapping the two results. That's a textbook recursion — the structure of the solution mirrors the recursive structure of the tree itself.
The stored solution drops the queue for that recursion: it inverts each subtree first, then assigns them back crossed over. (left and right in the code are the already-inverted subtrees, so the assignment root.left = right is the swap.)
Walking the recursion through [4, 2, 7, 1, 3, 6, 9]:
invert each subtree first, then swap the two results (post-order)
Recurse left first. Node 2's children are leaves; swap them so 3 lands on the left, 1 on the right.
The left subtree is inverted. Same on the right: at node 7, swap 6 and 9.
Both subtrees are inverted. Now swap them at the root: the 7-subtree moves left, the 2-subtree moves right.
Done. Read in level order: [4, 7, 2, 9, 6, 3, 1] — every level reversed, the mirror of the input.
- The empty-tree base case (
if (!root) return null) is what makes the recursion terminate; every leaf's twonullchildren hit it.
Optimization
Recursive swap
At every node, swap its two children, then recurse into both. The order of the swap-versus-recurse steps doesn't matter — every node is visited once and its children exchanged.
O(n) time (each node visited once), O(h) recursion space for tree height h.
function invertTree(root) {
// Empty subtree: nothing to invert, return as-is.
if (!root) return null;
// Swap this node's two children.
const left = invertTree(root.left);
const right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}Complexity analysis
Time complexity: O(n). Here's why:
- The recursion visits each of the
nnodes exactly once. - At each node it does O(1) work — swap two child references.
So the total is n × O(1) = O(n).
Space complexity: O(h). Here's why:
- The only extra space is the recursion call stack, which is as deep as the tree's height
h.
That's O(log n) for a balanced tree and O(n) for a degenerate (single-chain) tree. The output reuses the input nodes, so it isn't counted separately.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| root = []null | []null | Empty tree — nothing to invert. |
| root = [8]8 | [8]8 | Single node — its (absent) children swap to no effect. |
| root = [6,4,9]469 | [6,9,4]964 | Root's two children swap left for right. |
| root = [2,1,null,0]012 | [2,null,1,null,0]210 | A left-only spine inverts into a right-only spine. |
| root = [3,3,3,3]3333 | [3,3,3,null,null,null,3]3333 | Duplicate values: only the positions swap, the structure mirrors. |
Try it yourself
Write your solution against the real judge before checking the reference.