Trees & BSTs — Traversal (BFS/DFS)

Review boundary and corrected contracts

A distinct-key unbalanced BST has O(h) search, not unconditional O(log n). Returned traversal storage is O(n) in addition to O(h) recursion. The height example counts nodes; balance and duplicate policy are explicit. LCA requires both keys to exist.

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.

Learning objective: Walk any tree three ways (DFS pre/in/post, BFS), operate on a BST in O(h) time (expected O(log n) under uniformly random distinct-key insertion order), and know why real databases + filesystems use B-trees instead of BSTs.

Why this session exists

Trees model hierarchy in file directories, DOM nodes, syntax and decisions. Git commits form a DAG rather than a tree when histories merge; family relationships can also require a graph. A binary search tree adds ordering: lookup, insert and delete take O(h), where h is height. Uniformly random insertion permutations of distinct keys give expected logarithmic height; arbitrary application input does not supply that randomness. This session teaches the four traversal orders you'll use forever (pre, in, post, level), the classic BST operations, and the moment where balance stops being optional. Trees are also the recursive shape that makes recursion (S027) click — the code you write literally mirrors the definition.

You will be able to

• Build a binary tree in Python and traverse it four ways (pre-order, in-order, post-order, level-order).

• Insert into and search a BST in O(h), state the random-order assumption behind expected O(log n), and explain the O(n) worst case without balancing.

• Compute tree height and validate ‘is this a valid BST?’ with one recursion each.

• Distinguish binary tree ↔ BST ↔ balanced BST ↔ B-tree, and name the right tool for each real system.

• Write BFS iteratively with a deque (this is your gateway to graph traversal in S030).

Prerequisites

• S027 · Recursion — tree code is recursion in its purest form.
• S026 · Stacks & Queues — BFS uses a queue, iterative DFS uses a stack.
• S024 · Hashmaps — compare exact-key lookup with ordered tree queries; a standard LRU cache instead combines a hash map with a linked list.

Pre-read · skim before the session (25 min total)

Further reading: LeetCode · Tree Explore Card

Further reading: AVL Tree (Wikipedia)

Further reading: The Tree — from ‘Use The Index, Luke’

Optional archived videos

These original resource pointers are retained as optional practice aids, not governing evidence for technical claims.

• Binary Search Tree · MIT 6.006 — archived title/attribution; playback, duration and channel identity not independently verified in this review.
• BFS + DFS · Neetcode walkthrough — archived title/attribution; playback, duration and channel identity not independently verified in this review.
• B-Tree vs BST — Databases 101 — archived title/attribution; playback, duration and channel identity not independently verified in this review.

(a) Intuition · 5 min

A tree is an org chart that also tells you where to find people fast

Real: Think of an ordered filing cabinet where each drawer has TWO sub-drawers: ‘names A–M’ on the left, ‘N–Z’ on the right. Each sub-drawer splits its range again. To find ‘Nakamura’, you make one decision at each drawer — go left or right — and, with logarithmic height, reach the file in O(log n) steps. That's a binary search tree. Every node partitions the remaining keys into smaller and larger keys, not necessarily equally sized sets. But: if you always insert names alphabetically, the tree becomes a straight line — every ‘drawer’ has an empty left side. Now a worst-case lookup takes n steps. Balance is not a nice-to-have; it's the entire point.

 
    A binary tree is empty or a node with at most two children (each itself a subtree). A binary search tree adds the invariant: for every node, all values in the left subtree are smaller, all values in the right subtree are larger. Lookup = walk down while comparing. Insert = walk down, hang a new leaf.
    Traversal comes in four flavours: DFS in three orders (pre-order = root before children, in-order = left, root, right, post-order = children before root), and BFS = level by level. Different problems need different orders — memorise the four and pick the fit.
  

Four orders, four purposes

When to use each traversal

• Pre-order (root → left → right) — good for cloning a tree, serialising it, evaluating prefix expressions.

• In-order (left → root → right) — on a BST, yields values in sorted order. Use for ‘print in order’ or ‘k-th smallest’.

• Post-order (left → right → root) — process children before parent. Used for computing tree sizes, freeing memory, evaluating postfix expressions.

• Level-order / BFS (top-down, level by level) — use for shortest path in a tree, right-view / left-view problems, tree width.

An unbalanced BST is a linked list wearing a hat

Insert 1, 2, 3, 4, 5 into a plain BST in order → every node's left child is None, right child is the next number. Now every ‘search’ is O(n). Use a balancing guarantee when worst-case height matters: Java TreeMap uses a red-black tree. Do not classify every ordered container as a BST: Python SortedContainers uses sorted sublists. Splay trees provide amortised bounds, not logarithmic worst-case time for each operation.

Timeline — the family of trees

The useful historical progression is a change of invariant, not a claim that every product shares one implementation: ordinary BST ordering → AVL local height balance → red-black colour/black-height balance → wider B-tree pages → splay access-adaptation → LSM sorted runs and merging. AVL and red-black trees bound height; splay trees instead amortise work over a sequence. B-trees reduce page levels; LSM designs trade background merge work for buffered writes. No product adoption date is needed for these distinctions.

(b) Visit every node, or rule out a subtree · 15 min

Traversal and search use the same links for different jobs. A traversal must account for every node in the required order; a BST lookup uses key comparisons to avoid visiting entire subtrees. Keep those jobs separate as you read the two trees.

A tree and its four traversals

Use the left and right positions to follow each traversal, not the numerical order of the labels. This is a binary tree, not a binary search tree: the values name the nodes without satisfying the BST ordering rule.

In-order reaches 4 before 2 and 1, so its output is not sorted for this tree. Compare that sequence with the other three below: the structure stays fixed while the time at which a node is emitted changes.

Name: Pre-order

Tagline: root → left → right

• 1, 2, 4, 5, 3, 6, 7

• Copy / serialise a tree

• Prefix expression eval

Name: In-order

Tagline: left → root → right

• 4, 2, 5, 1, 6, 3, 7

• On BST → sorted output

• K-th smallest via early stop

Name: Post-order

Tagline: left → right → root

• 4, 5, 2, 6, 7, 3, 1

• Compute size / height

• Delete tree bottom-up

Name: Level-order (BFS)

Tagline: row by row

• 1, 2, 3, 4, 5, 6, 7

• Right-view / left-view

• Tree width, level averages

BST search — one decision per level

Now the keys do satisfy the search-tree invariant. To find 40, start at 50 and discard its right subtree; at 30, take the right link highlighted in the diagram. Unlike traversal, lookup needs only one path.

The lookup visits 50, 30, then 40; neither the subtree rooted at 70 nor the leaf 20 needs to be searched. A comparison discards one side, but only balance keeps that reduction substantial. Search cost = tree height. Balanced BST → O(log n). Degenerate BST → O(n).

Balanced vs unbalanced — the difference is life or death

What ‘balanced’ actually means

Name: Perfectly balanced

Desc: A perfect binary tree has two children at every internal node and all leaves at one depth. With node-count height h, n = 2^h − 1, so h = log₂(n+1). A complete tree fills levels left to right and has height floor(log₂ n)+1 for n > 0; empty height is 0.

Name: Height-balanced (AVL)

Desc: For every node, left subtree height and right subtree height differ by at most 1. Guaranteed O(log n). Updates check balance and rotate when needed, not on every update.

Name: Colour-balanced (Red-Black)

Desc: Equal black-height on root-to-null paths and no adjacent red nodes imply logarithmic height. A logarithmic bound holds under either edge-count or node-count height; specify the convention before comparing exact heights. Rotation and write costs depend on the implementation and workload; red-black is not a subtree-weight-balance rule.

Name: B-tree

Desc: An internal node with k keys has k+1 children; leaves have no children and occupancy varies within defined bounds. High fan-out can make a large index shallow. Page size, key width, occupancy and caching determine the actual height and I/O, not a universal K=100.

Name: Degenerate

Desc: Height = n. Effectively a linked list. What strictly increasing distinct-key insertion produces in this plain BST; repeated equal keys are ignored.

Why databases use B-trees, not BSTs

Balance limits the number of decisions. When a decision requires reading a disk page, widening each node can reduce the number of page reads too. The next steps apply the height argument to storage rather than just in-memory comparisons.

Count page reads before multiplying by latency

A balanced binary tree with a billion keys has about 30 levels. A multiway tree with effective fan-out 100 has a logarithmic depth scale log₁₀₀(10⁹)=4.5, roughly five levels; exact counts depend on occupancy and leaf capacity. If each level required one uncached read costing an illustrative 10 ms, 30 versus 5 reads would cost 300 versus 50 ms. This is arithmetic under an assumption, not a measured p99, hardware constant or sixfold production guarantee. Cached upper levels and SSD storage change the result.

Wider nodes match storage pages

A B-tree or B+tree groups many keys into each page. Page sizes are implementation-dependent; SQLite supports powers of two from 512 through 65,536 bytes. B+tree-style leaf links also support ordered range scans without restarting lookup for each key.

B-tree is a common index type, not every SQL index

PostgreSQL offers B-tree, Hash, GiST, SP-GiST, GIN and BRIN indexes. B-tree is its default and supports equality and ordered comparisons. An index range query returning r rows requires Ω(r) output work; index access is not an O(log n) guarantee for an entire query.

The BST-in-your-head model to hold

Every node is a decision. Each comparison discards one subtree; it need not discard half the keys. If the tree has logarithmic height, O(log n) decisions get you home. If it's not, you're just doing a linear scan through a fancy pointer maze. Balance = performance.

Both example trees were drawn with short paths. Before implementing lookup, test the assumption hidden by that convenient shape: what happens when insertion order produces a chain instead?

Myth: "A binary search tree gives O(log n) lookup. That's what a BST is for."

Truth: A plain BST gives O(h) lookup, where h is the height. O(log n) only holds if the tree is balanced, and nothing in the BST insert algorithm enforces that. Insert already-sorted data and you build a linked list with extra pointers — O(n) lookup, worst case, silently.

Why: Because every diagram you were shown was balanced, and every practice dataset was inserted in random order — and random insertion order does give expected O(log n) height. Timestamps and increasing IDs are examples of non-random insertion orders that can produce a chain. Do not assume that a particular workload follows a uniform random permutation.

Test: Sorted input degenerates the tree. Run this bounded standalone witness rather than inserting 1,000 keys recursively near the interpreter limit:

import random
 
class DemoNode:
    def __init__(self, value):
        self.value, self.left, self.right = value, None, None
 
def demo_insert(node, value):
    if node is None:
        return DemoNode(value)
    if value < node.value:
        node.left = demo_insert(node.left, value)
    elif value > node.value:
        node.right = demo_insert(node.right, value)
    return node
 
def demo_height(node):
    return 0 if node is None else 1 + max(demo_height(node.left), demo_height(node.right))
 
values = list(range(60))
ordered = shuffled = None
for value in values:
    ordered = demo_insert(ordered, value)
random.Random(28).shuffle(values)
for value in values:
    shuffled = demo_insert(shuffled, value)
assert demo_height(ordered) == 60
print(demo_height(ordered), demo_height(shuffled))

The shuffled run is one reproducible example, not a proof of expected height. Both trees contain exactly the same distinct keys.

Question: Why is an in-order traversal of a BST guaranteed to emit values in sorted order? This is usually stated as a fact to memorise. It is a two-line proof.

Premise: The BST invariant says: for every node, all keys in its left subtree are less than it, and all keys in its right subtree are greater.

Because: that invariant is the entire definition of a BST — it is what makes search able to discard one whole subtree at each step

Premise: The invariant is stated recursively: it holds at every node, so each subtree is itself a valid BST.

Because: the rule quantifies over all descendants in each subtree, not just the two child values

Premise: In-order traversal is defined as: visit left subtree fully, then the node, then the right subtree fully.

Because: that is the only ordering that respects "everything smaller, then me, then everything larger"

Premise: By induction, if the left traversal emits its keys sorted and all are less than the node, and the right emits sorted and all greater, then concatenating them around the node is sorted.

Because: concatenating a sorted run, a value above all of it, and a sorted run above that value, yields one sorted run

Conclusion: Therefore in-order traversal is sorted output, and it costs O(n) with no key-to-key comparisons during traversal — the sorting work was paid at insert time. And note what this predicts: a BST is an incremental sort. Building one from n items costs O(n log n) if balanced, then traversal is O(n) — exactly the cost of a comparison sort, which is no coincidence. It also predicts the cleanest BST validity check: run an in-order traversal and assert it is strictly increasing. That is O(n) and catches every violation, whereas the naive "check each node against its two children" check is wrong and passes invalid trees.

Name: Twenty questions on a number line

Picture: A BST is the game of twenty questions, frozen into a structure. Every node is a question — "is your value above or below me?" — and every answer throws away one whole side of the remaining range. The power comes entirely from how much each question discards. A logarithmic-height balanced tree bounds the number of questions by O(log n); it need not discard exactly half at each step. A degenerate tree discards one item per question, so it takes n. Same code, same invariant; the only variable is how good the questions are.

• Cost is O(height), never O(log n) by right. Balance is what converts one into the other.

• In-order = sorted. Pre-order plus null markers = serialise/rebuild arbitrary binary-tree shape. Post-order = free children before parent (delete, evaluate expressions).

• An ordered tree supports range scans and predecessor/successor without sorting all keys. A hash map can still answer min/max by scanning and top-k by combining counts with a heap; Python dict iteration preserves insertion order, not key order.

• Self-balancing variants (red-black, AVL) do extra work on write to guarantee the height bound on read. The guarantee is bought, not free.

Trigger: Fire this model the moment you see: a range query ("all events between two timestamps") · "nearest value below X" · an ordered iteration requirement · a database index (B-trees are this idea widened for disk) · an interval or scheduling problem · anything where a hash map almost works but you also need sorting.

Decision: You need keyed lookup over a large collection. Hash map, self-balancing BST, or a sorted array?

Name: Hash map

Gain: expected O(1) table work for point operations under suitable hashing and load control; key hashing/equality and resizing have their own costs

Cost: no key-sorted index: range/min/max/successor require extra work or another structure; worst-case lookup can be O(n); resize can cause latency spikes; keys must be hashable

Pick: every query is an exact-match point lookup and you will never need order — the common case for joins, dedup and caches

Name: Self-balancing BST

Gain: O(log n) worst-case structural work for point lookup, insert, delete and successor; range reporting costs O(log n + r) for r returned keys, and full sorted iteration O(n). This is not a wall-clock latency guarantee

Cost: pointer chasing and rotations introduce overhead; constants and locality depend on the representation and workload

Pick: you need ordered operations or a worst-case operation-count bound rather than an expected one; wall-clock latency also depends on allocation and scheduling

Name: Sorted array + binary search

Gain: contiguous array storage often improves locality; O(log n) binary search and O(log n+r) range reporting for r results, with representation-dependent overhead

Cost: insert and delete are O(n) because everything shifts; often attractive for read-heavy data or batch rebuilding, though updates remain possible

Pick: the data is static or rebuilt in bulk — when that workload permits sorting/rebuilding; analytical formats and indexes use multiple strategies

Verdict: Ask one question first: do I need order? If no, hash map, and stop. If yes, ask the second question: does the data change after it is built? If no, consider a sorted array for simplicity and locality rather than assuming a tree wins. Order plus mutation is a strong reason to consider a balanced tree, not a universal winner. Storage engines may use B-trees (multiway page trees), LSM designs (sorted runs plus background merging), hashes and other indexes. B-tree and LSM designs both address ordered mutable data, with different I/O, caching and write tradeoffs.

(c) Hands-on · 25 min

Save as trees.py. Zero dependencies beyond stdlib.

"""trees.py — build a BST, traverse 4 ways, validate, and find k-th smallest.
 
Run:  python trees.py
"""
from __future__ import annotations
from collections import deque
from typing import Optional
 
 
class Node:
    __slots__ = ("val", "left", "right")
 
    def __init__(self, val: int, left: "Node | None" = None, right: "Node | None" = None):
        self.val = val
        self.left = left
        self.right = right
 
 
# ------------------------------------------------------------------
# 1) BST insert + search
# ------------------------------------------------------------------
def bst_insert(root: Node | None, val: int) -> Node:
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = bst_insert(root.left, val)
    elif val > root.val:
        root.right = bst_insert(root.right, val)
    # duplicates: silently ignored
    return root
 
 
def bst_search(root: Node | None, val: int) -> bool:
    node = root
    while node:
        if val == node.val:
            return True
        node = node.left if val < node.val else node.right
    return False
 
 
# ------------------------------------------------------------------
# 2) The four traversals
# ------------------------------------------------------------------
def pre_order(root: Node | None, out: list[int] | None = None) -> list[int]:
    out = out if out is not None else []
    if root:
        out.append(root.val)
        pre_order(root.left, out)
        pre_order(root.right, out)
    return out
 
 
def in_order(root: Node | None, out: list[int] | None = None) -> list[int]:
    out = out if out is not None else []
    if root:
        in_order(root.left, out)
        out.append(root.val)
        in_order(root.right, out)
    return out
 
 
def post_order(root: Node | None, out: list[int] | None = None) -> list[int]:
    out = out if out is not None else []
    if root:
        post_order(root.left, out)
        post_order(root.right, out)
        out.append(root.val)
    return out
 
 
def level_order(root: Node | None) -> list[list[int]]:
    """BFS, grouping values by level."""
    if not root:
        return []
    levels: list[list[int]] = []
    q: deque[Node] = deque([root])
    while q:
        level = []
        for _ in range(len(q)):                      # snapshot the current level size
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        levels.append(level)
    return levels
 
 
# ------------------------------------------------------------------
# 3) Tree properties — height, size, is-BST
# ------------------------------------------------------------------
def height(root: Node | None) -> int:
    if root is None:
        return 0
    return 1 + max(height(root.left), height(root.right))
 
 
def size(root: Node | None) -> int:
    if root is None:
        return 0
    return 1 + size(root.left) + size(root.right)
 
 
def is_valid_bst(root: Node | None, low: float = float("-inf"), high: float = float("inf")) -> bool:
    """Every node must lie strictly in (low, high). Recurse tightening the bounds."""
    if root is None:
        return True
    if not (low < root.val < high):
        return False
    return is_valid_bst(root.left, low, root.val) and is_valid_bst(root.right, root.val, high)
 
 
# ------------------------------------------------------------------
# 4) k-th smallest — leverage in-order + early stop
# ------------------------------------------------------------------
def kth_smallest(root: Node | None, k: int) -> Optional[int]:
    """O(h+k) for integer 1 <= k <= size; otherwise None in O(n)."""
    stack: list[Node] = []
    node = root
    count = 0
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        count += 1
        if count == k:
            return node.val
        node = node.right
    return None
 
 
# ------------------------------------------------------------------
# 5) Build a plain, unbalanced BST from an insertion sequence
# ------------------------------------------------------------------
def build_bst_from(values: list[int]) -> Node | None:
    root: Node | None = None
    for v in values:
        root = bst_insert(root, v)
    return root
 
 
if __name__ == "__main__":
    # Build the tree:
    #         50
    #        /  \
    #      30    70
    #     / \   / \
    #   20  40 60 80
    root = build_bst_from([50, 30, 70, 20, 40, 60, 80])
 
    print("pre_order :", pre_order(root))
    print("in_order  :", in_order(root))            # sorted for a valid BST
    print("post_order:", post_order(root))
    print("level_order:", level_order(root))
    print("height    :", height(root))              # 3
    print("size      :", size(root))                # 7
    print("is_valid_bst :", is_valid_bst(root))     # True
    print("kth_smallest k=3 :", kth_smallest(root, 3))   # 40
    print("bst_search 60 :", bst_search(root, 60))
    print("bst_search 65 :", bst_search(root, 65))
 
    # Demonstrate the balance problem — insert sorted data
    bad = build_bst_from([1, 2, 3, 4, 5, 6, 7])
    print(f"height of BAD tree from sorted input : {height(bad)}  (should be ~3, actually 7 — a linked list)")

Anatomy of the script

What each function teaches

Name: bst_insert

Desc: Classic recursive insert. The BST invariant (left < root < right) is enforced by the choice of which subtree to descend into.

Name: bst_search (iterative)

Desc: Same walking logic, but iterative. This version avoids recursive search frames; insertion and other recursive helpers still depend on tree height.

Name: pre/in/post_order

Desc: Same three lines in different orders — just move the append relative to the recursive calls. Memorise the pattern.

Name: level_order

Desc: BFS using a deque. The for _ in range(len(q)) trick captures the current level size — a common LeetCode technique.

Name: is_valid_bst

Desc: The recursion tightens the (low, high) bounds as it descends. Checking only left.val < root.val < right.val is WRONG — a distant descendant could violate the invariant.

Name: kth_smallest

Desc: Iterative in-order traversal — the loop with left-spine descent is a classic template. Early-stop when count == k → O(h + k).

Name: ‘bad’ tree

Desc: Inserting sorted data into an unbalanced BST produces a linked list. Self-balancing variants prevent that height growth; this teaching implementation deliberately does not.

What to observe when you run it

in_order returns [20, 30, 40, 50, 60, 70, 80] — sorted, because valid BST. level_order returns [[50], [30, 70], [20, 40, 60, 80]] — perfect tree, 3 levels. height = 3, size = 7. kth_smallest(k=3) = 40 (third in sorted order). bst_search(60) = True; bst_search(65) = False. height of the ‘bad’ tree from sorted [1..7] = 7, not 3 — proving the degenerate case is real.

Goal: Write ‘lowest common ancestor of two nodes in a BST’ using the ordering invariant

Hint: If both target values are less than the current node → answer is in the left subtree. If both greater → right. Otherwise (targets are on opposite sides, or one equals the current node) → the current node IS the LCA. Iterative solution is O(h).

def lca_bst(root: Node | None, p: int, q: int) -> Node | None:
    node = root
    while node:
        if p < node.val and q < node.val:
            node = node.left
        elif p > node.val and q > node.val:
            node = node.right
        else:
            return node
    return None
 
# On the earlier balanced tree:
print(lca_bst(root, 20, 40).val)   # 30
print(lca_bst(root, 20, 60).val)   # 50 (root)

Exercise answer: 20 and 40 split at the existing node 30; 20 and 60 split at the existing root 50. The return value is that node object, not a clone. Both target keys must exist in this distinct-key BST, including the p=q case. Missing keys are outside the contract: for example, 25 and 40 can return 30 even though 25 is absent; call bst_search first when existence is not guaranteed.

Contracts, identity and total storage

These functions accept a finite, acyclic binary tree with no shared child nodes; following arbitrary object links can revisit a shared node or recurse forever on a cycle. Node identity and equal values are different: two separate nodes may hold the same integer in an ordinary binary tree. The BST uses strict distinct-key ordering; repeated insertion returns the original root without allocating another node. It mutates links in place. Do not use the sorted-value list alone as a test for identical tree shape.

The traversal helpers append into a caller-supplied out list and return that same list. They emit values, not copies of nodes. Full traversals, size and height cost O(n); recursive auxiliary space is O(h), plus O(n) returned traversal values. Level-order costs O(n) time, O(w) queue space for maximum width w and O(n) output. Search is O(h) time and O(1) auxiliary space; recursive insert uses O(h) frames. Building n sorted distinct keys takes Θ(n²) total work. kth_smallest uses O(h) auxiliary space and O(h+k) time for 1 ≤ k ≤ n; invalid integer ranks return None after up to O(n) work. The validator's bounds are inherited ancestor constraints, so Node(10, Node(5, None, Node(12))) must fail even though every immediate child comparison passes. Large Python integers retain exact comparisons here; arithmetic/bit costs are not being treated as measured constant latency.

(d) Production reality · 15 min

Index plans: inspect the work, not just the tree label

An index on users(email) is useful when the predicate can use its operator ordering and returns a selective subset. Inspect PostgreSQL EXPLAIN for index conditions, filters, estimates and row counts: a sequential scan may be appropriate when much of the table is needed. EXPLAIN ANALYZE actually runs the statement, so use a safe read-only workload and do not casually run it on mutating production SQL. This session does not execute a database or certify any latency.

DOM structure is not the React work tree

The DOM is a node tree, and event propagation follows ancestor paths. React's rendering/reconciliation work is related but not identical to that DOM tree; Fiber supports splitting and scheduling work. There is no rule that every render traverses every DOM node exactly twice, or that nested markup alone determines update cost. Diagnose the actual update and profiled work rather than inferring it from a tree diagram.

User-controlled depth needs a resource policy

A recursive comparator can exhaust the interpreter recursion budget on a deep chain even when it works on wide shallow fixtures. An explicit stack avoids recursive call depth, but still consumes memory and time. Bound node count/depth for untrusted inputs; neither raising the recursion limit nor replacing recursion with a loop makes arbitrary data safe. See the executable structural comparator below for correct empty/shape/value cases, not a hardened parser.

Where this shows up in the rest of the plan

Root: Trees are the shape of half of computing

Label: S029 · Heaps & Priority Queues

Desc: A binary heap IS a complete binary tree stored in an array.

Label: S030 · Graphs

Desc: A finite undirected tree is connected and acyclic; an acyclic disconnected graph is a forest. Child-only tree traversal generalises to graph traversal by tracking discovery.

Label: S036 · SQL Basics

Desc: B-tree is one important SQL index; query plans organise operators as trees or DAGs, not universally as one index walk.

Label: Further connection · JSON and parsing

Desc: JSON parsing is tree construction. Regex ASTs are trees.

Label: Further connection · Redis sorted sets

Desc: Large Redis sorted sets can use a skip list plus a hash table; compact encodings are also possible. Ordered access does not imply a binary tree.

Label: Further connection · Merkle trees and Git

Desc: Git commits form a DAG. A balanced binary Merkle tree has logarithmic-size inclusion proofs; verification also hashes the supplied leaf/path data. Not every Git operation has that cost.

(e) Recall + stretch · 10 min

Self-check (answer follows each question).

Recall — questions and worked answers

Q: State the BST invariant in one sentence.

A: For every node, all values in its left subtree are strictly less than its value, and all values in its right subtree are strictly greater.

Q: What are the four traversal orders and one use for each?

A: Pre-order (root → L → R): cloning / serialising. In-order (L → root → R): sorted output for a BST. Post-order (L → R → root): compute sizes / free memory bottom-up. Level-order / BFS: right/left view, shortest edges from root.

Q: Why is BST search O(log n) on average but O(n) worst case?

A: Uniformly random permutations of distinct insertions give expected O(log n) search/height; merely saying average does not establish that model. Sorted distinct insertion gives a chain of node-height n and O(n) worst-case search. AVL/red-black balancing gives a logarithmic worst-case structural bound.

Q: How does BFS on a tree differ from DFS?

A: BFS visits level by level, using a queue. DFS goes as deep as possible before backtracking, using a stack (explicit or the call stack). Same tree, different order.

Q: Why do databases use B-trees instead of BSTs?

A: High fan-out packs many keys into a page and reduces the number of page levels. Actual reads and latency depend on occupancy, key size, storage and cache state; many databases also support non-B-tree indexes.

Q: How do you validate ‘is this a valid BST?’ correctly?

A: Recurse with tightening (low, high) bounds. At each node, check low < node.val < high. Recurse left with (low, node.val), right with (node.val, high). Just comparing to immediate children is INSUFFICIENT — a distant descendant can violate the invariant.

Q: What is the node-count height of a complete binary tree with n nodes?

A: For n > 0, floor(log₂ n)+1; empty height is 0. A perfect tree has n=2^h−1 exactly. For one million nodes, a complete tree has height 20, and for one billion, 30.

Q: Give the 4-line iterative in-order traversal template.

A: Use a stack to retain ancestors whose left subtree is still being processed. Here is the complete value-returning version, using Node from the lab:

def inorder_iterative(root):
    stack, node, out = [], root, []
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out

Q: In a BST, how do you find the k-th smallest in O(h + k)?

A: Iterative in-order traversal, counting nodes as you visit them; stop when count == k. h is tree height, k is how far into the sorted order you need to go.

Q: Stretch — how would you check if two binary trees are structurally identical AND have equal values?

Stretch: true

A: Recursion. Base case: both None → True; one None → False. Recursive case: root1.val == root2.val AND same(root1.left, root2.left) AND same(root1.right, root2.right). O(n) time, O(h) stack. This is the same shape as ‘serialise both trees and compare strings’, but doesn't allocate the serialised strings.

Structural equality: executable stretch answer

def same_tree(a, b):
    if a is None or b is None:
        return a is b
    return (a.val == b.val and same_tree(a.left, b.left)
            and same_tree(a.right, b.right))
 
assert same_tree(Node(1, Node(2)), Node(1, Node(2)))
assert not same_tree(Node(1, Node(2)), Node(1, None, Node(2)))

Matching values in traversal order alone do not establish shape. This checks value/shape equality, not a is b; it neither clones nor mutates inputs. O(n) worst-case time and O(h) stack on ordinary trees, with early exit on a mismatch.

Explain-out-loud test

Teach these three, one minute each, no notes:

1. What is a BST and what makes lookup fast?
2. Give one real system that uses a tree (with why).
3. Why does balance matter, and what happens when you lose it?

Grind this pattern in the LeetCode track

This session builds the mental model for trees & bsts. The full pattern treatment — templates, five graded problems each, and the design review follow-ups — lives in the dedicated LeetCode series:

L22 · Trees I (DFS) · L23 · Trees II (BFS) · L24 · Trees III (BST) · L25 · Trees IV (Paths)

Do the concept here, then go there to build the reflex.

Explain-out-loud answer guide

1. A BST partitions all descendant keys around each node. Search follows one path, so height controls cost; balancing or a stated random model supplies logarithmic bounds.
2. A page-oriented B-tree index reduces page levels and supports range access. Returning r rows still requires r-row work; choose an index according to predicates and workload.
3. Sorted insertion into this plain BST makes a chain; balancing prevents that worst-case height, while a splay tree instead offers amortised bounds.

What comes next

Next: S029 · Heaps & Priority Queues

Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.

Corrective source notes

Primary passages checked 2026-10-10; saved raw/canonical evidence and bounded exact-program tests support the named contracts, not production benchmarks or whole-site approval.

• Princeton Algorithms: Binary Search Trees
• PostgreSQL: index types
• PostgreSQL: using EXPLAIN
• SortedContainers implementation
• SQLite page format
• React Fiber architecture author notes