L22 · Trees I — DFS Traversals

Series: LeetCode — From Basics to Interview-Ready · Session 22 / 65 · Phase 1 · Core patterns

Prerequisites

What this pattern IS

A binary tree is nodes, each holding a value and pointers to a left child and a right child (either may be empty). Depth-first search (DFS) explores it by going as deep as possible down one branch before backtracking — which is exactly what recursion does naturally, because each recursive call dives into a child and the call stack remembers where to resume.

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

The revelation of this session is that preorder, inorder, and postorder are the same recursive walk — visit node, recurse left, recurse right — and differ only in where you place the line that does the work. Do the work before recursing → preorder (root, left, right). Between the two recursions → inorder (left, root, right). After both → postorder (left, right, root). One skeleton, one moved line, three traversals. That's the whole thing, and seeing it collapses three memorised algorithms into one.

Each order has a signature use. Preorder copies or serialises a tree (you see the root before its children, so you can rebuild top-down). Inorder on a binary search tree yields values in sorted order — because a BST puts smaller values left and larger right, so "left, me, right" visits them ascending. Postorder computes things that depend on children first — a subtree's height, whether it's balanced, deleting a tree safely — because you have both children's answers before you handle the node.

Deriving the three orders

The templates — annotated Python

# ---- Template A: the three recursive DFS orders -------------
def preorder(node, out):
    if not node: return               # base case: empty subtree
    out.append(node.val)              # WORK here => preorder (N,L,R)
    preorder(node.left, out)
    preorder(node.right, out)
 
def inorder(node, out):
    if not node: return
    inorder(node.left, out)
    out.append(node.val)              # WORK here => inorder (L,N,R)
    inorder(node.right, out)
 
def postorder(node, out):
    if not node: return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.val)              # WORK here => postorder (L,R,N)
 
 
# ---- Template B: iterative PREORDER (explicit stack) --------
def preorder_iter(root):
    if not root: return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right: stack.append(node.right)   # push right FIRST
        if node.left:  stack.append(node.left)    # so left pops first
    return out
 
 
# ---- Template C: iterative INORDER (go left, then unwind) ---
def inorder_iter(root):
    out, stack, cur = [], [], root
    while cur or stack:
        while cur:                    # dive left, stacking as you go
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()             # leftmost unvisited
        out.append(cur.val)           # visit
        cur = cur.right               # then go right
    return out
 
 
# ---- Template D: the RETURN-vs-UPDATE split (the big one) ---
def max_depth(root):
    if not root: return 0             # base
    l = max_depth(root.left)          # trust: left subtree depth
    r = max_depth(root.right)         # trust: right subtree depth
    return 1 + max(l, r)              # postorder combine
# Many hard problems: RETURN one thing to the parent, UPDATE a
# shared answer with another. See diameter / max-path-sum below.

Two things to lock in. In iterative preorder (B), you push the right child first so the left child pops first — the stack reverses your intended order, so you feed it reversed. And Template D is the shape of essentially every non-trivial tree problem: you do a postorder recursion, and at each node you combine the children's returned values. When "what the parent needs from me" differs from "the global answer this node contributes to", you split them: return one value, update a shared variable with another. That split is the single highest-leverage idea in all of tree algorithms.

Memory / mnemonic

Anchor the three orders with "the ROOT's position names it": pre = Root first, in = Root in the middle, post = Root last — read left-to-right as N-L-R, L-N-R, L-R-N. Say "pre-in-post = root first, middle, last" and the visit line's placement falls out instantly.

Two more pegs. "Inorder + BST = sorted" — memorise it as a fact and it solves a whole class of BST problems (kth smallest, validate BST, range sum) on sight. And for iterative preorder, remember "push RIGHT first so LEFT comes out first" — the stack flips you, so you flip it. For the capstone, chant "RETURN up, UPDATE across": the value you hand your parent goes up, the answer you contribute (a path across through you) updates the shared max.

What interviewers actually ask

Tree DFS is one of the most-asked interview areas because a single traversal skeleton spawns dozens of problems, and the return-vs-update split cleanly separates candidates who understand recursion from those who pattern-match.

• Maximum Depth of Binary Tree (104) · Easy · Amazon, LinkedIn · probes: the postorder combine (1 + max of children) · follow-up: minimum depth, and the iterative BFS version.
• Invert Binary Tree (226) · Easy · Amazon, Google · probes: swap children at every node — trivial recursion, famous for a Google rejection tweet · follow-up: do it iteratively.
• Same Tree (100) / Subtree of Another Tree (572) · Easy · Amazon, Meta · probes: structural recursion comparing two trees in lockstep · follow-up: subtree check reuses same-tree.
• Validate Binary Search Tree (98) · Medium · Amazon, Meta, Microsoft · probes: the trap — check bounds, not just parent vs child · follow-up: do it via inorder and check ascending.
• Kth Smallest Element in a BST (230) · Medium · Amazon, Meta · probes: inorder yields sorted, so stop at the k-th · follow-up: what if the BST is modified often (augment nodes with subtree counts).
• Binary Tree Maximum Path Sum (124) · Hard · Meta, Amazon · probes: the return-vs-update split in full — return the best single downward branch, update a global with left+node+right · follow-up: reconstruct the actual path.

Worked solutions

1. Validate Binary Search Tree (98)

Plain words: is this tree a valid BST — every node greater than all of its left subtree and less than all of its right subtree? The classic bug is checking only node.left.val < node.val < node.right.val, which misses violations deeper down. The fix: pass down the allowed (low, high) range each node must fall within.

def isValidBST(root) -> bool:
    def valid(node, low, high):
        if not node:                       # base: empty is valid
            return True
        if not (low < node.val < high):    # must fit the inherited bounds
            return False
        # left subtree tightens the UPPER bound; right the LOWER
        return valid(node.left,  low, node.val) and \
               valid(node.right, node.val, high)
    return valid(root, float('-inf'), float('inf'))

Complexity: O(n) time, O(h) space (recursion depth). The insight is that the constraint on a node comes from all its ancestors, not just its parent — encoded as a shrinking (low, high) window. Follow-up: an inorder traversal that checks each value exceeds the previous is an equivalent, often cleaner, solution (inorder + BST = sorted).

2. Kth Smallest Element in a BST (230)

Plain words: find the k-th smallest value. Since inorder on a BST emits values ascending, walk inorder and stop at the k-th. The iterative form lets you stop early without traversing the whole tree.

def kthSmallest(root, k: int) -> int:
    stack, cur = [], root
    while cur or stack:
        while cur:                         # dive to the smallest
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()                  # next in sorted order
        k -= 1
        if k == 0:                         # the k-th smallest
            return cur.val
        cur = cur.right
    return -1                              # k out of range (shouldn't happen)

Complexity: O(h + k) time (dive to the smallest, then k steps), O(h) space. This is iterative inorder (Template C) with an early stop — the reason to know the iterative form is exactly this "stop partway" capability that recursion makes awkward. Follow-up: if the tree is modified often, augment each node with its subtree size to answer k-th in O(h).

3. Binary Tree Maximum Path Sum (124)

Plain words: find the maximum sum of any path, where a path is any node-to-node route through connected nodes (it needn't touch the root). This is the return-vs-update split in its purest, hardest form.

def maxPathSum(root) -> int:
    best = float('-inf')
    def gain(node):                        # returns best DOWNWARD branch
        nonlocal best
        if not node:
            return 0
        left  = max(gain(node.left),  0)   # ignore negative branches
        right = max(gain(node.right), 0)
        # UPDATE: path THROUGH this node bends left+node+right
        best = max(best, node.val + left + right)
        # RETURN: parent can only extend ONE branch, not both
        return node.val + max(left, right)
    gain(root)
    return best

Complexity: O(n) time, O(h) space. The crux: a node returns node.val + max(left, right) because its parent can only continue the path through one child, but it updates best with node.val + left + right because the best path might peak at this node using both children. Clamping negatives to 0 means "drop a branch that only hurts". Return-up, update-across — this exact split reappears in diameter (543) and many hard tree problems.

Recursive versus iterative DFS

Where this shows up in production

Tree DFS is everywhere data is nested: the DOM in a browser (rendering, event bubbling), the abstract syntax tree in every compiler and linter (postorder to evaluate expressions, preorder to emit code), file-system walks (os.walk is DFS), JSON/XML parsing and serialisation (preorder to serialise, so you can rebuild top-down), and dependency resolution. Inorder-on-a-BST underlies ordered maps and database index scans that must return keys in sorted order. The honest framing: whenever a structure is recursive, DFS is the natural traversal, and which order you pick is dictated by whether you need parents before children (pre), sorted BST output (in), or children before parents (post).

Practice queue

• Maximum Depth of Binary Tree (104) — the combine; anchor +7d.
• Invert Binary Tree (226) — swap children.
• Same Tree (100) — lockstep recursion.
• Subtree of Another Tree (572) — reuse same-tree.
• Validate Binary Search Tree (98) — inherited bounds; anchor +7d.
• Kth Smallest Element in a BST (230) — inorder early-stop.
• Diameter of Binary Tree (543) — return-vs-update; anchor +21d.
• Binary Tree Maximum Path Sum (124) — the hard capstone.