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.
# ─── INVERT BINARY TREE (LeetCode 226) ───
# Pattern: Swap children, recurse
# Time: O(n) Space: O(h)
#
# 1. Define: invertTree(self, root)
#
# 2. Base case: if root is None: return None
#
# 3. Swap left and right: root.left, root.right = root.right, root.left
#
# 4. Recurse left: self.invertTree(root.left)
#
# 5. Recurse right: self.invertTree(root.right)
#
# 6. Return: return root
#
# Vars: root
▼ your implementation ▼
Verify your solution: