Trees: DFS & BFS cheatsheet

🌳 Trees: DFS & BFS

Each call answers one question about one subtree: base case on None, trust the children, combine.

Recognize the pattern

Anything computed from both subtrees (height, size, balanced?, same?) → recursive DFS that returns the answer up (post-order)
Answer depends on the path from the root (running sum, depth, max so far) → pass state down as parameters (pre-order)
Best path may bend at any node (diameter, max path sum) → return the one-sided value, track the global best with nonlocal
"Level", "row", "right side view", "closest to the root" → BFS with a deque, one level per round
BST: search/insert/LCA → walk one direction per node, O(h); "sorted" or "k-th smallest" → in-order traversal
Validate a BST → pass an allowed (low, high) range down, not just parent vs child
Very deep (chain-like) trees → iterative DFS with an explicit stack

Level-order notation

[3, 9, 20, None, None, 15, 7] is read row by row, left to right; None is a missing child, children of None are not listed, trailing Nones are dropped.

DFS: return the answer up

Python template

def height(node: Optional[TreeNode]) -> int:
    if node is None:          # base case: empty tree
        return 0
    left = height(node.left)  # trust the recursion
    right = height(node.right)
    return 1 + max(left, right)  # combine

DFS: pass state down

Python template

def has_path_sum(node: Optional[TreeNode],
                 target: int) -> bool:
    if node is None:
        return False
    target -= node.val        # state flows down
    if node.left is None and node.right is None:
        return target == 0    # leaf: check the path
    return (has_path_sum(node.left, target)
            or has_path_sum(node.right, target))

Return one thing, track the best of another

Python template

def diameter(root: Optional[TreeNode]) -> int:
    best = 0

    def height(node: Optional[TreeNode]) -> int:
        nonlocal best
        if node is None:
            return 0
        left, right = height(node.left), height(node.right)
        best = max(best, left + right)  # bends here
        return 1 + max(left, right)     # parent extends

    height(root)
    return best

BFS level by level

Python template

from collections import deque

def level_order(root: Optional[TreeNode]) -> List[List[int]]:
    if root is None:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):  # one level
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

BST: validate & iterative in-order

Python template

import math

def is_bst(node, low=-math.inf, high=math.inf) -> bool:
    if node is None:
        return True
    if not low < node.val < high:
        return False
    return (is_bst(node.left, low, node.val)
            and is_bst(node.right, node.val, high))

def inorder(root: Optional[TreeNode]) -> List[int]:
    out, stack, node = [], [], root
    while stack or node:
        while node:              # dive left
            stack.append(node)
            node = node.left
        node = stack.pop()       # next smallest
        out.append(node.val)
        node = node.right
    return out

Operation costs

Operation	Time	Space
DFS / BFS over the whole tree	O(n)	O(h) DFS, O(w) BFS
Height h: balanced vs skewed	O(log n) vs O(n)	—
BST search / insert / delete	O(h)	O(1) iterative
BST in-order (sorted output)	O(n)	O(h)
k-th smallest in a BST	O(h + k)	O(h)

Watch for

Forgetting the node is None base case (AttributeError: 'NoneType' has no attribute 'val').
Validating a BST by comparing each node only with its children: every node must fit the (low, high) range set by all its ancestors.
BFS without snapshotting len(queue): levels bleed into each other.
Max path sum / diameter: initialising the best to 0 when all values can be negative; use -math.inf or the root value.
Testing if node.val: instead of if node: (a node with value 0 is still a node).
Passing a shared list down (the current path) without popping after the recursive calls, so branches leak into each other.