The short answer
Ten tree traversal patterns cover almost every tree problem in interviews: preorder, inorder, postorder, level-order BFS, zigzag level-order, iterative traversal with stack, Morris traversal, path sum DFS, lowest common ancestor, and serialize/deserialize. Master preorder, inorder, and level-order first. Morris traversal is a flex for O(1) space.
Trees are the most predictable interview topic. A problem that involves a binary tree is almost always solved by one of ten traversals. Here they are with clean Python, the invariant each one relies on, and the problems where each one appears.
Pattern 1: Preorder (root, left, right)
Visit the node, then recurse left, then recurse right. Useful for serializing a tree and for problems where you process a node before its children.
def preorder(root):
if not root: return []
return [root.val] + preorder(root.left) + preorder(root.right)Pattern 2: Inorder (left, root, right)
On a BST, inorder yields sorted values. This is why BST validation and the k-th smallest in a BST both reduce to inorder.
def inorder(root):
if not root: return []
return inorder(root.left) + [root.val] + inorder(root.right)Pattern 3: Postorder (left, right, root)
Process children before the parent. Useful when the parent’s answer depends on its children: tree height, diameter, path sum where the path can bend at the root.
def height(root):
if not root: return 0
return 1 + max(height(root.left), height(root.right))This is postorder in structure: both children’s heights are computed before the parent combines them.
Pattern 4: Level-order BFS
Queue-based. Produces a list of lists where each inner list is one tree level. Every “right view,” “left view,” or “level average” problem uses this template.
from collections import deque
def level_order(root):
if not root: return []
out = []
q = deque([root])
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
out.append(level)
return outPattern 5: Zigzag level-order
Alternate the direction of each level. Same BFS skeleton with a boolean flag that reverses the level before adding.
def zigzag(root):
if not root: return []
out, q, left_to_right = [], deque([root]), True
while q:
level = deque()
for _ in range(len(q)):
node = q.popleft()
if left_to_right: level.append(node.val)
else: level.appendleft(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
out.append(list(level))
left_to_right = not left_to_right
return outPattern 6: Iterative traversal with explicit stack
Interviewers sometimes ask for an iterative version to test understanding. Here is iterative inorder:
def inorder_iter(root):
out, stack, cur = [], [], root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
out.append(cur.val)
cur = cur.right
return outPattern 7: Morris traversal for O(1) space
Rewires the tree during traversal: temporarily link each node’s predecessor to itself, follow the link back, undo the link. The tree ends unchanged, memory stays constant.
Morris is a flex. If you demonstrate it under pressure, interviewers remember. In production you would almost never use it because the recursive version is clearer.
Pattern 8: Path sum DFS
Count or find all root-to-leaf paths that sum to a target. Recursive DFS passing the remaining sum.
def has_path_sum(root, target):
if not root: return False
if not root.left and not root.right:
return root.val == target
return (has_path_sum(root.left, target - root.val) or
has_path_sum(root.right, target - root.val))Pattern 9: Lowest Common Ancestor
The LCA of two nodes p and q is the deepest node that has both as descendants. For a general binary tree, recurse: if the root is p or q, return it; else recurse left and right, and return the root if both sides return non-null.
def lca(root, p, q):
if not root or root == p or root == q: return root
left = lca(root.left, p, q)
right = lca(root.right, p, q)
if left and right: return root
return left or rightPattern 10: Serialize and deserialize
Encode a tree to a string, decode back. Use preorder with null markers. Deserialize by recursing on an iterator.
def serialize(root):
out = []
def go(n):
if not n: out.append("#"); return
out.append(str(n.val))
go(n.left); go(n.right)
go(root)
return ",".join(out)
def deserialize(s):
it = iter(s.split(","))
def go():
v = next(it)
if v == "#": return None
node = TreeNode(int(v))
node.left = go()
node.right = go()
return node
return go()LeetCode 297. One of the most-asked hard tree problems.
Common pitfalls to avoid
- Checking “if root” when you need “if root is not None”. For a tree where a node’s value can be falsy (0, empty string), the first form silently prunes those nodes.
- Returning the wrong thing from a leaf. Path-sum style problems need to check that root is a leaf (no children) before returning True; otherwise you count mid-tree matches as leaf matches.
- Using BFS with a plain list and pop(0). That is O(n) per pop; use collections.deque for O(1).
- Forgetting to handle null children when adding to a BFS queue. Always check before enqueueing.
- Mixing up preorder, inorder, and postorder when writing iterative versions. Draw a small tree and trace by hand once; the pattern sticks after that.
Practice schedule that works
Week 1: preorder, inorder, postorder, and level-order BFS. Write each from memory daily. Week 2: path sum, tree height, diameter, and lowest common ancestor. Week 3: serialize, deserialize, and one iterative traversal. That covers the interview surface.
When trees get harder
N-ary trees generalize the same patterns; the recursion iterates over a children list instead of left and right. Red-black and AVL trees do not appear in coding interviews but may come up in system design discussions. Segment trees and Fenwick trees are for range-query problems and are a separate study track.
Frequently asked questions
When do I use BFS versus DFS on a tree?
BFS when the answer is level-based: minimum depth, right side view, level averages, zigzag order. DFS when the answer is path-based or depends on subtree structure: tree height, diameter, path sum, LCA.
What is the space complexity of recursive traversal?
O(h) where h is the tree height. Balanced trees have h = log n; skewed trees have h = n. Python recursion also has a default depth limit of 1000. For deep trees, convert to iterative or increase sys.setrecursionlimit.
How do I validate a BST?
Inorder traversal must be strictly increasing. Or pass min and max bounds down each recursion: left subtree must have values less than the root, right subtree greater. The bounds approach is cleaner.
What is Morris traversal good for in production?
Memory-constrained environments like embedded systems. In application code it is rarely worth the complexity. The main production value is pedagogical: understanding Morris builds intuition for in-place algorithms generally.
How do I find all paths from root to leaf?
DFS with a path accumulator. On reaching a leaf, append path.copy() to the result. On backtracking, pop the current value. Classic backtracking pattern applied to trees.
Which pattern is most common in FAANG interviews?
Level-order BFS and path-based DFS. Expect at least one of each across a full loop. Serialize/deserialize is common in senior rounds. LCA is a classic warm-up to a harder tree problem.
Final study approach
Keep a notebook with one tree problem per page, write your solution, then rewrite it a week later. Compare the two solutions for cleaner code. Patterns that stick move to the back of the notebook; patterns that give you trouble stay in rotation. After a month of 20 minutes a day on this routine, tree problems become routine in interviews.
