Tree traversals — DFS and BFS

Almost every tree problem reduces to “visit nodes in some order and accumulate.” Pick the right traversal and most of the work is done.

Setup

from dataclasses import dataclass
from typing import Optional

@dataclass
class TreeNode:
    val: int
    left: Optional["TreeNode"] = None
    right: Optional["TreeNode"] = None

DFS — depth-first, three flavors

def preorder(node):
    if not node: return
    visit(node)              # root
    preorder(node.left)      # left subtree
    preorder(node.right)     # right subtree

def inorder(node):
    if not node: return
    inorder(node.left)       # left
    visit(node)              # root
    inorder(node.right)      # right

def postorder(node):
    if not node: return
    postorder(node.left)
    postorder(node.right)
    visit(node)

• Inorder on a BST yields values in sorted order. Useful for BST validation, k-th smallest.
• Preorder is good for serialization (each node visited before its children).
• Postorder is good when each node’s value depends on its children (computing sums, heights, deletions).

DFS iterative (with explicit stack)

def preorder_iter(root):
    if not root: return []
    stack = [root]
    result = []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right: stack.append(node.right)
        if node.left: stack.append(node.left)
    return result

Push right first so left is processed first (LIFO).

Inorder iterative is trickier:

def inorder_iter(root):
    stack = []
    result = []
    curr = root
    while stack or curr:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right
    return result

BFS — level order

from collections import deque

def level_order(root):
    if not root: return []
    result = []
    q = deque([root])
    while q:
        level_size = len(q)
        level = []
        for _ in range(level_size):
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        result.append(level)
    return result

Snapshotting level_size at the start of each iteration is what separates levels. Without that you can’t tell where one level ends.

Pattern: tree height (postorder)

def height(root):
    if not root: return 0
    return 1 + max(height(root.left), height(root.right))

Each node returns its height; parent uses max of children + 1.

Pattern: diameter of binary tree (longest path between any two nodes)

def diameter(root):
    best = 0
    def height(node):
        nonlocal best
        if not node: return 0
        l = height(node.left)
        r = height(node.right)
        best = max(best, l + r)        # path through this node
        return 1 + max(l, r)
    height(root)
    return best

Single DFS — at each node, the longest path through that node is left_height + right_height.

Pattern: validate BST

def is_bst(root, lo=float("-inf"), hi=float("inf")):
    if not root: return True
    if not (lo < root.val < hi): return False
    return is_bst(root.left, lo, root.val) and is_bst(root.right, root.val, hi)

Common bug: only comparing to immediate parent. A node’s left subtree’s values must be less than ALL ancestors on the right path, not just the immediate parent. The bounds-passing approach handles this.

Pattern: lowest common ancestor (LCA)

def lca(root, p, q):
    if not root or root is p or root is q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root         # p and q in different subtrees
    return left or right

The recursion returns the LCA, or one of the targets if only one is in this subtree. When both calls return non-None, the current node is the LCA.

Pattern: serialize / deserialize

def serialize(root):
    parts = []
    def go(node):
        if not node:
            parts.append("#")
            return
        parts.append(str(node.val))
        go(node.left)
        go(node.right)
    go(root)
    return ",".join(parts)

def deserialize(data):
    it = iter(data.split(","))
    def go():
        val = next(it)
        if val == "#": return None
        node = TreeNode(int(val))
        node.left = go()
        node.right = go()
        return node
    return go()

Preorder with explicit null markers. Deserialize is straightforward DFS using an iterator.

Pitfalls

• Returning True/False from a recursive helper but forgetting to combine the results.
• BST validation comparing only to parent.
• BFS level-aware traversals without snapshotting len(q) per level.
• Stack overflow on deeply skewed trees with recursive DFS — convert to iterative if depth exceeds ~1000.
• Using == to compare BST nodes when you mean structural identity (use is for “same node”).

Interview angle

• “DFS or BFS?” - BFS for shortest path in an unweighted graph or anything level-by-level; DFS for path existence, subtree aggregation, or when recursion mirrors the structure. BFS uses O(width) memory, DFS O(height).
• “Which traversal order for which job?” - in-order gives sorted output on a BST; pre-order suits serialisation and copying; post-order suits deletion and any computation needing children before the parent, such as subtree sums or heights.
• “Recursive or iterative?” - recursive is clearer and usually what you write first. Mention that Python’s default recursion limit is about 1000, so a degenerate tree of 10,000 nodes needs the explicit-stack version.
• “How do you do level-order?” - BFS with a queue, recording the queue length at the start of each level so you know where the level boundary is. That length snapshot is the trick people forget.