These are my data structures and algorithms notes, cleaned up into nineteen posts, one pattern at a time. This one covers trees: binary search trees and how to insert, remove and query them, depth-first and breadth-first traversal, and the explicit-stack version of DFS for trees too deep to recurse on. It ends with the fifteen tree problems from the problem set.

Trees are where recursion stops being something you can avoid. A tree is a node plus two smaller trees, so almost every tree algorithm comes down to deciding what a node hands down to its children and what it expects back from them. In the order this series follows, this topic comes after Binary Search (a BST is binary search stored as nodes) and Linked List (a tree node is a list node with two next pointers). It leads into Tries, Heap / Priority Queue and Backtracking, and all three reuse the traversals taught here.

The prerequisites here are BST Insert and Remove, Depth-First Search, Breadth-First Search, BST Sets and Maps, and Iterative DFS. That’s five modules. Where they overlap I keep them lean: both BST modules share one worked tree, and the three traversal modules share another.

How to use this post: the method. Checkpoints have no answers on the page: work them out, then open the linked chat to have your answer checked.

All code in this post uses one node class:

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

BST Insert and Remove

Foundation

A binary search tree (BST) is a sorted array folded into nodes. Every node obeys one rule: all keys in its left subtree are smaller, all keys in its right subtree are larger. The rule does the same job as sortedness in binary search. One comparison at a node rules out an entire subtree, so a lookup follows a single root-to-leaf path instead of scanning everything.

What you gain over a sorted array is cheap change. Inserting into a sorted array shifts O(n) elements. Inserting into a BST just attaches a leaf at the end of that single path.

Mechanics

Worked tree: insert 8, 3, 10, 1, 6, 14, 4, 7, 13 in that order into an empty BST.

Insert walks down exactly as a search would. At each node, compare: smaller goes left, larger goes right, and the first empty slot is where the key belongs. Inserting 7 goes 7 < 8 left, 7 > 3 right, 7 > 6 right, and 6’s right slot is empty, so 7 lands there. Why is it safe to ignore the other side each time? At node 3, everything in 3’s left subtree is below 3, and 7 is above 3, so 7 can never belong there.

Remove has three cases, decided by how many children the target node has:

1. Leaf (0 children). Cut it off. Nothing below it needs a new parent.
2. One child. Hand that child up to the parent. Everything in the child’s subtree was already on the correct side of every ancestor, because it sat under the removed node, which was on that side too.
3. Two children. You can’t just splice the node out, since two subtrees would compete for one slot. Instead copy in the in-order successor (the smallest key in the right subtree), then delete the successor from the right subtree.

Why case 3 is safe, on the worked tree: remove 3. Its right subtree holds {6, 4, 7}, and its minimum is 4. Put 4 where 3 was:

• 4 is greater than everything in the left subtree ({1}), because 4 came from 3’s right side, so 4 > 3 > 1.
• 4 is smaller than everything left in the right subtree ({6, 7}), because it was that subtree’s minimum.

So the BST rule still holds at the new node. And deleting 4 from the right subtree is always case 1 or 2. The minimum has no left child, or it wouldn’t be the minimum.

Diagram

The worked tree before and after remove(3). Edge labels mark left and right, since a lone child’s side matters.

Before: 3 (red) is the node to remove; it has two children. 4 (amber) is its in-order successor, the smallest key in 3's right subtree.

After remove(3): 4 is copied up into 3’s position, and the old leaf 4 under 6 is deleted.

After: 4 (green) now holds 3's old position, and the old leaf 4 under 6 is gone, so 6 keeps only its right child 7.

Continuing: remove(14) is case 2, so 13 moves up to become 10’s right child. remove(7) is case 1, so it is cut off.

Implementation

def insert(root, val):
    """Insert val into the BST rooted at root; return the (possibly new) subtree root."""
    if root is None:
        return TreeNode(val)                  # the empty slot where val belongs
    if val < root.val:
        root.left = insert(root.left, val)    # every key in root.right is > root.val > val
    elif val > root.val:
        root.right = insert(root.right, val)  # every key in root.left is < root.val < val
    # val == root.val: already present; a set ignores duplicates
    return root


def remove(root, val):
    """Remove val from the BST rooted at root; return the new root of this subtree."""
    if root is None:
        return None                           # val was never in the tree
    if val < root.val:
        root.left = remove(root.left, val)
    elif val > root.val:
        root.right = remove(root.right, val)
    else:
        # 0 children: root.left is None, so root.right (also None) replaces root
        # 1 child: whichever side is not None replaces root
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        # 2 children: succ = smallest key in root.right; it is > every key in root.left
        # and < every other key in root.right, so it can sit where root.val was
        succ = root.right
        while succ.left:
            succ = succ.left
        root.val = succ.val
        # succ has no left child, so this nested call ends in the 0- or 1-child branch
        root.right = remove(root.right, succ.val)
    return root


def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []


root = None
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, v)
print(inorder(root))          # [1, 3, 4, 6, 7, 8, 10, 13, 14]
for v in [3, 14, 7]:
    root = remove(root, v)
    print(v, inorder(root))
# 3 [1, 4, 6, 7, 8, 10, 13, 14]
# 14 [1, 4, 6, 7, 8, 10, 13]
# 7 [1, 4, 6, 8, 10, 13]

Both functions return the subtree’s root so the caller can write root.left = remove(root.left, val), which re-attaches a subtree whose root changed or vanished, including the whole tree’s root. Edge cases I ran: removing from an empty tree or removing the only node returns None, and removing a missing key leaves the tree unchanged.

Complexity: both operations follow one root-to-leaf path, so time is O(h) where h is the tree’s height, plus O(h) recursion stack. For n keys, h is about log2(n) when the tree is balanced and n in the worst case. The worked tree has 9 keys and height 4. Inserting 1 through 100 in order produces height 100, which is a linked list with extra steps.

Recognition

Signals: the input is described as a binary search tree, or you need a collection that stays sorted while keys are added and removed. When NOT to hand-roll one: for exact lookups only, a hash set is O(1) average; for keys that never change, a sorted array plus binary search is simpler. In interviews you write the plain BST and say that production code would use a balanced one.

No problem in this topic’s list asks you to insert or delete. Three of them (Validate Binary Search Tree, Kth Smallest Element In a Bst, Lowest Common Ancestor of a Binary Search Tree) depend on the ordering rule this module rests on.

Pitfalls

• Forgetting to re-assign the return value (remove(root.left, val) without root.left =). The deletion happens in a subtree that is never re-attached.
• In case 3, deleting the successor from the whole tree rather than from root.right. You can end up deleting the wrong node or walking the wrong path.
• Assuming O(log n). A plain BST is only as good as its insertion order.
• Duplicates. Decide up front whether you ignore them (set), overwrite a value (map), or keep a count. Mixing <= and < between insert and search loses keys.

Active Recall

1. Insert 5 into the original worked tree (before any removals). Name the path and where 5 ends up.

2. Remove 8 (the root) from the original tree. What is the new root, and what does the right subtree look like?

3. You remove 3 using the predecessor instead of the successor. What replaces 3, and is the tree still valid?

Answer out loud or on paper first.

Answer these yourself, then get them checked byChatGPT ↗Claude ↗

Mini-task

Judgment call: no problem in this list inserts into or deletes from a BST, so these mechanics won’t be exercised anywhere else. The checkpoint stays.

You’re given the root of a BST and two numbers lo and hi. Return the tree with every key outside [lo, hi] removed, keeping every surviving node in its correct BST position relative to the others. On the worked tree with lo = 4, hi = 10, the surviving keys are 4, 6, 7, 8, 10.

Before any code, write down: the observation, the approach, why it’s correct, the complexity.

Work it out, then talk it through withChatGPT ↗Claude ↗

Transfer test

You’re logging events keyed by timestamp. Timestamps arrive in strictly increasing order, and you need insert, delete-by-key and “next event after time t”. A colleague suggests a plain BST. Would you use it? Why?

Decide, then get a second opinion fromChatGPT ↗Claude ↗

Depth-First Search

Foundation

Depth-first search visits a tree by going as deep as possible down one branch before backing up to try the next. Recursion gives you this for free: a call on a node makes a call on its left child, which runs to completion before the call on its right child begins.

The mental model that carries most tree problems is a node as a manager. It delegates to its two children (“give me the answer for your subtree”), waits, and combines their two answers with its own value. The empty tree (None) is the base case every delegation eventually hits.

Information can flow two ways:

• Top-down: the parent passes something down as an argument, like a running total, the current depth, or a bound.
• Bottom-up: the child returns something up, like a subtree size, a sum, or a flag.

Many problems use both. The function returns one thing to its parent and also updates a separate “best so far” answer on the side.

Mechanics

Worked tree (a plain binary tree, not a BST):

The worked tree. 3 has only a right child, 6; its left child is None.

Three visiting orders. Where you do the work at a node, relative to the two recursive calls, gives the order:

Order	Work happens	Worked tree
Preorder	before both children	1, -2, 4, -5, 3, 6
Inorder	between left and right	4, -2, -5, 1, 3, 6
Postorder	after both children	4, -5, -2, 6, 3, 1

Preorder sees a node before anything under it, so it’s the natural place to pass information down. Postorder sees a node after everything under it, so it’s the only place a node can use its children’s results. On a BST, inorder produces sorted order (you saw that in the previous module).

Bottom-up example: largest subtree sum. Each node’s subtree sum is node.val + left_sum + right_sum, and an empty subtree has sum 0. That only works in postorder, because both child sums must exist first. The value you return (this subtree’s sum) is not the value you want (the largest sum anywhere), so the largest one is tracked in a variable outside the recursion. Computed in postorder:

Node	left sum	right sum	subtree sum	best so far
4	0	0	4	4
-5	0	0	-5	4
-2	4	-5	-3	4
6	0	0	6	6
3	0	6	9	9
1	-3	9	7	9

The answer is 9 (the subtree rooted at 3), not the root’s 7. That’s why the return value and the answer have to be kept apart.

Top-down example: every root-to-leaf sum. Pass the running total down. When you reach a node with no children, that total is a finished path: 1 + (-2) + 4 = 3, 1 + (-2) + (-5) = -6, 1 + 3 + 6 = 10.

Diagram

The call tree for the subtree-sum DFS. Each box shows what the call returns to its parent. None calls return 0 and are left out, except the one under 3 that feeds its + 0.

Each box is one call and what it returns to its parent. dfs(3) (green) returns 9 and sets best = 9, the final answer; the dashed dfs(None) under 3 supplies its + 0.

Implementation

def sample():
    return TreeNode(1,
                    TreeNode(-2, TreeNode(4), TreeNode(-5)),
                    TreeNode(3, None, TreeNode(6)))


def preorder(node, out):
    if node is None:
        return
    out.append(node.val)      # work before children
    preorder(node.left, out)
    preorder(node.right, out)
# inorder / postorder: move the append between / after the two calls


def max_subtree_sum(root):
    best = float("-inf")      # -inf, not 0: with all-negative values the answer is negative

    def dfs(node):
        nonlocal best
        if node is None:
            return 0          # empty subtree adds nothing to its parent's sum
        left = dfs(node.left)             # postorder: both child sums exist
        right = dfs(node.right)           # before node's own sum is formed
        total = node.val + left + right   # at node -2: -2 + 4 + (-5) = -3
        best = max(best, total)           # the answer lives here...
        return total                      # ...the parent only needs this

    dfs(root)
    return best


def root_to_leaf_sums(root):
    sums = []

    def dfs(node, running):
        if node is None:
            return
        running += node.val               # top-down: the parent's total arrives as an argument
        if node.left is None and node.right is None:
            sums.append(running)          # a path ends only at a real leaf
            return
        dfs(node.left, running)
        dfs(node.right, running)

    dfs(root, 0)
    return sums


out = []
preorder(sample(), out)
print(out)                            # [1, -2, 4, -5, 3, 6]
print(max_subtree_sum(sample()))      # 9
print(root_to_leaf_sums(sample()))    # [3, -6, 10]

Edge cases I ran: root_to_leaf_sums(None) returns []. max_subtree_sum on a single node -7 returns -7, and on the tree -1 (children -2, -3) returns -2. On an empty tree it returns -inf, so decide what an empty input should mean before you return that.

Complexity: every node is visited once, so time is O(n) for n nodes. Space is O(h) for the call stack, where h is the height: O(log n) for a balanced tree, O(n) for a chain. root_to_leaf_sums also stores one number per leaf.

Recognition

Signals: the answer for a node depends on answers for its subtrees (“height”, “size”, “sum”, “is it balanced”, “same shape”). Or something accumulates along a path from the root (“path”, “ancestor”, “depth so far”). Or you need to visit every node and the order doesn’t matter much. In this list, Invert Binary Tree, Maximum Depth, Diameter, Balanced Binary Tree, Same Tree, Subtree of Another Tree, Count Good Nodes, and Binary Tree Maximum Path Sum all show these signals. Several of them also have the “return one thing, track another” shape from the subtree-sum example.

When NOT to reach for it first: when the question is about levels or rows, or about the nearest or shallowest match. That’s BFS (next module). DFS can answer those questions too, but it has to explore deep branches it could have skipped.

How it differs from the backtracking you’ll meet in Part 11: backtracking is DFS over a tree of choices that you build as you go. Here the tree already exists.

Pitfalls

• Missing the None base case, or checking node.left.val without checking that node.left exists.
• Detecting leaves at None instead of at the node. If root_to_leaf_sums appended at None, it would record every total twice for real leaves and invent a “path” ending at 3 (whose left child is None). On the worked tree that returns [3, 3, -6, -6, 4, 10, 10] instead of [3, -6, 10].
• Initializing the global best to 0 when values can be negative.
• Using a mutable default argument (def f(node, out=[])), which is shared across calls. That’s recalled Python behaviour, and it bites in repeated test runs.
• Returning the global answer from the recursion instead of the value the parent needs.

Active Recall

1. In the subtree-sum function, why must total be computed after both recursive calls and not before?

2. Change best = float("-inf") to best = 0 and run it on the tree -1 with children -2 and -3. What comes back, and what should?

3. Two different trees both have preorder [1, 2]. Draw them. Does inorder tell them apart?

Answer out loud or on paper first.

Answer these yourself, then get them checked byChatGPT ↗Claude ↗

Mini-task

Judgment call: skipped. Maximum Depth, Diameter, Balanced Binary Tree and Binary Tree Maximum Path Sum each make you build a combine-the-children DFS from scratch, so that practice happens when you solve them.

Transfer test

An org chart: each manager has a list of direct reports (any number, not two). For every manager you need the total headcount beneath them, counting reports of reports. Would you use DFS? Why?

Decide, then get a second opinion fromChatGPT ↗Claude ↗

Breadth-First Search

Foundation

Breadth-first search visits a tree level by level: the root, then everything one edge down, then everything two edges down. Picture a building’s floors being evacuated in order, where nobody from floor 3 leaves before all of floor 2 has.

The tool is a queue (first in, first out). Children join the back of the queue while the current level is served from the front, so a deeper level can’t be served before the shallower one is finished.

Mechanics

Same worked tree as DFS:

The same tree, one row per level.

Plain BFS order is 1, -2, 3, 4, -5, 6. To also know where one level ends, record the queue’s length at the start of each round. At that moment, the queue holds exactly one full level and nothing else. Why? It’s an invariant. Start: the queue holds only the root, which is all of level 0. During a round you pop exactly size nodes (all of level k) and push only their children (all of level k + 1, left to right). When the round ends, level k is gone and level k + 1 is complete.

Worked example: sum each level. Level sums are 1, then -2 + 3 = 1, then 4 + (-5) + 6 = 5, giving [1, 1, 5].

Diagram

Queue contents at the start of each round (front on the left):

The queue at the start of each round (blue). Its length is the round's size, every node in it is popped during that round, and their values give the level sum (green).

Implementation

from collections import deque


def level_sums(root):
    if root is None:
        return []
    sums = []
    queue = deque([root])     # deque: popleft is O(1) (recalled); list.pop(0) is O(n)
    while queue:
        size = len(queue)     # exactly one level is queued right now
        total = 0
        # range(size) is fixed here: the children appended below wait for the next round
        for _ in range(size):
            node = queue.popleft()
            total += node.val
            if node.left:
                queue.append(node.left)     # left before right keeps each level left-to-right
            if node.right:
                queue.append(node.right)
        sums.append(total)
    return sums


print(level_sums(sample()))   # [1, 1, 5]

I ran it with the queue printed at the start of each round: [1], [-2, 3], [4, -5, 6], matching the diagram. Edge cases: an empty tree gives [], a single node 5 gives [5], and a left-leaning chain 1, 2, 3 gives [1, 2, 3] with one node per level.

Complexity: each node is enqueued and dequeued once, so time is O(n). Space is O(w), where w is the tree’s maximum width. For a complete tree the last level holds about n/2 nodes, so that’s O(n). For a chain it’s O(1).

Recognition

Signals: “level”, “row”, “depth-by-depth”, “from left to right on each level”, “the first/nearest/shallowest node that…”, “minimum number of steps”. In this list, Binary Tree Level Order Traversal and Binary Tree Right Side View show the level signal directly.

When NOT to use it: when a node’s answer comes from its children’s answers (sizes, sums, heights), bottom-up DFS is shorter and uses O(h) memory rather than O(w). DFS vs BFS on a tree is mostly a question of which order the problem cares about. Both visit every node in O(n).

Pitfalls

• Letting one level bleed into the next. for _ in range(len(queue)) is safe because range evaluates len(queue) once (recalled Python semantics, verified here). An inner while queue: is not safe, because it keeps consuming the children you just appended. On the worked tree it returns one “level” [1, -2, 3, 4, -5, 6].
• Using list.pop(0), which shifts every remaining element and turns BFS into O(n²) on wide trees.
• Enqueuing None children and then dereferencing them. Either guard before appending (as above) or skip None right after popping, and do it consistently.
• Forgetting the empty-root check before seeding the queue.

Active Recall

1. Right after round 1 finishes, what is in the queue, and why is -5 guaranteed to sit before 6?

2. Swap the deque for a stack: pop() from the back instead of popleft(). Keep the same push order (left, then right). What order do you get on the worked tree?

3. For a perfect binary tree with 1,023 nodes (10 levels), roughly how much memory do BFS and recursive DFS need at their peak?

Answer out loud or on paper first.

Answer these yourself, then get them checked byChatGPT ↗Claude ↗

Mini-task

Judgment call: skipped. Binary Tree Level Order Traversal and Binary Tree Right Side View both make you build level-by-level BFS yourself, so that’s where this gets practised.

Transfer test

A company tree (CEO at the root). You need the smallest number of management steps from the CEO to any employee whose title is “Security Lead”. The tree is very deep in some departments. Would you use BFS? Why?

Decide, then get a second opinion fromChatGPT ↗Claude ↗

BST Sets and Maps

Foundation

A BST is how many languages implement an ordered set (keys only) or an ordered map (key to value). Java’s TreeMap and C++’s std::map are balanced BSTs (recalled). A hash map answers “is this key here?” in O(1) average but knows nothing about order. An ordered map answers the same question in O(log n) when balanced, and it can also answer order questions a hash map can’t: smallest key, largest key, next key above x, previous key below x, and all keys in sorted order.

Python’s standard library has no tree-based map (recalled). dict is a hash map that remembers insertion order, not key order. When you need order in Python you use a sorted list with bisect, or the third-party sortedcontainers package (recalled), or you write the BST yourself.

Mechanics

Same worked BST as module 1 (8, 3, 10, 1, 6, 14, 4, 7, 13, before any removals). A map node carries key and val, and search compares keys exactly like insert did.

get(key) walks one path. put(key, val) walks the same path and either overwrites the value (the key exists) or attaches a new leaf.

floor(x), the largest key ≤ x, shows the BST ordering doing real work. Keep a best candidate and walk down:

• At a node with key > x, this key is too big, and so is everything in its right subtree. Go left.
• At a node with key ≤ x, this key is a valid candidate. Record it. Any better candidate must be larger but still ≤ x, and the only larger keys below here are in the right subtree. Go right.

Trace for floor(5): at 8 (8 > 5) go left. At 3 (3 ≤ 5) best = 3, go right. At 6 (6 > 5) go left. At 4 (4 ≤ 5) best = 4, go right. None, so stop. Answer: 4.

ceiling(x), the smallest key ≥ x, is the mirror, and it’s worth checking separately rather than trusting “symmetric”. Trace for ceiling(11): at 8 (8 < 11) go right. At 10 (10 < 11) go right. At 14 (14 ≥ 11) best = 14, go left. At 13 (13 ≥ 11) best = 13, go left. None, so stop. Answer: 13.

Diagram

The floor(5) walk, with best after visiting each node:

Amber nodes are greater than 5, so the walk goes left; blue and green nodes are ≤ 5, so they are recorded as best and the walk goes right. Green is the final answer, 4. Grey nodes are never visited.

Implementation

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


class TreeMap:
    def __init__(self):
        self.root = None

    def put(self, key, val):
        if self.root is None:
            self.root = Node(key, val)
            return
        cur = self.root
        while True:
            if key == cur.key:
                cur.val = val                 # map semantics: existing key, overwrite
                return
            side = "left" if key < cur.key else "right"
            nxt = getattr(cur, side)
            if nxt is None:
                setattr(cur, side, Node(key, val))   # first empty slot on the path
                return
            cur = nxt

    def get(self, key):
        cur = self.root
        while cur:
            if key == cur.key:
                return cur.val
            cur = cur.left if key < cur.key else cur.right
        return None

    def floor(self, x):
        """Largest key <= x, or None."""
        best, cur = None, self.root
        while cur:
            if cur.key > x:
                cur = cur.left        # cur.key and every key in cur.right are > x
            else:
                best = cur.key        # cur.key <= x is valid; anything better is
                cur = cur.right       # in (cur.key, x], so only in cur.right
        return best

    def ceiling(self, x):
        """Smallest key >= x, or None."""
        best, cur = None, self.root
        while cur:
            if cur.key < x:
                cur = cur.right       # cur.key and every key in cur.left are < x
            else:
                best = cur.key        # cur.key >= x is valid; anything better is
                cur = cur.left        # in [x, cur.key), so only in cur.left
        return best


m = TreeMap()
for k in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    m.put(k, f"v{k}")
m.put(6, "six")
print(m.get(6), m.get(5))            # six None
print(m.floor(5), m.ceiling(11))     # 4 13
print(m.floor(0), m.ceiling(15))     # None None
print(m.floor(8), m.ceiling(8))      # 8 8

The None results check both “no candidate” paths. For floor(0), every key is > 0, so the walk only goes left and best is never set. For ceiling(15), every key is < 15, so it only goes right. An exact match returns the key itself for both floor and ceiling. On an empty map all three queries return None. For comparison, the sorted-list version: with keys = [1, 3, 4, 6, 7, 8, 10, 13, 14], keys[bisect.bisect_right(keys, 5) - 1] gives 4 and keys[bisect.bisect_left(keys, 11)] gives 13 (both run here). Remember to bounds-check those indices when x is below or above every key.

Complexity: get, put, floor and ceiling are O(h) time and O(1) extra space (loops, no recursion). An in-order walk over all keys is O(n). With bisect on a sorted list, lookups are O(log n) but inserts are O(n), because the list shifts (recalled).

Recognition

Signals: you need “the closest key above/below x”, “the k-th smallest”, “all keys in a range”, or sorted iteration while the collection keeps changing. When the input is already a BST, the signal is the ordering itself. Any comparison at a node can discard a whole subtree, so ask what one comparison rules out. In this list, Validate Binary Search Tree, Kth Smallest Element In a Bst, and Lowest Common Ancestor of a Binary Search Tree are the problems where the BST property carries the solution.

When NOT to use it: exact-match lookups only (use dict or set), or a fixed dataset (sort once, then bisect). If you only ever need the min or max, a heap (Part 10) is simpler.

Pitfalls

• Moving on without recording the candidate: in floor, forgetting best = cur.key before going right returns None or a stale key.
• Mixing up the directions between floor and ceiling. Test each one on an exact match, below-all, and above-all input.
• Assuming a plain BST gives O(log n). The same sorted-insert collapse from module 1 applies.
• Treating Python’s dict order as key order. It’s insertion order (recalled, guaranteed since 3.7).

Active Recall

1. On the worked BST, what are ceiling(5) and floor(7)? Trace ceiling(5).

2. In floor, after recording best = cur.key, why is it safe to never look at cur.left again?

3. With keys = [1, 3, 4, 6, 7, 8, 10, 13, 14], what does bisect.bisect_right(keys, 0) - 1 return, and why is that a bug if used directly as an index?

Answer out loud or on paper first.

Answer these yourself, then get them checked byChatGPT ↗Claude ↗

Mini-task

Judgment call: skipped. Validate Binary Search Tree, Kth Smallest Element In a Bst and Lowest Common Ancestor of a Binary Search Tree each require reasoning from the ordering property on your own, so they serve as this module’s checkpoint.

Transfer test

A ride-hailing service stores drivers keyed by their current distance from the city centre (distances change as drivers move). Riders ask for “the driver whose distance is closest to mine”. Would you use an ordered map? Why?

Decide, then get a second opinion fromChatGPT ↗Claude ↗

Iterative DFS

Foundation

Recursion uses a hidden stack, the call stack. Iterative DFS makes that stack an ordinary Python list you control. Two reasons to do it:

• Depth. CPython’s default recursion limit is 1,000 frames (recalled; sys.getrecursionlimit() printed 1000 here). A 5,000-node chain made the recursive preorder above raise RecursionError when I ran it. The iterative version handled it fine.
• Control. With your own stack you can pause after any node, resume later, or stop early without unwinding frames.

Mechanics

Same worked tree as DFS and BFS.

Preorder is the easy one: pop a node, visit it, then push its children. Push the right child first, because a stack is last-in-first-out. The left child, pushed last, is popped next, so the left subtree is fully explored before the right one resumes. Here’s the invariant: the stack holds exactly the subtrees still owed a visit, in the reverse of the order they’ll be visited.

Inorder is trickier because a node must wait until its left subtree is done. The pattern: from the current node, push every node down the left spine. Pop one, and that popped node’s left subtree is finished (everything pushed after it has already been popped), so visit it now. Then move to its right child and repeat. The loop runs while cur or stack: cur is a subtree not yet started, and stack holds nodes waiting to be visited.

Carrying state. Recursive top-down DFS passes arguments. Iteratively, you push a tuple (node, state) so each node carries its own copy, for example (node, running_sum).

Postorder trick: do a root, right, left preorder and reverse the output. On the worked tree, root, right, left gives 1, 3, 6, -2, -5, 4, and reversed that’s 4, -5, -2, 6, 3, 1, the postorder from the DFS module.

Diagram

The stack after each pop, for both orders (top of stack on the right):

Preorder: the popped node (amber), the stack after pushing its children, and the output so far. The top of the stack (blue) is the next node popped.

Inorder: the popped node (amber), the stack right after that pop, and the output so far. Blue marks the top of the stack.

In the inorder trace, 1, -2 and 4 are pushed before the first pop (the left spine). After -2 is popped, cur moves to -5, which is pushed and popped immediately because it has no left child.

Implementation

def preorder_iter(root):
    out = []
    stack = [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:
            stack.append(node.right)   # pushed first, popped after the whole left subtree
        if node.left:
            stack.append(node.left)    # pushed last, popped next (LIFO)
    return out


def inorder_iter(root):
    out, stack, cur = [], [], root
    while cur or stack:
        while cur:                     # push the whole left spine of cur
            stack.append(cur)
            cur = cur.left
        node = stack.pop()             # every node in node.left is already in out
        out.append(node.val)
        cur = node.right               # next: the right subtree of node
    return out


def root_to_leaf_iter(root):
    sums = []
    stack = [(root, 0)] if root else []
    while stack:
        node, running = stack.pop()    # each entry carries its own running total
        running += node.val
        if node.left is None and node.right is None:
            sums.append(running)
        if node.right:
            stack.append((node.right, running))
        if node.left:
            stack.append((node.left, running))
    return sums


print(preorder_iter(sample()))      # [1, -2, 4, -5, 3, 6]
print(inorder_iter(sample()))       # [4, -2, -5, 1, 3, 6]
print(root_to_leaf_iter(sample()))  # [3, -6, 10]

All three match the recursive outputs from the DFS module. Edge cases I ran: empty tree gives [] for all three, a single node 9 gives [9], and a 5,000-deep left chain returns all 5,000 values from both preorder_iter and inorder_iter (inorder starts 0, 1, 2 from the bottom of the chain) with no error.

Complexity: O(n) time. O(h) stack space for inorder and for the chain-shaped trees above. Preorder’s stack can hold one pending right child per level plus the current node’s children, which is still O(h) for a binary tree.

Recognition

Signals: the tree may be very deep (degenerate or adversarial inputs, n up to 10^5 as a chain), you need to pause and resume a traversal, or you want to stop early after finding what you need without unwinding recursion. Otherwise recursion is shorter and interviewers accept it. Say out loud that deep inputs could hit the recursion limit, then offer the iterative version.

In this list, every problem can be solved recursively. Kth Smallest Element In a Bst is the one where knowing the iterative version gives you a real alternative.

How it differs from BFS: the same loop shape with a different container. Stack means depth-first, queue means breadth-first.

Pitfalls

• Pushing left before right in preorder, which gives root, right, left.
• Inorder loop condition while stack: alone. It exits at the start, when the stack is empty but cur is the root, and again after the root is popped while its right subtree is still unvisited.
• Forgetting cur = node.right after visiting, which loops forever on the same left spine or skips right subtrees.
• Sharing one mutable state object (like a list for the current path) across stack entries. Push a copy or an immutable value.
• Raising sys.setrecursionlimit as a “fix”. It moves the crash to the C stack instead, which can kill the interpreter (recalled). An explicit stack is the real fix.

Active Recall

1. In inorder_iter on the worked tree, what’s on the stack right after 4 is popped, and why can 4 be visited then?

2. Why does inorder_iter need cur at all, when preorder_iter works with just the stack?

3. How would you turn preorder_iter into postorder without a visited flag?

Answer out loud or on paper first.

Answer these yourself, then get them checked byChatGPT ↗Claude ↗

Mini-task

Judgment call: included. Every problem in this list can be solved with recursion, so explicit-stack mechanics would otherwise never be practised on their own.

Design a class that takes the root of a BST and offers has_next() and next(), where next() returns the keys in ascending order, one per call. The tree may have 10^5 nodes. Your class may use O(h) memory, where h is the height, but not O(n). So copying all keys into a list up front is not allowed. On the worked BST from module 1, repeated next() calls return 1, 3, 4, 6, 7, 8, 10, 13, 14.

Before any code, write down: the observation, the approach, why it’s correct, the complexity.

Work it out, then talk it through withChatGPT ↗Claude ↗

Transfer test

You’re writing a tool that walks a directory tree to total file sizes. Some generated build folders nest 20,000 levels deep. Would you use iterative DFS? Why?

Decide, then get a second opinion fromChatGPT ↗Claude ↗

Integration

How the five connect to trees. Every tree problem makes two decisions. The first is what order to visit nodes in: depth-first (recursive by default, iterative when depth or pausing matters) or breadth-first (when levels or nearness matter). The second is which way information flows: down as arguments, up as return values, or both, with a separate variable for the answer. The two BST modules add a third question: does the ordering let me skip subtrees? If it does, a problem that looks like “visit everything” becomes “walk one path” in O(h).

Distinguishing the approaches:

If the problem…	Reach for	Why
needs a node’s answer from its children’s answers	recursive DFS, postorder	children must finish first
passes a constraint or running value from root toward leaves	recursive DFS, preorder-style arguments	each path carries its own state
talks about levels, rows, “leftmost/rightmost per level”, or nearest	BFS with a level-size loop	the queue separates levels
is on a BST and asks about keys, ranks or ranges	walk using the ordering (plus inorder = sorted)	one comparison discards a subtree
may be thousands deep, or must pause/stop early	iterative DFS	your stack, your control
compares two trees	DFS on both in lockstep	the same recursion shape on a pair of nodes

Competing pairs to keep straight: DFS vs BFS (both O(n) time; BFS memory is width, DFS memory is height; choose by the order the problem cares about). Recursive vs iterative DFS (same order and complexity; iterative only buys depth safety and control). General-tree reasoning vs BST reasoning (if the problem says BST and your solution never compares against a node’s key, you’re probably ignoring the property that makes it easy).

Recognition checklist for an unfamiliar tree problem:

1. Is it a BST? If yes, what does one comparison at a node rule out?
2. What does a node need from its children? If anything, that’s a postorder return value. Write its definition in one sentence.
3. What does a node need from its ancestors? If anything, pass it as an argument.
4. Is the returned value the same as the final answer? If not, keep the answer in a separate variable.
5. Does the problem mention levels, rows, or “nearest”? If so, use BFS with size = len(queue).
6. What does None return? Check that it doesn’t break a max, min or sum at the parent.
7. How deep can the tree be? If a chain of 10^4 or more nodes is allowed, mention the recursion limit and have the iterative version ready.
8. Is the input traversal sequences rather than nodes? Remember which traversals pin down a shape and which don’t.

The problems

Solve these with the cycle from the method: a 15-minute honest struggle, a one-sentence key insight once it clicks, then spaced repetition. For trees, spend the struggle on two questions: can I combine results from the left and right subtrees? And can I reconstruct the call stack on a three- or four-node example and explain how information flows from the leaves to the root?

15 problems · 6 easy · 7 medium · 2 hard · tracker spreadsheet (.xlsx)

#	Problem	Difficulty	Coach
1	Invert Binary Tree	Easy	ChatGPT · Claude
2	Maximum Depth of Binary Tree	Easy	ChatGPT · Claude
3	Diameter of Binary Tree	Easy	ChatGPT · Claude
4	Balanced Binary Tree	Easy	ChatGPT · Claude
5	Same Tree	Easy	ChatGPT · Claude
6	Subtree of Another Tree	Easy	ChatGPT · Claude
7	Lowest Common Ancestor of a Binary Search Tree	Medium	ChatGPT · Claude
8	Binary Tree Level Order Traversal	Medium	ChatGPT · Claude
9	Binary Tree Right Side View	Medium	ChatGPT · Claude
10	Count Good Nodes In Binary Tree	Medium	ChatGPT · Claude
11	Validate Binary Search Tree	Medium	ChatGPT · Claude
12	Kth Smallest Element In a Bst	Medium	ChatGPT · Claude
13	Construct Binary Tree From Preorder And Inorder Traversal	Medium	ChatGPT · Claude
14	Binary Tree Maximum Path Sum	Hard	ChatGPT · Claude
15	Serialize And Deserialize Binary Tree	Hard	ChatGPT · Claude

Take this lesson as a live session

To be taught this interactively instead, with the coach waiting for your answers at every checkpoint, open the full lesson prompt, already filled in for trees:

Open the full lesson inChatGPT ↗Claude ↗

dsa trees binary-search-tree python series