Day 29 · Org charts with a sorting rule

Binary Trees & BSTs

You will be able to

Define tree anatomy precisely: root, leaf, depth, height, subtree
Implement all four traversals (pre/in/post-order and level-order) from scratch
Implement BST search and insert and state why both are O(h), not O(log n)
Explain how a BST degenerates into a linked list and what that costs
Solve max-depth, invert-tree, and validate-BST with clean recursion

Today's ~120 minutes

Spaced-rep warm-up: due cards from Week 4 (recursion, stacks, linked lists)	10 min
ELI5 + tech read; step through the BST-search visualizer	18 min
Guided: build & traverse, then BST ops + three classics	42 min
Practice: kth smallest in a BST	18 min
Project: tree toolkit + tests, commit	22 min
Quiz + add today's flashcards to the deck	10 min

Builds on: Day 26 — Linked lists — nodes & pointers · Day 27 — Recursion & divide/conquer · Day 25 — Stacks & queues (BFS preview)

The analogy

🧸 ELI5⚙ Tech

Picture a company org chart: one CEO at the top, each person managing at most two reports. That is a binary tree — every box is a node, the boxes under it are its children, and everything below one manager is that manager's subtree. Walking the chart top-to-bottom, level-by-level is one way to visit everyone; diving down one management chain before backing up is another.

Now add a sorting rule to the org chart: everyone to a manager's LEFT earns less, everyone to the RIGHT earns more — and the rule holds for the entire left and right sides, not just direct reports. That is a binary search tree. The rule is what makes it searchable: to find the person earning 72k you never interview the whole company — at each box you ask "less or more?" and discard half the chart, exactly like the phone-book halving you will formalize on Day 33. But the magic only works if the chart stays bushy. If every hire lands on the right side, your "tree" is really a queue of people in a hallway, and searching it means walking the whole hallway.

Why this matters on the job

Trees are everywhere in your future stack: the JSON documents your APIs pass around are trees, HTML is a tree, Python parses your code into an abstract syntax tree, Postgres indexes are B-trees (Day 38), and the tries behind autocomplete (Day 30) are trees too. In interviews, tree questions are the single most common data-structure category, and they are really recursion questions in costume — the Day 27 skill cashed in. As an FDE you will also literally walk trees: extracting fields from deeply nested customer JSON payloads is a tree traversal you will write on-site.

Watch it happen

The org chart with a sorting rule — find 40 in a BST

step 1 / 5

A binary search tree: every node's LEFT subtree holds smaller values, RIGHT holds bigger. That one invariant is a promise we can cash in at every step. Target: 40.

🎯 Predict modespeed1×

Guided practice

guided 1

Build a tree and walk it four ways

20 min

Create trees_lab.py and paste the starter code — a TreeNode class and a hand-built sample tree.
Implement inorder, preorder, and postorder as recursive functions that append to a result list. Each is three lines of real logic.
Predict on paper what each traversal prints for the sample tree BEFORE running. Diff your prediction against reality — mispredictions are where learning lives.
Implement level_order with collections.deque: pop from the left, append children on the right, collect values per level.
Sanity check: run inorder on the BST built by the starter's insert calls — the output must be sorted. Say out loud WHY (left < node < right, applied recursively).

🐍 python — editable, runs in your browser

from collections import deque

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

# hand-built tree:        4
#                        / \
#                       2   7
#                      / \   \
#                     1   3   9
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7, None, TreeNode(9)))

def inorder(node, out=None):
    if out is None:
        out = []
    if node is None:
        return out
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)
    return out

def preorder(node, out=None):
    # TODO: node first, then left, then right
    ...

def postorder(node, out=None):
    # TODO: left, right, then node
    ...

def level_order(root):
    if root is None:
        return []
    levels, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):   # exactly one level per outer pass
            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

print("inorder:", inorder(root))        # [1, 2, 3, 4, 7, 9] -- sorted!
print("levels:", level_order(root))     # [[4], [2, 7], [1, 3], [9]]

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

guided 2

BST ops + three classics, think-aloud

22 min

Work each problem with the two-question recipe: base case? combine children's answers?

Implement bst_insert and bst_search (starter has signatures). Insert 50 sorted values into a fresh BST, then measure its height — you have just built the degenerate case. Insert the same values shuffled and compare heights.
Classic 1 — Max depth. Think aloud: "Empty tree is depth 0. Otherwise I am 1 + the deeper of my two subtrees." Write it in 3 lines.
Classic 2 — Invert a tree. Think aloud: "Swap my children, then ask each child to invert itself." Verify by printing level_order before/after.
Classic 3 — Validate BST. First write the TEMPTING wrong version (check each node against only its direct children), and break it with the starter's trap tree. Then write the correct version: pass down (lo, hi) bounds that every node must respect. This bug is the most common tree-interview mistake — earn the scar now.

🐍 python — editable, runs in your browser

def bst_insert(node, val):
    if node is None:
        return TreeNode(val)
    if val < node.val:
        node.left = bst_insert(node.left, val)
    else:
        node.right = bst_insert(node.right, val)
    return node

def bst_search(node, val):
    if node is None:
        return False
    if val == node.val:
        return True
    return bst_search(node.left if val < node.val else node.right, val)

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

# the trap for naive validate: 5.left=3, 5.right=8, but 3.right=9
# every parent-child pair is fine; 9 in the LEFT subtree of 5 is not.
trap = TreeNode(5, TreeNode(3, TreeNode(1), TreeNode(9)), TreeNode(8))

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))

print(is_valid_bst(trap))   # False -- bounds catch what parent-checks miss

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

On your own

Kth smallest in a BST

18 min

Given the root of a BST and an integer k, return the kth smallest value (1-indexed). Solve it two ways: (1) the obvious way using a full traversal, then (2) an early-exit version that stops traversing the moment it has seen k values.

State the complexity of both. Test on a BST of 1..15 with k = 1, 7, 15.

Hints (only if stuck): which traversal visits BST values in sorted order? For early exit, a generator (Day 11) plus itertools.islice is elegant — or count down k inside the recursion.

Ship before you stop

Tree toolkit for the interview repo

Create dsa/trees.py in your practice repo: TreeNode, all four traversals, bst_insert/bst_search, height, plus the three classics (max depth, invert, validate). Add test_trees.py with pytest cases including the degenerate BST (sorted inserts) and the validate-BST trap tree. In the module docstring, write a 5-line "when do I reach for a tree?" note in your own words. Commit — Day 35's drill and Day 179's interview gym pull problems straight from this file.

Rubric — check what you completed (0/5)

All four traversals pass tests, including an empty tree and a single-node treevalidate-BST test includes the trap tree that defeats the parent-only checkDegenerate-vs-shuffled height test demonstrates O(n) vs ~O(log n) heightKth-smallest solution included with both versions and their complexities in commentsCommitted with a descriptive message; tests green via pytest

Common mistakes & misconceptions

Validating a BST by comparing each node only with its children. The invariant covers WHOLE subtrees — pass down (lo, hi) bounds. This is the classic trap.
Saying BST search is O(log n) unconditionally. It is O(h); only a balanced tree gives h ≈ log n. Sorted inserts give h = n.
Confusing depth (node property, from root) with height (tree property, longest path down). Interviewers use both; know which is which.
Forgetting the base case handles None, then crashing on leaf children. Every recursive tree function starts with the None check.
Using level-order (queue) when a recursive DFS is three lines — or recursion when the problem says "by level", which is the queue's job.
Tracing every recursive call by hand instead of trusting the recursive contract: assume children return correct answers, combine, done.

Knowledge check

Q1. You run an in-order traversal on a valid BST. What comes out?

Q2. You insert 1, 2, 3, ..., 1000 into an empty BST in that order. Searching it now costs…

Q3. A colleague validates a BST by checking node.left.val < node.val < node.right.val at each node. Why is this wrong?

Go deeper — curated resources

toolVisuAlgo — Binary Search Tree visualization ↗15 min bookOpenDSA — Binary Trees chapter ↗25 min courseNeetCode Roadmap — Trees section (pick 2 to attempt) ↗20 min

If you have a third hour

Self-balancing trees (AVL rotations) on VisuAlgo ↗ — Watch how a rotation restores balance after an insert. You need the concept, not the code — Day 38's B-trees solve balance for databases differently.

Done means

All four traversals implemented; in-order-on-BST-is-sorted verified
Trap tree defeats the naive validator and passes the bounds version
Kth smallest solved both ways with complexities stated
Tree toolkit committed with green tests
Quiz ≥ 2/3

How this connects

← Back: Nodes-and-pointers come straight from Day 26's linked lists — a tree is a linked list that branches. Every traversal is Day 27's recursion recipe, and level-order is Day 25's queue earning its keep.

Forward →: Day 30 reshapes trees into heaps and tries. Day 31 generalizes traversal to graphs (BFS/DFS). Day 33 formalizes the halving idea BSTs rely on, and Day 38 reveals the B-tree — the BST's disk-based cousin inside every database index.

Unlocks: D30 Heaps, Priority Queues & Tries · D31 Graphs, BFS & DFS · D33 Binary Search & Variants · D35 Week 5 Checkpoint: Interview Drill I