Example 1
ready- Input
root = [ 4, 2, 7, 1, 3, 6, 9 ]- Expected
[ 4, 7, 2, 9, 6, 3, 1 ]- Why
- every left and right branch trades places
Invert Binary Tree
25 min · invertTree()Picture a family tree pressed against wet ink and folded down the middle. Every branch lands on the opposite side.
Given a binary tree's root, invert it by swapping the left and right children of
every node, then return the root of the mirrored tree.
The transformation follows a few firm rules:
- Node values stay unchanged.
- Every former left subtree becomes a right subtree, and vice versa.
- You may swap child links in place; you don't need to create new nodes.
- An empty tree remains empty.
Constraints
0 <= number of nodes <= 10_000-1_000 <= node.val <= 1_000
Hints
One node at a time
At a single node, the local job is only one swap. The remaining work lives inside the two child subtrees.
Choose a traversal
Breadth-first search can swap nodes from the root downward. Depth-first search can invert both subtrees and attach them on opposite sides.
Return the same doorway
After swapping everything below root, the entry point hasn't changed. Return that
root, including from recursive calls.
Follow-up
If the tree were a single branch thousands of nodes deep, how would you invert it without relying on recursion?
Visible cases
Examples
Example 2
ready- Input
root = []- Expected
[]- Why
- there are no child links to swap
Example 3
ready- Input
root = [ 1 ]- Expected
[ 1 ]- Why
- a single node is already its own mirror
Interview signal
Asked at
AmazonGoogleMeta
Breadth-first swaps — mirror one level at a time
Put the root in a queue. For each node you remove, swap its children, then queue the children in their new positions. Each node needs exactly one local operation.
from collections import deque
def invert_tree(root: TreeNode | None) -> TreeNode | None:
if root is None:
return None
queue = deque([root])
while queue:
node = queue.popleft()
node.left, node.right = node.right, node.left
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
return rootQueueing after the swap isn't a correctness requirement — both children still get visited — but it keeps the traversal aligned with the tree you're returning.
Time O(n) — every node is swapped once. Space O(w) — the queue can hold one
level's width, w.
Recursive subtree swap — solve the two smaller mirrors
Ask recursion to invert the original right subtree and attach that result on the left. Do the symmetric operation for the original left subtree.
def invert_tree(root: TreeNode | None) -> TreeNode | None:
if root is None:
return None
original_left = root.left
root.left = invert_tree(root.right)
root.right = invert_tree(original_left)
return rootSaving original_left matters: once root.left is overwritten, you still need a handle
to the subtree that belongs on the right.
Time O(n) — each node performs one swap. Space O(h) — recursive calls occupy one
path of height h.
A 1,200-node line can exceed Python's recursion limit. The breadth-first version above is the stack-safe implementation for arbitrary depth: its queue lives outside the call stack and still performs the same one-swap-per-node work.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[ 4, 7, 2, 9, 6, 3, 1 ]
Run: visible + custom · Submit: full suite