Trees I — DFS Traversals

Review boundary and corrected contracts

A tree is acyclic and has no shared child nodes in these examples. BST validation propagates all ancestor bounds; the convention here forbids duplicate keys. BST examples use finite integer keys; kth-smallest assumes 1 ≤ k ≤ node count. Maximum path sum is defined for a nonempty tree and returns one branch upward while considering a two-branch path for the global answer.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Where the theory lives

If the underlying data structure feels shaky, the from-scratch explanation for trees & bsts is in the 6-month plan: S028 — theory.

Learning objective: See preorder, inorder and postorder as ONE recursive skeleton with the work line moved, know why inorder-on-a-BST yields sorted order, write the iterative forms, and master the return-vs-update split used by diameter and maximum-path-sum problems.

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

Prerequisites

What you need first

You need L21 (recursion: base case, the leap of faith, O(depth) stack cost) and L16 (the explicit stack, for the iterative forms). A binary tree is just a node with a value and two child pointers — the same node model as a linked list, but with two nexts. Everything else is built here. This session is the gateway to all of trees (L23–L26).

Optional original companions: Tree traversals — Abdul Bari for visit timing; Recursive and iterative traversal — take U forward for explicit stacks; Diameter — NeetCode for returning height while updating a path answer.

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 supports copying or serialisation when you retain structure, for example null-child markers. Values alone are not enough: a root 1 with left child 2 and a root 1 with right child 2 both have preorder [1,2]. 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.

Reading an org chart

Real: Walk an organisation chart depth-first: dive into a manager's whole team before moving to the next manager. WHEN you note down each person's name — before you look at their reports (preorder), or after you've tallied their whole team (postorder) — changes what you compute, but the walk is identical.

def dfs(node): visit(node); dfs(node.left); dfs(node.right)   # move 'visit' to change the order

Deriving the three orders

Question: Why are preorder, inorder and postorder the same algorithm, and why does inorder on a BST come out sorted?

Premise: Fix a left-before-right DFS convention; each nonempty node contributes its work plus the recursive walks of both subtrees.

Because: left-before-right is our chosen ordering, not a requirement of DFS itself. With that order fixed, moving the node work gives the three named traversals.

Premise: The only freedom is WHEN the 'handle this node' action fires relative to the two recursions.

Because: the two recursions have fixed order (left then right), so the node-visit is the one movable piece.

Premise: Before => preorder (N,L,R); between => inorder (L,N,R); after => postorder (L,R,N).

Because: those are the only three positions the node-visit can occupy.

Premise: In a BST, every left descendant is smaller and every right descendant is larger than the node.

Because: that's the BST ordering invariant.

Premise: So inorder (all-of-left, then node, then all-of-right) emits everything smaller, then the node, then everything larger — recursively — which is ascending order.

Because: the invariant holds at every node, so the emitted sequence is globally sorted.

Conclusion: One skeleton, three visit positions. Inorder + BST = sorted, because 'left, me, right' composes the ordering invariant into a globally ascending sequence.

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 many subtree-aggregation problems: 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.

Name: One walk, movable pen

Picture: You trace the whole tree with your finger (always left before right, diving deep first). Your other hand holds a pen. WHERE along the trace you press the pen — on the way in, in the crook between children, or on the way out — is the only choice, and it names the traversal.

• Same walk every time; move the WORK line to pick pre/in/post.

• Inorder on a BST = sorted output — reach for it whenever a BST wants order.

• Postorder = 'children first', for heights, balance, sums, safe deletion.

• Hard problems: RETURN what the parent needs, UPDATE a shared global with the rest.

Trigger: Any binary tree question: traversal, aggregate over subtrees, path problems, BST order, or 'compute something that depends on children'.

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.

Myth: Preorder, inorder and postorder are three different algorithms you memorise separately.

Truth: They are ONE recursive skeleton with the single work line moved to one of three positions. Learn the skeleton and the position rule, not three separate procedures.

Why: Textbooks present them as a list of three, encouraging rote memorisation of each. That hides the fact that only one line moves, which is why students mix them up under pressure.

Test: Write preorder, then produce inorder by MOVING the append line down one position, then postorder by moving it down once more — without rewriting anything else. If you can, you've internalised the skeleton; if you had to recall three templates, you memorised instead of understood.

What reviewers actually ask

Tree DFS is a useful practice family: one traversal skeleton supports many problems, and the return-vs-update split forces you to distinguish a parent’s input from the overall answer.

• Maximum Depth of Binary Tree (104) · Easy · Practice selection. · probes: the postorder combine (1 + max of children) · follow-up: minimum depth, and the iterative BFS version.
• Invert Binary Tree (226) · Easy · Practice selection. · probes: swap children at every node — a direct structural recursion · follow-up: do it iteratively.
• Same Tree (100) / Subtree of Another Tree (572) · Easy · Practice selection. · probes: structural recursion comparing two trees in lockstep · follow-up: subtree check reuses same-tree.
• Validate Binary Search Tree (98) · Medium · Practice selection. · 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 · Practice selection. · 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 · Practice selection. · 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. Both recursive and iterative inorder can stop early if termination is propagated; the explicit stack makes that control state visible.

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 explicit stack exposes the suspended traversal state directly; a recursive version can also return early if it propagates a found-result flag. 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.

Goal: Solve Diameter of Binary Tree (543) with the same split

Hint: Return the height; update a global with left-height + right-height (edges on the path through the node).

Compute the diameter — the number of edges on the longest path between any two nodes. Reuse Template D's shape: each call returns its height (1 + max of children), and updates a shared max with left_height + right_height (the path bending through this node). Heights count nodes from each child downward; their sum therefore counts edges across the parent.

def diameter(root):
    best = 0
    def height(node):
        nonlocal best
        if node is None:
            return 0
        left, right = height(node.left), height(node.right)
        best = max(best, left + right)
        return 1 + max(left, right)
    height(root)
    return best

An empty tree or a single node has diameter 0; a three-node chain has diameter 2. The best path may lie entirely inside one subtree, so updating only at the root is insufficient. For maximum path sum, initialise best to negative infinity rather than zero: an all-negative tree must return its least-negative node, not an empty path. Both routines visit each node once with O(h) call-frame overhead.

Recursive versus iterative DFS

Decision: Recursive DFS versus iterative (explicit stack) DFS versus BFS for tree problems.

Name: Recursive DFS

Gain: Shortest, clearest code; the visit-position rule makes pre/in/post trivial; natural for combine/return-vs-update.

Cost: O(h) call-frame overhead; a skewed tree can exceed the configured recursion limit. No universal numerical height is safe.

Pick: When the input contract bounds height safely; balanced trees have O(log n) height, arbitrary binary trees can have O(n).

Name: Iterative DFS (explicit stack)

Gain: No recursion-limit risk; lets you stop early mid-traversal (k-th smallest).

Cost: More code, especially inorder/postorder; you manage the stack by hand.

Pick: Very deep/skewed trees, or when you must pause/resume/stop-early a traversal.

Name: BFS (queue, level order)

Gain: Processes by level; needed for level-order and shortest-path-in-unweighted problems.

Cost: O(width) memory (can be O(n) at the widest level); not depth-first.

Pick: Level-order traversal, minimum depth, or anything defined per level (L23).

Verdict: Use recursive DFS when a known height bound fits the runtime; use an explicit stack for unknown or large height. BFS is natural for level output and the first leaf by distance, although either traversal can compute many of the same aggregates. Returning lists adds O(n) output storage beyond the O(h) DFS stack.

Where this shows up in production

DFS is useful for abstract syntax trees, nested documents, and directory hierarchies. Child-first evaluation naturally uses postorder; a preorder serializer must encode child boundaries or null markers to preserve shape. DOM event bubbling follows one ancestor chain, not a full DFS. Dependency graphs may have shared vertices or cycles and need visited/active-state tracking, unlike the tree-only code here. Binary-search-tree inorder explains sorted output for that structure; database B-tree indexes are not generally binary trees.

You can now…

• Write pre/in/post order by moving one work line in a single skeleton.

• Explain why inorder on a BST yields sorted output.

• Pick the right order: pre with structure markers to serialise, in for BST order, post for child-dependent work.

• Write iterative preorder and inorder with an explicit stack.

• Validate a BST with inherited (low, high) bounds, not just parent comparison.

• Find the k-th smallest in a BST by early-stopping an inorder walk.

• Apply the return-vs-update split to diameter and maximum path sum.

Self-check (answer follows each question).

Recall · L22

Q: What's the single difference between pre-, in-, and postorder?

A: The position of the 'visit/work' line relative to the two recursive calls: before (pre, N-L-R), between (in, L-N-R), after (post, L-R-N). Same walk otherwise.

Q: Why does inorder on a BST produce sorted output?

A: A BST puts smaller values left and larger right; inorder emits all-of-left, then the node, then all-of-right, recursively — which is globally ascending.

Q: In iterative preorder, why push the right child before the left?

A: The stack is LIFO, so pushing right first makes left pop (and get visited) first, matching preorder's left-before-right.

Q: What's the trap in validating a BST?

A: Comparing only a node to its immediate parent/children misses deeper violations; you must enforce an inherited (low, high) range from all ancestors.

Q: What is the return-vs-update split?

A: In hard tree problems you RETURN to the parent what the parent can use (e.g. one downward branch / height) but UPDATE a shared global with the full contribution (e.g. left+node+right).

Q: In Maximum Path Sum, why return node.val+max(left,right) but update best with node.val+left+right?

A: A parent can extend the path through only ONE of this node's children (a path can't fork), so you return the single best branch; but the overall best path might peak at this node using BOTH children, so best is updated with the two-sided sum.

Stretch: true

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.

• Pre/in/post = ONE DFS skeleton with the work line in one of three positions (root first/middle/last).

• Inorder on a BST yields sorted output — a fact that solves a whole class of problems.

• Postorder = children-first, for heights, balance, sums, safe deletion.

• Iterative preorder: push right before left; iterative inorder: dive left, unwind, go right.

• Validate a BST with inherited (low, high) bounds, not just parent comparison.

• The return-vs-update split (return up, update across) unlocks diameter and max path sum.

Corrective source notes

• Depth First Search - Algorithms for Competitive Programming — DFS explores a graph through recursive or explicit-stack expansion. Checked 2026-10-07.

• Recursion limits (CPython v3.14.0) — the configured limit is inspectable; raising it too far can crash the process. Rechecked 2026-10-09.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.