17 · Classics: binary search, recursion, trees and BST Code

Half-open binary search without off-by-one bugs · recursion base cases · tree traversal · closest value in a BST · linked lists and LRU as optional breadth

Why it matters for NPE. Reported alongside the file task: 'closest value in a BST', 'binary search for an element meeting a condition', 'split an array into equal halves'. One sitting of fundamentals covers the conventional-algorithm half of the screen.

Primer: three ideas, one sitting

The second problem on the screen is usually a LeetCode easy or medium. The reported ones for this role cluster into three ideas. Binary search: halve a sorted range or a monotone predicate until one index remains ("binary search for an element meeting a condition"). Recursion: solve the problem on a smaller input and combine, with a base case that stops it ("split an array into two parts with equal sum" has a choose/skip recursion under it). Trees: a node with two children, visited depth-first by recursion or breadth-first by a queue, with the BST ordering rule making search O(height) ("closest value to K in a BST"). Linked lists and the LRU cache are breadth: know them, do not drill them.

Watch

Binary search on a half-open interval

Keep the candidates in [lo, hi): lo is included, hi is excluded. Start with lo, hi = 0, len(a). Stop when lo == hi, which means the range is empty and lo is the answer position. The invariant you say out loud: everything left of lo fails the test, everything from hi onward passes it, and the answer, if it exists, is in [lo, hi).

def lower_bound(a, target):
    """First index i with a[i] >= target, or len(a) if none. Same as bisect.bisect_left."""
    lo, hi = 0, len(a)                     # candidates are [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2               # lo <= mid < hi, always
        if a[mid] < target:
            lo = mid + 1                   # a[mid] is too small: it and everything left of it are out
        else:
            hi = mid                       # a[mid] might be the answer: keep it, drop what is right of it
    return lo

def search(nums, target):                  # LC 704: exact match or -1
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return -1

Why it terminates. mid < hi always, so hi = mid strictly shrinks the range; lo = mid + 1 strictly grows lo. Each step halves the range: O(log n) steps, O(1) space. Why no off-by-one. The two updates are asymmetric on purpose: mid is excluded when it fails (lo = mid + 1) and kept when it might be the answer (hi = mid, because hi is exclusive). You never write mid - 1 and you never write lo = mid.

bisect: the library versions

from bisect import bisect_left, bisect_right, insort

a = [1, 3, 3, 5, 8]
bisect_left(a, 3)    # 1: first index with a[i] >= 3   (insertion point before equal items)
bisect_right(a, 3)   # 3: first index with a[i] >  3   (insertion point after equal items)
bisect_right(a, 3) - bisect_left(a, 3)   # 2: how many 3s, O(log n)
bisect_right(a, 4) - 1                   # 2: index of the largest value <= 4
i = bisect_left(a, 5); found = i < len(a) and a[i] == 5     # exact membership test
insort(a, 4)         # insert keeping order: O(log n) to find, O(n) to shift. A list is not a tree.
bisect_left(rows, 7, key=lambda r: r[0])  # Python 3.10+: search by a field

Use these whenever the list is already sorted and you need "where would x go" or "largest value not above x": the Time Based Key-Value Store in topic 15, finding the config version active at a timestamp, matching a value to a bucket boundary.

The "first true" form: binary search on a predicate

Most interview binary searches are not "find x in a sorted list". They are: a predicate over indices is False, False, ..., False, True, True, ..., True and you want the first True. Sorted search is the special case pred(i) = a[i] >= target. Any time you can phrase the question as a monotone yes/no over a range, this template answers it in O(log n) calls.

def first_true(lo, hi, pred):
    """Smallest i in [lo, hi) with pred(i) True; pred must be monotone False..True. Returns hi if none."""
    while lo < hi:
        mid = (lo + hi) // 2
        if pred(mid):
            hi = mid                   # mid is True: answer is mid or left of it
        else:
            lo = mid + 1               # mid is False: answer is right of it
    return lo

# LC 278 First Bad Version: versions 1..n, isBadVersion(v) is monotone (once bad, all later are bad)
def first_bad_version(n, is_bad):
    return first_true(1, n + 1, is_bad)         # O(log n) API calls instead of O(n)

# LC 162 Find Peak Element: nums[i] != nums[i+1]; a peak is nums[i] > nums[i+1] (nums[n] is -inf)
def find_peak(nums):
    n = len(nums)
    return first_true(0, n - 1, lambda i: nums[i] > nums[i + 1])
    # pred is monotone: once the slope turns downward there is a peak at or before that point;
    # if it never turns, first_true returns n - 1, the last element, which is then the peak.

Say the argument for Find Peak before coding: the array is not sorted, but the predicate "the slope goes down at i" is. If nums[mid] < nums[mid+1] you are on an upslope, so a peak must exist to the right; otherwise a peak exists at mid or to the left. That is exactly the first_true shape. Other instances: the smallest capacity that ships packages in D days, the first commit that broke the build, the first timestamp when a counter exceeded a threshold, square root to integer precision.

Recursion: base case, progress, the stack

A recursive function needs two things: a base case that returns without recursing, and progress, meaning every recursive call is on a strictly smaller input so it reaches the base case. Each call pushes a frame on the call stack holding its locals; depth d costs O(d) memory. CPython's default limit is about 1000 frames (sys.getrecursionlimit()) and exceeding it raises RecursionError. Raising the limit with sys.setrecursionlimit helps for a few thousand frames, but deep recursion (a 10⁵-node skewed tree, a linked list) must be rewritten as a loop with an explicit stack. Say that unprompted whenever you recurse on input you do not control.

def depth_recursive(node):                  # fine for balanced trees: depth is O(log n)
    if node is None:                        # base case first
        return 0
    return 1 + max(depth_recursive(node.left), depth_recursive(node.right))

def depth_iterative(root):                  # explicit stack: safe for any shape
    best, stack = 0, [(root, 1)] if root else []
    while stack:
        node, d = stack.pop()
        best = max(best, d)
        for child in (node.left, node.right):
            if child:
                stack.append((child, d + 1))
    return best

Memoisation: functools.lru_cache and House Robber as choose/skip

When a recursion calls itself on the same arguments many times, cache the results. @lru_cache(maxsize=None) turns an exponential tree of calls into one call per distinct argument. Arguments must be hashable (ints, tuples, strings), not lists.

from functools import lru_cache

def rob(nums):                              # LC 198: no two adjacent houses
    @lru_cache(maxsize=None)
    def best(i):                            # most loot from houses i.. end
        if i >= len(nums):                  # base case: no houses left
            return 0
        take = nums[i] + best(i + 2)        # choose house i, must skip i + 1
        skip = best(i + 1)                  # skip house i
        return max(take, skip)
    return best(0)                          # O(n) time and O(n) space with the cache; 2^n without it

def rob_iterative(nums):                    # same recurrence, bottom up, O(1) space
    take = skip = 0                         # best so far if we robbed / did not rob the previous house
    for x in nums:
        take, skip = skip + x, max(take, skip)
    return max(take, skip)

Trace rob_iterative([2, 7, 9, 3, 1]): (take, skip) goes (2,0), (7,2), (11,7), (10,11), (12,11). Answer 12 = 2 + 9 + 1. "Choose or skip" is the shape of every subset-style recursion, including the next problem.

Split an array into two parts with equal sum

Ask which version is meant. Contiguous: find an index where the left slice and right slice have equal sums. Subset: partition the elements, not necessarily contiguous, into two groups of equal sum (LC 416). Different problems, different complexity.

def split_point(nums):
    """Contiguous: return k so that sum(nums[:k]) == sum(nums[k:]), both non-empty, else -1. O(n), O(1)."""
    total, prefix = sum(nums), 0
    for i in range(len(nums) - 1):          # k = i + 1 must leave at least one element on the right
        prefix += nums[i]
        if prefix * 2 == total:
            return i + 1
    return -1
# split_point([1, 2, 3, 6]) == 3   ([1,2,3] | [6]);  split_point([1, 2, 3]) == 2  ([1,2] | [3]);  split_point([1, 2]) == -1

def can_partition(nums):
    """Subset: can the elements be split into two groups of equal sum? O(n * sum), O(sum)."""
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    reachable = {0}                          # sums achievable with the elements seen so far
    for x in nums:
        reachable |= {s + x for s in reachable if s + x <= target}     # choose x for every old sum
        if target in reachable:
            return True
    return False
# can_partition([1, 5, 11, 5]) is True (11 | 1+5+5);  can_partition([1, 2, 3, 5]) is False

The contiguous version is one pass with a running prefix sum: compare 2 * prefix with the total to avoid recomputing the right side. The subset version is a choose/skip recursion can(i, remaining) with 2ⁿ leaves; memoising on (i, remaining) gives O(n · sum) states, which is what the set version computes bottom up. Say "pseudo-polynomial": linear in the numeric value of the sum, not in its bit length. If the interviewer only says "split into two equal halves" and the array is sorted, it may just mean two slices of equal length: nums[:n//2], nums[n//2:]. Ask.

Trees

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

DFS: recursive and iterative

def inorder(node):                          # recursive, as a generator
    if node is None:
        return
    yield from inorder(node.left)
    yield node.val
    yield from inorder(node.right)
# pre-order: yield node.val first; post-order: yield it last

def preorder_iterative(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right: stack.append(node.right)   # push right first so left is processed first
        if node.left: stack.append(node.left)
    return out

def inorder_iterative(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:                         # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()                  # leftmost unvisited
        out.append(node.val)
        node = node.right                   # then its right subtree
    return out
# post-order iterative: pre-order with children pushed left first, then reverse the output

BFS: level order with a deque

from collections import deque

def level_order(root):                      # LC 102
    if root is None:
        return []
    out, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):             # exactly the nodes that are in the queue now = this level
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out

def max_depth(root):                        # LC 104, iterative: count the levels
    return len(level_order(root))

deque.popleft() is O(1); list.pop(0) is O(n) and turns BFS into O(n²). The for _ in range(len(q)) snapshot is what separates levels; without it you get one flat list. Variants that reuse this loop exactly: right side view (last value per level), average per level, zigzag (reverse alternate levels), minimum depth (stop at the first leaf).

BST: search, closest value, validate

def search_bst(node, target):               # LC 700: O(h), iterative
    while node and node.val != target:
        node = node.left if target < node.val else node.right
    return node                             # None if absent

def closest_value(root, k):
    """Value in the BST closest to k. Walk down one path, remembering the best seen. O(h) time, O(1) space."""
    best, node = root.val, root
    while node:
        if abs(node.val - k) < abs(best - k) or (abs(node.val - k) == abs(best - k) and node.val < best):
            best = node.val                 # tie-break: smaller value (say which rule you chose)
        if k < node.val:
            node = node.left                # everything right of here is even further from k
        elif k > node.val:
            node = node.right
        else:
            return node.val                 # exact hit
    return best

Why one path is enough. At each node the BST property tells you which side can contain anything closer: if k < node.val, every value in the right subtree is larger than node.val and so further from k than node.val itself. So you only ever descend toward k, like a search for k that remembers the nearest value it passed. The closest value is always on that search path. O(h): O(log n) balanced, O(n) skewed. Follow-ups: k closest values: in-order traversal is sorted, so collect it and take a window of k around bisect_left, O(n); or two stacks for predecessors and successors, O(h + k). Not a BST: no ordering to prune, full traversal, O(n). Closest as a node, not a value: track the node instead of its value. Recursive version: same logic, but say the iterative one avoids the stack on a skewed tree.

def is_valid_bst(root):                     # LC 98: every node must be inside the bounds its ancestors set
    def ok(node, lo, hi):
        if node is None:
            return True
        if not (lo < node.val < hi):
            return False
        return ok(node.left, lo, node.val) and ok(node.right, node.val, hi)
    return ok(root, float('-inf'), float('inf'))

def is_valid_bst_inorder(root):             # alternative: in-order must be strictly increasing
    prev = float('-inf')
    for v in inorder(root):
        if v <= prev:
            return False
        prev = v
    return True

Comparing each node only with its parent is the classic wrong answer: a node in the left subtree of the root can be larger than the root while still being larger than its own parent. The bounds version carries the ancestor constraints down. Use float('-inf') and float('inf') rather than None checks, and strict inequalities unless the problem allows duplicates.

Linked lists and LRU cache (breadth)

class ListNode:
    def __init__(self, val, next=None):
        self.val, self.next = val, next

def reverse_list(head):                     # LC 206: O(n), O(1)
    prev, cur = None, head
    while cur:
        nxt = cur.next                      # save before overwriting
        cur.next = prev
        prev, cur = cur, nxt
    return prev                             # the old tail is the new head

def merge_sorted(a, b):                     # LC 21: dummy head avoids special-casing the first node
    dummy = tail = ListNode(0)
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b                      # whatever is left is already sorted
    return dummy.next

from collections import OrderedDict

class LRUCache:                             # LC 146: get and put in O(1)
    def __init__(self, capacity):
        self.cap, self.d = capacity, OrderedDict()
    def get(self, key):
        if key not in self.d:
            return -1
        self.d.move_to_end(key)             # most recently used goes to the back
        return self.d[key]
    def put(self, key, value):
        if key in self.d:
            self.d.move_to_end(key)
        self.d[key] = value
        if len(self.d) > self.cap:
            self.d.popitem(last=False)      # evict the front: least recently used

Say what OrderedDict is underneath: a hash map whose entries are also linked in a doubly linked list, so moving an entry to the end and popping the front are O(1). If asked to implement it by hand, that is the structure: a dict from key to node, nodes in a doubly linked list with sentinel head and tail, unlink and append-to-tail on every access. The linked-list trap is losing the rest of the list by overwriting cur.next before saving it; the merge trap is forgetting the dummy node and writing four lines of "if result is None" bookkeeping.

Interview questions

Traps

• lo = mid in the fail branch: infinite loop when the range is two elements.
• Mixing conventions: hi = len(a) - 1 with while lo < hi, or hi = mid - 1 with an exclusive hi. Pick half-open and stay there.
• Recursion on a 10⁵-node skewed tree or a long linked list: RecursionError. Write it iteratively or say you would.
• Forgetting the dummy node in list merges and writing head special cases that have their own bugs.
• Comparing nodes instead of values: if node.left < node raises TypeError; if node.left.val < node.val is what you meant. Same for stack.pop() returning a node you then treat as a number.
• Validating a BST against the parent only. Carry (lo, hi) bounds down.
• BFS with list.pop(0), or forgetting the len(q) snapshot so the levels collapse into one list.
• Caching with lru_cache on a function that takes a list: unhashable. Index into a closed-over list and cache on the integer index.
• Returning mid after a binary search loop, or returning lo without checking it is in range and equals the target.

Do before marking this topic done

1. Type lower_bound and first_true from memory, then trace lower_bound([1,3,3,5,8], 3) and bisect_right on paper, step by step, as in the diagram. Then First Bad Version and Find Peak Element with first_true.
2. Draw a six-node BST. Write closest_value, search_bst, is_valid_bst with bounds, level_order and max_depth against it, iteratively where it matters, and say the complexity of each in terms of n and h.
3. House Robber with lru_cache, then with two variables. Trace [2, 7, 9, 3, 1].
4. Equal-sum split both ways: split_point in O(n) and can_partition in O(n · sum). State which one the interviewer's wording implies before you write a line.
5. Reverse Linked List and Merge Two Sorted Lists with a dummy head, then the OrderedDict LRU cache. Then explain the dict-plus-doubly-linked-list version out loud without coding it.

Practice: linked problems

Logged attempts feed the tracker. Open the problem in a new tab, solve in a blank editor, then log honestly.

• LC 104Maximum Depth of Binary TreeEasy
• LC 700Search in a Binary Search TreeEasy
• LC 21Merge Two Sorted ListsEasy
• LC 206Reverse Linked ListEasy
• LC 278First Bad VersionEasy
• LC 704Binary SearchEasy
• LC 102Binary Tree Level Order TraversalMedium
• LC 162Find Peak ElementMedium
• LC 146LRU CacheMedium
• LC 198House RobberMedium

← 16 · Meta's network: Clos fabrics, ECMP, BGP in the DC, FBOSS, backbone and MPLS · all topics · 18 · Linux networking toolkit →