Lesson 10 of 16 Trees and Heaps

Tree DFS and BFS Patterns

Tree DFS and BFS patterns: what each recursive call returns, max depth, binary tree maximum path sum, level order traversal and validating a BST.

45-55 min intermediate 0/16 lessons done
Course contents Lesson 10 of 16 · 0 done
On this page (9 sections)
  1. What you will learn
  2. Signals
  3. DFS: decide what each call returns
  4. BFS: process level by level
  5. Code
  6. Traversal orders
  7. Key takeaways
  8. Exercises
  9. Quiz

What you will learn

  • The one question that solves most tree DFS problems: what does each call return?
  • Level-order BFS with a queue snapshot.
  • Passing bounds down to validate a BST.

Signals

  • Binary tree or n-ary tree input.
  • “Depth”, “path”, “diameter”, “balanced”, “lowest common ancestor” → DFS.
  • “Level”, “right side view”, “zigzag”, “minimum depth” → BFS.

DFS: decide what each call returns

Write the function for one node, assuming the recursive calls on children already return correct answers. Then combine. Sometimes the value you return differs from the value you track globally: in maximum path sum, a call returns the best path going down from the node, while the global best may bend through the node using both children.

BFS: process level by level

Use a queue; at the start of each level, take len(q) as the number of nodes on this level. That snapshot is how you separate levels without storing depths.

Code

"""Tree DFS and BFS: depth, path sums, level order, validating a BST."""
from collections import deque


class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def from_list(values):
    """Build a tree from level-order values with None for gaps (LeetCode style)."""
    if not values:
        return None
    it = iter(values)
    root = TreeNode(next(it))
    q = deque([root])
    for left in it:
        node = q.popleft()
        right = next(it, None)
        if left is not None:
            node.left = TreeNode(left)
            q.append(node.left)
        if right is not None:
            node.right = TreeNode(right)
            q.append(node.right)
    return root


def max_depth(node):
    if node is None:
        return 0
    return 1 + max(max_depth(node.left), max_depth(node.right))


def max_path_sum(root):
    best = float("-inf")

    def gain(node):  # best downward path starting at node
        nonlocal best
        if node is None:
            return 0
        left, right = max(gain(node.left), 0), max(gain(node.right), 0)
        best = max(best, node.val + left + right)  # path that bends at this node
        return node.val + max(left, right)

    gain(root)
    return best


def level_order(root):
    out, q = [], deque([root] if root else [])
    while q:
        level = []
        for _ in range(len(q)):  # snapshot: exactly this level's nodes
            node = q.popleft()
            level.append(node.val)
            q.extend(c for c in (node.left, node.right) if c)
        out.append(level)
    return out


def is_valid_bst(node, lo=float("-inf"), hi=float("inf")):
    if node is None:
        return True
    if not lo < node.val < hi:
        return False
    return is_valid_bst(node.left, lo, node.val) and is_valid_bst(node.right, node.val, hi)


if __name__ == "__main__":
    t = from_list([-10, 9, 20, None, None, 15, 7])
    print(max_depth(t), max_path_sum(t), level_order(t))
    print(is_valid_bst(from_list([5, 1, 8, None, None, 6, 9])), is_valid_bst(from_list([5, 1, 8, None, None, 3, 9])))

Output:

3 42 [[-10], [9, 20], [15, 7]]
True False
  • max_path_sum is 42: the path 15 → 20 → 7. Negative child gains are clipped to 0 (“don’t take that branch”).
  • is_valid_bst passes the allowed (lo, hi) range down. The second tree fails because 3 is in the right subtree of 5, even though it’s a valid left child of 8. Checking only parent-child pairs misses this, which is the classic bug.
  • from_list builds trees from LeetCode-style arrays so you can test quickly.

Traversal orders

  • Pre-order (node, left, right): copy or serialise a tree.
  • In-order (left, node, right): sorted order of a BST; k-th smallest.
  • Post-order (left, right, node): when the parent needs children’s results first (heights, path sums, deletes).

Recursion depth equals tree height; for very deep (skewed) trees, use an explicit stack or raise Python’s recursion limit.

Practise: tree DFS, tree BFS and BST problems.

Key takeaways

  • For DFS, define what a call returns for one node, trust the recursion for children, combine.
  • Track a global answer separately when it can bend through a node.
  • BFS by level: snapshot the queue size at the start of each level.
  • Validate a BST with bounds passed down, not parent-child comparisons.

Exercises

  1. Diameter of a binary tree (longest path between any two nodes).
  2. Right side view using BFS (last node of each level).
  3. Lowest common ancestor of two nodes in a binary tree.

Quiz

  1. In max_path_sum, why does gain return node.val + max(left, right) instead of both sides?
  2. How does BFS know where one level ends?
  3. Why does checking left.val < node.val < right.val fail to validate a BST?
Show answers
  1. A path continuing up to the parent can use only one branch; the bending path using both is recorded in best but can’t be extended.
  2. It records the queue length at the start of the level and pops exactly that many nodes.
  3. It only checks direct children; a deeper node can still violate an ancestor’s bound (like 3 under 5’s right subtree).

Finished this lesson?

Mark it complete to track your progress (saved in this browser).