Practice: Invert a Binary Tree
A mirror image.
Invert a binary tree, so it becomes its own mirror image. Every left child swaps places with its right child, all the way down. It's a short problem that tests whether you trust recursion.

- A mirror image
- Swap left and right
- All the way down
Swap, then recurse
If the node is empty, there's nothing to do. Otherwise, swap its two children, and invert each of them in the same way. Three lines. We print the tree level by level, before and after. Run it. Each level now reads in reverse.
from tree import sample
from levels import levels
def invert(node):
if node:
node.left, node.right = invert(node.right), invert(node.left)
return node
root = sample()
print(levels(root))
print(levels(invert(root)))[[8], [3, 10], [1, 6, 14], [4, 7, 13]] [[8], [10, 3], [14, 6, 1], [13, 7, 4]]
Also uses tree.py
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
def sample():
return TreeNode(8,
TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
TreeNode(10, None, TreeNode(14, TreeNode(13))))
PICTURE = ' 8\n / \\\n 3 10\n / \\ \\\n 1 6 14\n / \\ /\n 4 7 13'Also uses levels.py
from collections import deque
def levels(root):
out, q = [], deque([root])
while q:
out.append([n.value for n in q])
q = deque(c for n in q for c in (n.left, n.right) if c)
return outRecursion confidence
Interviewers like this problem because it's short, if you trust recursion, and long and messy if you don't. The pattern is the tree recipe again. Handle the empty case, do the work at this node, and let recursion handle the children. It visits each node once, so it's O of N.
| key | value |
|---|---|
| Empty | return it |
| This node | swap children |
| Children | recurse |
| Cost | O(n) |
Summary
Swap the children, and recurse. Inverting a tree is three lines with recursion. Next, merging two sorted linked lists.
Key takeaways- Swap left and right
- Recurse on both
- O(n)