Dashboard/Coding patterns/20. Tree Depth-First Search

CODING PATTERNS · LESSON 20 OF 28 · 67 MIN VIDEO · 22 PROBLEMS

Tree Depth-First Search

Module Progress (0 / 22 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (67 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Tree Depth-First Search — How the Pattern Works

Tree Depth-First Search (DFS) explores each root-to-leaf branch to completion before backtracking, using the call stack to pass ancestor state top-down via parameters and aggregate subtree properties bottom-up via return values. At every node u, the recursion maintains the invariant that parameters summarize the exact root-to-u path context while child return values represent fully solved properties of u.left and u.right. By evaluating subtree metrics once in postorder, propagating ancestor bounds in preorder, or combining both in a two-pass rerooting traversal, DFS eliminates redundant subtree scans and reduces O(n^2) recomputation to O(n) time (or O(h) along a guided BST path) with O(h) stack space.

WHEN TO USE THIS PATTERN
  • Optimizing or aggregating over subtrees and paths that may bend at any node (Diameter of Binary Tree, Binary Tree Maximum Path Sum, Lowest Common Ancestor), where each node combines independent bottom-up answers from node.left and node.right in postorder.
  • Enforcing or querying path-dependent constraints from the root (Validate Binary Search Tree, Path Sum, Binary Tree Right Side View), where ancestor bounds, depths, or remaining target budgets flow top-down.
  • Querying ordered keys, ranks, or nearest neighbors in a Binary Search Tree (Inorder Successor in BST, Closest Binary Search Tree Value, Kth Smallest Element in a BST), leveraging BST ordering for an O(h) root-to-leaf walk or early-stopping inorder traversal.
  • Serializing, reconstructing, or rewiring tree topology (Flatten Binary Tree to Linked List, Serialize and Deserialize Binary Tree, Build Binary Tree from Preorder and Inorder Traversal), where traversal order uniquely determines pointer links.
  • Computing answers for every node or under virtual subtree removals (Sum of Distances in a Tree, Height of Binary Tree After Subtree Removal Queries), pairing a bottom-up subtree pass with a top-down complement or rerooting pass.
COMMON INTERVIEW PITFALLS
  • Mixing up node-count height and edge-count height: returning 0 for None assigns leaves height 1 (nodes on downward path), whereas returning -1 for None assigns leaves height 0 (edges on downward path, required when summing depth + height in Subtree Removal Queries).
  • Returning a forked two-sided path to a parent in bending-path problems (Diameter of Binary Tree, Binary Tree Maximum Path Sum): left + node + right is valid only as a candidate peaking at node, whereas the recursive return value to node's parent must extend at most one branch.
  • Validating only immediate parent-child pairs in Validate Binary Search Tree or accepting remaining == 0 at internal nodes in Path Sum: ancestor bounds (low, high) must propagate across all levels, and root-to-leaf checks require not node.left and not node.right.
  • Initializing global maxima to 0 instead of float('-inf') when node values can be negative (Binary Tree Maximum Path Sum), which erroneously prefers an empty path over the least-negative node.
Bottom-Up Postorder Aggregation (Subtree & Bending Paths)When a node's answer or a global optimum depends on solved results from both children (height, diameter, max path sum, LCA).
def postorder_aggregate(root):
    best = 0
    def dfs(node):
        nonlocal best
        if not node:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        best = max(best, left + right)
        return 1 + max(left, right)
    dfs(root)
    return best
Top-Down Preorder Context PropagationWhen each node must be validated or recorded against state accumulated along the path from the root (ancestor intervals, depth, remaining sum).
def preorder_validate(root):
    def dfs(node, low, high):
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return (dfs(node.left, low, node.val) and
                dfs(node.right, node.val, high))
    return dfs(root, float("-inf"), float("inf"))
Iterative BST Guided SearchWhen BST ordering prunes an entire child subtree at each step (inorder successor, closest BST value, key lookup) in O(h) time and O(1) space.
def bst_guided_walk(root, target):
    candidate = None
    node = root
    while node:
        if node.val > target:
            candidate = node
            node = node.left
        else:
            node = node.right
    return candidate
Inorder Traversal with Early TerminationWhen reading BST elements in ascending sorted order up to rank k without materializing or sorting all n values.
def inorder_early_stop(root, k):
    count, ans = 0, None
    def dfs(node):
        nonlocal count, ans
        if not node or ans is not None:
            return
        dfs(node.left)
        count += 1
        ans = node.val if count == k else ans
        dfs(node.right)
    dfs(root)
    return ans
🔒 PRO PROBLEMTarget: O(h) time · O(1) space

12. Inorder Successor in BST

Pattern Trigger: next value in a search tree → walk one path

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

A leaf reports a height of one: one plus the bigger of its two children's heights. So what must an empty child report?