Exercise 3: Reproducing the Wrong-Child Bug for key=15 — Possible Solution
====================================================================

THE TEST
------------------------------
    btree_search(root, 15)
    btree_search_buggy(root, 15)

RESULT
------------------------------
    btree_search(root, 15)       -> 'v15'   (correct)
    btree_search_buggy(root, 15) -> None    (WRONG -- 15 genuinely exists in the tree)

TRACING THE SHARED FIRST STEP (both versions run identical code here)
------------------------------
    i = 0
    while i < 2 and 15 > root.keys[i]:
        # i=0: 15 > root.keys[0]=10 -- True -> i becomes 1
        # i=1: 15 > root.keys[1]=20 -- False -- loop stops
    # i is now 1
    if i < 2 and 15 == root.keys[1]:   # 15 == 20 -- False
        ...                            # skipped, doesn't match either root key
    if root.leaf:                      # False -- root is an internal node
        ...                            # skipped

Both versions reach this exact same point with i=1, having correctly
determined that 15 doesn't match either key stored directly in the
root, and that a descent into a child is required.

WHERE THE TWO VERSIONS DIVERGE
------------------------------
    Correct:  return btree_search(node.children[i], key)         # children[1]
    Buggy:    return btree_search_buggy(node.children[i - 1], key) # children[0]

root.children = [left_child, mid_child, right_child]. children[1] is
mid_child (keys [12, 15, 18]) -- the subtree that genuinely CONTAINS
15, per the tree's own real structure (mid_child holds every key
between the root's own 10 and 20). children[0] is left_child (keys
[3, 5, 7]) -- a completely different, real subtree that has nothing to
do with 15 at all.

The correct version descends into mid_child, where the same search
logic runs again: i ends at 1 (since 15 > 12 but not 15 > 15), and
mid_child.keys[1] == 15 matches directly, returning 'v15'.

The buggy version instead descends into left_child, where none of its
three keys (3, 5, 7) come anywhere close to matching 15 -- the while
loop runs to completion (i ends at 3, the length of left_child's own
keys list), the equality check fails, and since left_child IS a leaf
(`if node.leaf: return None`), the function returns None -- reporting
a real, present key as missing, because the search was looking in a
real but entirely unrelated part of the tree.

WHY BOTH CHILDREN ARE "REAL" BUT ONLY ONE IS CORRECT
------------------------------
Unlike the key=5 case (where children[-1] triggers Python's own
negative-index wraparound to an out-of-range-feeling result),
children[0] for i=1 is a completely ordinary, valid, in-range Python
list index -- there's no wraparound trick happening here at all. The
bug is purely a logical one: the search invariant says children[i] is
correct, and children[i-1] is simply a different, wrong subtree that
happens to also be a real, existing child -- no crash, no obviously
invalid index, just a confidently wrong answer from searching the
wrong, but perfectly legitimate-looking, part of the tree.

WHY THIS WORKS AS AN ANSWER
------------------------------
Tracing key=15 specifically (rather than key=5, the chapter's own
headline example) demonstrates the bug isn't SPECIFICALLY about
negative indices or Python's own wraparound quirk -- that was only
one particular symptom, occurring specifically when i=0. The
UNDERLYING bug (off-by-one in which child to descend into) is wrong
for ANY value of i, including i=1, i=2, and so on -- it just happens
to manifest as a silent wraparound in one specific case and as a
plain wrong-but-valid index in every other case.