Invert Binary Tree
LeetCode 226 • Easy • Trees
Input: root = [4, 2, 7, 1, 3, 6, 9] → Output: [4, 7, 2, 9, 6, 3, 1]
Swap the left and right children of every node. Mirror the tree.
TimeO(n)visit each node once
SpaceO(n)stack holds nodes
Swapped: 0/7
Stack: 0
Ready
Press Play. Pop node, swap left & right, push children. Stack-based DFS mirrors the recursive solution.
TimeO(n)visit each node once
SpaceO(h)call stack depth
Recursive: base if root is None return None. Swap root.left, root.right, recurse on both subtrees, return root.
Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.
PATTERN ▸ Swap children, recurse O(n) · O(h)
① BASE CASE
if root is None: return None
② SWAP
root.left, root.right = root.right, root.left
③ RECURSE
self.invertTree(root.left)
self.invertTree(root.right)
④ RETURN
return root
▼ your implementation ▼
Verify your solution: