Trees and Binary Search Trees Questions

      50
     /  \
   30    70
  /  \
20    40

chain (keys 1 to 5 inserted in order)      balanced (same keys)
1                                              3
 \                                            / \
  2                                          2   4
   \                                        /     \
    3                                      1       5
     \
      4
       \
        5

import random


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


def bst_insert(root, key):
    """Returns (root, comparisons)."""
    if root is None:
        return Node(key), 0
    cur, steps = root, 0
    while True:
        steps += 1
        side = "left" if key < cur.key else "right"
        nxt = getattr(cur, side)
        if nxt is None:
            setattr(cur, side, Node(key))
            return root, steps
        cur = nxt


def bst_find(root, key):
    cur, steps = root, 0
    while cur:
        steps += 1
        if key == cur.key:
            return True, steps
        cur = cur.left if key < cur.key else cur.right
    return False, steps


def bst_range(node, lo, hi, out, visited):
    """Keys in [lo, hi] in sorted order; skips subtrees that cannot contain any."""
    if node is None:
        return
    visited[0] += 1
    if lo < node.key:
        bst_range(node.left, lo, hi, out, visited)
    if lo <= node.key <= hi:
        out.append(node.key)
    if node.key < hi:
        bst_range(node.right, lo, hi, out, visited)


def bst_height(root):
    h, level = -1, [root] if root else []
    while level:
        h += 1
        level = [c for n in level for c in (n.left, n.right) if c]
    return h


def lower_bound(a, x):
    """First index with a[i] >= x, and the comparisons used (binary search)."""
    lo, hi, steps = 0, len(a), 0
    while lo < hi:
        steps += 1
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo, steps


if __name__ == "__main__":
    random.seed(5)
    keys = random.sample(range(100_000), 1000)       # distinct keys, random arrival order

    root = None
    for k in keys:
        root, _ = bst_insert(root, k)
    table = {k: True for k in keys}                    # hash map
    arr = sorted(keys)                                 # sorted array

    # Lookup: average comparisons over every stored key
    bst_avg = sum(bst_find(root, k)[1] for k in keys) / len(keys)
    arr_avg = sum(lower_bound(arr, k)[1] for k in keys) / len(keys)
    print(f"lookup, average comparisons: BST {bst_avg:.1f} (height {bst_height(root)}), sorted array {arr_avg:.1f}, hash map: 1 hash + about 1 probe")

    # Insert one new key that lands in the middle of the order
    new = 50_001
    _, bst_steps = bst_insert(root, new)
    idx, find_steps = lower_bound(arr, new)
    print(f"insert {new}: BST {bst_steps} comparisons, sorted array {find_steps} comparisons + {len(arr) - idx} elements shifted")

    # Range query: keys between 40000 and 41999
    lo, hi = 40_000, 41_999
    out, visited = [], [0]
    bst_range(root, lo, hi, out, visited)
    start, c1 = lower_bound(arr, lo)
    end, c2 = lower_bound(arr, hi + 1)
    in_hash = sorted(k for k in table if lo <= k <= hi)
    assert out == arr[start:end] == in_hash
    print(f"range [{lo}, {hi}] returns {len(out)} keys:")
    print(f"  BST visits {visited[0]} nodes, sorted array uses {c1 + c2} comparisons + {end - start} copies, hash map examines all {len(table)} entries, then sorts the {len(in_hash)} hits")
    print("smallest 3 keys in order:", arr[:3], "| BST in-order gives the same without a sort step")

lookup, average comparisons: BST 11.8 (height 20), sorted array 10.0, hash map: 1 hash + about 1 probe
insert 50001: BST 13 comparisons, sorted array 10 comparisons + 473 elements shifted
range [40000, 41999] returns 25 keys:
  BST visits 40 nodes, sorted array uses 19 comparisons + 25 copies, hash map examines all 1000 entries, then sorts the 25 hits
smallest 3 keys in order: [9, 57, 86] | BST in-order gives the same without a sort step

import random


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


def bst_insert(root, key):
    if root is None:
        return Node(key)
    cur = root
    while True:
        side = "left" if key < cur.key else "right"
        nxt = getattr(cur, side)
        if nxt is None:
            setattr(cur, side, Node(key))
            return root
        cur = nxt


def bst_range_visits(node, lo, hi, visited):
    """Keys of every node the range walk enters, in visiting order."""
    if node is None:
        return
    visited.append(node.key)
    if lo < node.key:
        bst_range_visits(node.left, lo, hi, visited)
    if node.key < hi:
        bst_range_visits(node.right, lo, hi, visited)


def lookup_path(root, key):
    path, cur = [], root
    while cur:
        path.append(cur.key)
        if key == cur.key:
            break
        cur = cur.left if key < cur.key else cur.right
    return path


random.seed(5)
keys = random.sample(range(100_000), 1000)
root = None
for k in keys:
    root = bst_insert(root, k)
lo, hi = 40_000, 41_999
visited = []
bst_range_visits(root, lo, hi, visited)
inside = [k for k in visited if lo <= k <= hi]
outside = [k for k in visited if not lo <= k <= hi]
path_lo, path_hi = lookup_path(root, lo), lookup_path(root, hi)
print(f"range walk visited {len(visited)} nodes: {len(inside)} inside the range, {len(outside)} outside")
print(f"lookup path for {lo} has {len(path_lo)} nodes, lookup path for {hi} has {len(path_hi)} nodes")
print("every outside node lies on one of the two lookup paths:", all(k in path_lo or k in path_hi for k in outside))

# A hash table with 8 slots and linear probing: a probe is one look at one slot.
slots = [None] * 8


def put(key):
    i = key % 8                       # the hash function: key modulo the table size
    probes = 1
    while slots[i] is not None:       # collision: the slot is taken, try the next one
        i = (i + 1) % 8
        probes += 1
    slots[i] = key
    return probes


def get(key):
    i, probes = key % 8, 1
    while slots[i] != key:
        i = (i + 1) % 8
        probes += 1
    return probes


for key in (10, 18, 3, 26, 7):
    print(f"put {key}: hash slot {key % 8}, probes {put(key)}")
print("table:", slots)
print("probes to find each key:", {key: get(key) for key in (10, 18, 3, 26, 7)})

# A chain versus a balanced tree on the same five keys.
chain = None
for k in (1, 2, 3, 4, 5):
    chain = bst_insert(chain, k)
balanced = None
for k in (3, 2, 4, 1, 5):
    balanced = bst_insert(balanced, k)
print("lookup path for 5 in the chain:", lookup_path(chain, 5), "| in the balanced tree:", lookup_path(balanced, 5))

range walk visited 40 nodes: 25 inside the range, 15 outside
lookup path for 40000 has 13 nodes, lookup path for 41999 has 16 nodes
every outside node lies on one of the two lookup paths: True
put 10: hash slot 2, probes 1
put 18: hash slot 2, probes 2
put 3: hash slot 3, probes 2
put 26: hash slot 2, probes 4
put 7: hash slot 7, probes 1
table: [None, None, 10, 18, 3, 26, None, 7]
probes to find each key: {10: 1, 18: 2, 3: 2, 26: 4, 7: 1}
lookup path for 5 in the chain: [1, 2, 3, 4, 5] | in the balanced tree: [3, 4, 5]

        50
       /  \
     30    70
    /  \
  20    40

0 (empty) -> 1 -> 2 -> 3 -> 4 -> 5 -+-> 6  (put 60)  -> 8  (remove 50 from 6)
                                    +-> 7  (remove 30)

import random


class Node:
    __slots__ = ("key", "val", "left", "right")

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


def put(root, key, val):
    """Return (new_root, nodes_created). Copies only the path from the root to the key."""
    path, node = [], root
    while node is not None and node.key != key:
        went_left = key < node.key
        path.append((node, went_left))
        node = node.left if went_left else node.right
    if node is None:
        child = Node(key, val)
    else:
        child = Node(key, val, node.left, node.right)     # overwrite: copy the node, share its subtrees
    created = 1
    for parent, went_left in reversed(path):
        child = (Node(parent.key, parent.val, child, parent.right) if went_left
                 else Node(parent.key, parent.val, parent.left, child))
        created += 1
    return child, created


def remove(root, key):
    path, node = [], root
    while node is not None and node.key != key:
        went_left = key < node.key
        path.append((node, went_left))
        node = node.left if went_left else node.right
    if node is None:
        return root, 0                                    # absent: the old version is reused as is
    created = 0
    if node.left is None:
        child = node.right
    elif node.right is None:
        child = node.left
    else:                                                 # two children: promote the in-order successor
        spine, succ = [], node.right
        while succ.left is not None:
            spine.append(succ)
            succ = succ.left
        right = succ.right
        for p in reversed(spine):
            right = Node(p.key, p.val, right, p.right)
            created += 1
        child = Node(succ.key, succ.val, node.left, right)
        created += 1
    for parent, went_left in reversed(path):
        child = (Node(parent.key, parent.val, child, parent.right) if went_left
                 else Node(parent.key, parent.val, parent.left, child))
        created += 1
    return child, created


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


def items(root):
    out, stack = [], []
    while stack or root is not None:
        while root is not None:
            stack.append(root)
            root = root.left
        root = stack.pop()
        out.append((root.key, root.val))
        root = root.right
    return out


def node_ids(*roots):
    seen, stack = set(), [r for r in roots if r is not None]
    while stack:
        n = stack.pop()
        if id(n) not in seen:
            seen.add(id(n))
            stack += [c for c in (n.left, n.right) if c is not None]
    return seen


class VersionedMap:
    def __init__(self):
        self.roots = [None]                    # roots[v] is the tree of version v; version 0 is empty

    def put(self, version, key, val):
        root, created = put(self.roots[version], key, val)
        self.roots.append(root)
        return len(self.roots) - 1, created

    def remove(self, version, key):
        root, created = remove(self.roots[version], key)
        self.roots.append(root)
        return len(self.roots) - 1, created

    def get(self, version, key):
        return get(self.roots[version], key)


# 1. a short history
vm = VersionedMap()
v = 0
for k in (50, 30, 70, 20, 40):
    v, made = vm.put(v, k, f"v{len(vm.roots)}")
    print(f"put {k} -> version {v}, new nodes {made}, nodes in that version {len(items(vm.roots[v]))}")
v6, made = vm.put(5, 60, "late")          # branch A: update version 5
print(f"put 60 on version 5 -> version {v6}, new nodes {made}")
v7, made = vm.remove(5, 30)               # branch B: also update version 5
print(f"remove 30 from version 5 -> version {v7}, new nodes {made}")
for ver in (5, 6, 7):
    print(f"version {ver} items:", items(vm.roots[ver]))
print("get(3, 30) =", vm.get(3, 30), "| get(5, 30) =", vm.get(5, 30), "| get(7, 30) =", vm.get(7, 30))
# a two-child delete whose successor is NOT the right child: the nodes between them are the spine
v8, made = vm.remove(6, 50)               # version 6: 50 has right child 70, and 70 has left child 60
print(f"remove 50 from version 6 -> version {v8}, new nodes {made}")
print("version 8 items:", items(vm.roots[8]))
print(f"versions 6 and 8 hold {len(node_ids(vm.roots[6]))} and {len(node_ids(vm.roots[8]))} nodes, "
      f"{len(node_ids(vm.roots[6]) & node_ids(vm.roots[8]))} are the same objects")
for a_, b_ in ((5, 6), (5, 7)):
    ids_a, ids_b = node_ids(vm.roots[a_]), node_ids(vm.roots[b_])
    print(f"versions {a_} and {b_} hold {len(ids_a)} and {len(ids_b)} nodes, {len(ids_a & ids_b)} are the same objects")

# a rotation is local too: left rotation at the root of a small tree, written in the same copy-don't-edit style
def rotate_left(node):
    pivot = node.right
    new_left = Node(node.key, node.val, node.left, pivot.left)
    return Node(pivot.key, pivot.val, new_left, pivot.right)


def preorder(root):
    out, stack = [], [root]
    while stack:
        n = stack.pop()
        if n is not None:
            out.append(n.key)
            stack += [n.right, n.left]
    return out


def height(root):                         # edges: empty tree -1, single node 0
    best, stack = -1, [(root, 0)]
    while stack:
        n, d = stack.pop()
        if n is not None:
            best = max(best, d)
            stack += [(n.left, d + 1), (n.right, d + 1)]
    return best


tree = None
for k in (10, 20, 15, 30, 40):
    tree, _ = put(tree, k, k)
turned = rotate_left(tree)
print(f"\nbefore rotation: preorder {preorder(tree)}, height {height(tree)}")
print(f"after rotation : preorder {preorder(turned)}, height {height(turned)}")
print(f"old tree still : preorder {preorder(tree)}")
new_nodes = len(node_ids(turned) - node_ids(tree))
print(f"nodes created by the rotation: {new_nodes}; nodes shared with the old tree: "
      f"{len(node_ids(turned) & node_ids(tree))}")

# 2. every old version stays correct: random operations on random versions against full copies
rng = random.Random(9)
histories = set()
for _ in range(200):
    vm, copies = VersionedMap(), [{}]
    for step in range(30):
        base = rng.randrange(len(copies))
        key = rng.randrange(12)
        new = dict(copies[base])
        if rng.random() < 0.6:
            vm.put(base, key, step)
            new[key] = step
        else:
            vm.remove(base, key)
            new.pop(key, None)
        copies.append(new)
        for ver, expected in enumerate(copies):
            assert dict(items(vm.roots[ver])) == expected
    histories.add(tuple(map(lambda d: tuple(sorted(d.items())), copies)))
print("\nrandom branching histories checked:", len(histories), "distinct")

# the same check on an in-place update, which is wrong on purpose
def put_in_place(root, key, val):
    if root is None:
        return Node(key, val)
    node = root
    while True:
        if key == node.key:
            node.val = val
            return root
        side = "left" if key < node.key else "right"
        nxt = getattr(node, side)
        if nxt is None:
            setattr(node, side, Node(key, val))
            return root
        node = nxt


first = put_in_place(None, 50, "a")
second = put_in_place(first, 30, "b")
print("in-place update: version 1 should hold [(50, 'a')] but holds", items(first))

# 3. memory per update: random order, sorted order, and copying the whole tree each time
n = 1000
keys = random.Random(2).sample(range(100_000), n)
for label, order in (("random order", keys), ("ascending order", sorted(keys))):
    vm, v, created_total, full_copy_total = VersionedMap(), 0, 0, 0
    for i, k in enumerate(order):
        v, made = vm.put(v, k, i)
        created_total += made
        full_copy_total += i + 1
    distinct = len(node_ids(*vm.roots))
    print(f"{label:>15}: {n} versions, path-copy nodes {created_total:,} (distinct alive {distinct:,}), "
          f"whole-tree copies {full_copy_total:,}")

put 50 -> version 1, new nodes 1, nodes in that version 1
put 30 -> version 2, new nodes 2, nodes in that version 2
put 70 -> version 3, new nodes 2, nodes in that version 3
put 20 -> version 4, new nodes 3, nodes in that version 4
put 40 -> version 5, new nodes 3, nodes in that version 5
put 60 on version 5 -> version 6, new nodes 3
remove 30 from version 5 -> version 7, new nodes 2
version 5 items: [(20, 'v4'), (30, 'v2'), (40, 'v5'), (50, 'v1'), (70, 'v3')]
version 6 items: [(20, 'v4'), (30, 'v2'), (40, 'v5'), (50, 'v1'), (60, 'late'), (70, 'v3')]
version 7 items: [(20, 'v4'), (40, 'v5'), (50, 'v1'), (70, 'v3')]
get(3, 30) = v2 | get(5, 30) = v2 | get(7, 30) = None
remove 50 from version 6 -> version 8, new nodes 2
version 8 items: [(20, 'v4'), (30, 'v2'), (40, 'v5'), (60, 'late'), (70, 'v3')]
versions 6 and 8 hold 6 and 5 nodes, 3 are the same objects
versions 5 and 6 hold 5 and 6 nodes, 3 are the same objects
versions 5 and 7 hold 5 and 4 nodes, 2 are the same objects

before rotation: preorder [10, 20, 15, 30, 40], height 3
after rotation : preorder [20, 10, 15, 30, 40], height 2
old tree still : preorder [10, 20, 15, 30, 40]
nodes created by the rotation: 2; nodes shared with the old tree: 3

random branching histories checked: 200 distinct
in-place update: version 1 should hold [(50, 'a')] but holds [(30, 'b'), (50, 'a')]
   random order: 1000 versions, path-copy nodes 12,792 (distinct alive 12,792), whole-tree copies 500,500
ascending order: 1000 versions, path-copy nodes 500,500 (distinct alive 500,500), whole-tree copies 500,500

python3.12 persistent_bst.py

import io
import os
import random
import sys
import tempfile

NULL = "#"


class Node:
    __slots__ = ("val", "left", "right")

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


def write_tree(root, out, batch=4096, stats=None):
    """Iterative preorder; tokens leave memory in batches of `batch`."""
    stack, buf = [root], []
    while stack:
        if stats is not None:
            stats["max_stack"] = max(stats.get("max_stack", 0), len(stack))
        node = stack.pop()
        if node is None:
            buf.append(NULL)
        else:
            buf.append(str(node.val))
            stack.append(node.right)   # pushed first so the left child is popped first
            stack.append(node.left)
        if stats is not None:
            stats["max_buffer"] = max(stats.get("max_buffer", 0), len(buf))
        if len(buf) >= batch:
            out.write(" ".join(buf) + " ")
            buf.clear()
    out.write(" ".join(buf) + " ")


def iter_tokens(fp, block=64 * 1024, stats=None):
    """Yield space-separated tokens (lazily: a generator, so each `yield` hands one token to the caller
    and pauses), reading `block` characters at a time."""
    carry = ""
    while True:
        chunk = fp.read(block)
        if not chunk:
            break
        parts = (carry + chunk).split(" ")
        carry = parts.pop()            # the last piece may be a token cut in half
        if stats is not None:
            stats["max_tokens_alive"] = max(stats.get("max_tokens_alive", 0), len(parts))
        for p in parts:
            if p:
                yield p
    if carry:
        yield carry


def naive_tokens(fp, block):
    """Broken on purpose: splits every block on its own and drops the carry."""
    while chunk := fp.read(block):
        yield from chunk.split()


def read_tree(tokens, trace=None, stats=None):
    """Rebuild from a token iterator using a stack of nodes whose right slot is still open.
    State: `parent` and `filling_left` name the slot the next token fills."""
    it = iter(tokens)
    first = next(it, None)
    if first is None:
        raise ValueError("tokens ended before the tree was complete")
    if first == NULL:
        if next(it, None) is not None:
            raise ValueError("extra tokens after the tree is complete")
        return None
    root = Node(int(first))
    parent, filling_left = root, True
    right_open = []
    if trace is not None:
        trace.append(f"token {first:>2}: next slot = left of {parent.val}, right_open = []")
    for tok in it:
        if parent is None:
            raise ValueError("extra tokens after the tree is complete")
        child = None if tok == NULL else Node(int(tok))
        if filling_left:
            parent.left = child
            right_open.append(parent)
        else:
            parent.right = child
        if stats is not None:   # measured before the pop, when the stack is at its fullest
            stats["max_open"] = max(stats.get("max_open", 0), len(right_open))
        if child is not None:
            parent, filling_left = child, True
        elif right_open:
            parent, filling_left = right_open.pop(), False
        else:
            parent = None
        if trace is not None:
            slot = "none, tree complete" if parent is None else f"{'left' if filling_left else 'right'} of {parent.val}"
            trace.append(f"token {tok:>2}: next slot = {slot}, right_open = {[n.val for n in right_open]}")
    if parent is not None:
        raise ValueError("tokens ended before the tree was complete")
    return root


def same_tree(a, b):
    stack = [(a, b)]
    while stack:
        x, y = stack.pop()
        if x is None or y is None:
            if x is not y:
                return False
            continue
        if x.val != y.val:
            return False
        stack.append((x.left, y.left))
        stack.append((x.right, y.right))
    return True


def left_chain(n):
    root = cur = Node(1)
    for v in range(2, n + 1):
        cur.left = Node(v)
        cur = cur.left
    return root


def random_tree(n, seed):
    rng = random.Random(seed)
    root = Node(1)
    slots = [(root, 0), (root, 1)]
    for v in range(2, n + 1):
        i = rng.randrange(len(slots))
        slots[i], slots[-1] = slots[-1], slots[i]
        parent, side = slots.pop()
        node = Node(v)
        setattr(parent, "left" if side == 0 else "right", node)
        slots += [(node, 0), (node, 1)]
    return root


def chain(n):
    root = cur = Node(1)
    for v in range(2, n + 1):
        cur.right = Node(v)
        cur = cur.right
    return root


# 1. a small tree, what the file holds
small = Node(1, Node(2), Node(3, Node(4), None))
buf = io.StringIO()
write_tree(small, buf)
print("small tree file:", repr(buf.getvalue()))
steps = []
buf.seek(0)
read_tree(iter_tokens(buf), trace=steps)
print("\n".join(steps))

# 2. round trips, including block sizes that cut tokens in half
cases = 0
for seed in range(200):
    n = random.Random(seed).randint(0, 40)
    t = random_tree(n, seed) if n else None
    s = io.StringIO()
    write_tree(t, s, batch=3)
    for block in (1, 2, 5, 64 * 1024):
        s.seek(0)
        assert same_tree(read_tree(iter_tokens(s, block)), t)
        cases += 1
print("round trips checked:", cases)

big_tokens = io.StringIO()
write_tree(Node(1234567, Node(7654321)), big_tokens)
big_tokens.seek(0)
good = list(iter_tokens(big_tokens, 4))
big_tokens.seek(0)
bad = list(naive_tokens(big_tokens, 4))
print("carry reader :", good)
print("no-carry read:", bad)

# 3. memory, counted in tokens instead of bytes: 300,000 nodes
N = 300_000
tree = random_tree(N, 1)
with tempfile.TemporaryDirectory() as d:
    path = os.path.join(d, "tree.txt")
    write_stats = {}
    with open(path, "w") as f:
        write_tree(tree, f, stats=write_stats)
    size = os.path.getsize(path)

    with open(path) as f:
        n_tokens = len(f.read().split())

    stream_stats = {}
    with open(path) as f:
        count = sum(1 for _ in iter_tokens(f, stats=stream_stats))

    rebuild_stats = {}
    with open(path) as f:
        rebuilt = read_tree(iter_tokens(f), stats=rebuild_stats)
    assert same_tree(rebuilt, tree) and count == n_tokens

print(f"nodes {N:,}  tokens {n_tokens:,} (= 2n+1: {n_tokens == 2 * N + 1})  file bytes {size:,}")
print(f"writer: at most {write_stats['max_buffer']:,} tokens buffered, at most {write_stats['max_stack']:,} entries on its stack")
print(f"read().split(): {n_tokens:,} tokens alive at once")
print(f"streamed reader: at most {stream_stats['max_tokens_alive']:,} tokens alive at once (one 64 KiB block)")
print(f"read_tree: right_open never held more than {rebuild_stats['max_open']:,} nodes")
for name, shape in (("right-leaning chain of 1000", chain(1000)), ("left-leaning chain of 1000", left_chain(1000))):
    s, st = io.StringIO(), {}
    write_tree(shape, s)
    s.seek(0)
    read_tree(iter_tokens(s), stats=st)
    print(f"  {name}: right_open peaks at {st.get('max_open', 0):,}")

# 4. a chain 1,000,000 deep: no recursion anywhere
with tempfile.TemporaryDirectory() as d:
    path = os.path.join(d, "chain.txt")
    chain_tree = chain(1_000_000)
    with open(path, "w") as f:
        write_tree(chain_tree, f)
    with open(path) as f:
        again = read_tree(iter_tokens(f))
    print("1,000,000-deep chain round trip:", same_tree(again, chain_tree))

# 4b. malformed input, and a recursive writer on a deep chain
for text in ("", "# 5", "1 #", "1 # # 5"):
    try:
        read_tree(iter_tokens(io.StringIO(text)))
        outcome = "accepted"
    except ValueError as err:
        outcome = f"ValueError: {err}"
    print(f"{text!r:10} -> {outcome}")


def recursive_write(node, out):
    if node is None:
        out.append(NULL)
        return
    out.append(str(node.val))
    recursive_write(node.left, out)
    recursive_write(node.right, out)


try:
    recursive_write(chain(2000), [])
except RecursionError:
    print("recursive writer on a 2000-deep chain: RecursionError")

# 5. file size for ten million nodes labelled 1..10,000,000
n = 10_000_000
digits = sum(len(str(v)) for v in range(1, n + 1))
print(f"10,000,000 nodes: tokens {2 * n + 1:,}, bytes {digits + n + 2 * (n + 1):,}")
print(f"a list of those tokens needs {8 * (2 * n + 1):,} bytes for its 8-byte slots alone; "
      f"one 7-character token string is {sys.getsizeof('1234567')} bytes on this build")

small tree file: '1 2 # # 3 4 # # # '
token  1: next slot = left of 1, right_open = []
token  2: next slot = left of 2, right_open = [1]
token  #: next slot = right of 2, right_open = [1]
token  #: next slot = right of 1, right_open = []
token  3: next slot = left of 3, right_open = []
token  4: next slot = left of 4, right_open = [3]
token  #: next slot = right of 4, right_open = [3]
token  #: next slot = right of 3, right_open = []
token  #: next slot = none, tree complete, right_open = []
round trips checked: 800
carry reader : ['1234567', '7654321', '#', '#', '#']
no-carry read: ['1234', '567', '7654', '321', '#', '#', '#']
nodes 300,000  tokens 600,001 (= 2n+1: True)  file bytes 2,588,897
writer: at most 4,096 tokens buffered, at most 29 entries on its stack
read().split(): 600,001 tokens alive at once
streamed reader: at most 15,217 tokens alive at once (one 64 KiB block)
read_tree: right_open never held more than 28 nodes
  right-leaning chain of 1000: right_open peaks at 1
  left-leaning chain of 1000: right_open peaks at 1,000
1,000,000-deep chain round trip: True
''         -> ValueError: tokens ended before the tree was complete
'# 5'      -> ValueError: extra tokens after the tree is complete
'1 #'      -> ValueError: tokens ended before the tree was complete
'1 # # 5'  -> ValueError: extra tokens after the tree is complete
recursive writer on a 2000-deep chain: RecursionError
10,000,000 nodes: tokens 20,000,001, bytes 98,888,899
a list of those tokens needs 160,000,008 bytes for its 8-byte slots alone; one 7-character token string is 48 bytes on this build

python3.12 stream_tree_to_disk.py

        50
      /    \
    30      70
   /  \       \
  20   60      80

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


def local_only(node):
    """Wrong: compares each node with its immediate children only."""
    if node is None:
        return True
    if node.left and not node.left.key < node.key:
        return False
    if node.right and not node.right.key > node.key:
        return False
    return local_only(node.left) and local_only(node.right)


def range_check(node, low=float("-inf"), high=float("inf"), seen=None, steps=None):
    if node is None:
        return True
    if seen is not None:
        seen.append(node.key)
    if steps is not None:
        steps.append(f"{node.key} must be in ({low}, {high}): {low < node.key < high}")
    if not low < node.key < high:
        return False
    return (range_check(node.left, low, node.key, seen, steps)
            and range_check(node.right, node.key, high, seen, steps))


def inorder_check(root, seen=None):
    stack, cur, previous = [], root, None
    while stack or cur:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        if seen is not None:
            seen.append(cur.key)
        if previous is not None and cur.key <= previous:
            return False
        previous = cur.key
        cur = cur.right
    return True


#        50
#       /  \
#     30    70
#    /  \     \
#  20    60    80      60 is a right child of 30, yet it sits left of 50
trap = Node(50, Node(30, Node(20), Node(60)), Node(70, None, Node(80)))
print("trap tree: local_only =", local_only(trap),
      "| range =", range_check(trap), "| inorder =", inorder_check(trap))

#     50
#    /
#  60          every key on the left of 50 must be below 50
#  /
# 55
# /
# 52
leaning = Node(50, Node(60, Node(55, Node(52))))
steps, order = [], []
range_check(trap, steps=steps)
inorder_check(trap, order)
print("range method steps on the trap tree:")
print("\n".join("  " + s for s in steps))
print("inorder method on the trap tree:",
      "; ".join(f"{p} then {c}: {'ok' if c > p else 'NOT increasing'}" for p, c in zip(order, order[1:])))

#   50
#     \
#      70          40 is in the right subtree of 50 but is smaller than 50
#     /
#    60
#   /
#  40
deep_right = Node(50, None, Node(70, Node(60, Node(40))))
by_range, by_inorder = [], []
print("deep-right tree: range =", range_check(deep_right, seen=by_range),
      "| inorder =", inorder_check(deep_right, seen=by_inorder))
print("  range examined keys  :", by_range)
print("  inorder examined keys:", by_inorder)

by_range, by_inorder = [], []
print("leaning tree: range =", range_check(leaning, seen=by_range),
      "| inorder =", inorder_check(leaning, seen=by_inorder))
print("  range examined keys  :", by_range)
print("  inorder examined keys:", by_inorder)

trap tree: local_only = True | range = False | inorder = False
range method steps on the trap tree:
  50 must be in (-inf, inf): True
  30 must be in (-inf, 50): True
  20 must be in (-inf, 30): True
  60 must be in (30, 50): False
inorder method on the trap tree: 20 then 30: ok; 30 then 60: ok; 60 then 50: NOT increasing
deep-right tree: range = False | inorder = False
  range examined keys  : [50, 70, 60, 40]
  inorder examined keys: [50, 40]
leaning tree: range = False | inorder = False
  range examined keys  : [50, 60]
  inorder examined keys: [52, 55, 60, 50]

Insert 1,2,3,4,5          Insert 3,1,4,2,5
1                         3
    R:2                       L:1
        R:3                       R:2
            R:4               R:4
                R:5               R:5

import random

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

def insert(root, key):
    """Iterative insert. Returns (root, comparisons made)."""
    comparisons = 0
    if root is None:
        return Node(key), 0
    cur = root
    while True:
        comparisons += 1
        if key < cur.key:
            if cur.left is None:
                cur.left = Node(key)
                return root, comparisons
            cur = cur.left
        else:
            if cur.right is None:
                cur.right = Node(key)
                return root, comparisons
            cur = cur.right

def search_cost(root, key):
    """Number of nodes visited while searching for key."""
    visited = 0
    cur = root
    while cur:
        visited += 1
        if key == cur.key:
            return visited
        cur = cur.left if key < cur.key else cur.right
    return visited

def height(root):
    """Height = number of nodes on the longest root-to-leaf path (empty tree = 0). Iterative level count."""
    if root is None:
        return 0
    level, h = [root], 0
    while level:
        h += 1
        level = [c for n in level for c in (n.left, n.right) if c]
    return h

def draw(node, indent="", tag=""):
    """Print the tree sideways: children are indented under their parent, L: / R: mark the side."""
    print(indent + tag + str(node.key))
    if node.left:
        draw(node.left, indent + "    ", "L:")
    if node.right:
        draw(node.right, indent + "    ", "R:")

def build(keys):
    root, total = None, 0
    for k in keys:
        root, c = insert(root, k)
        total += c
    return root, total

def from_sorted(keys, lo=0, hi=None):
    """Build a perfectly balanced BST from sorted keys (recursion depth ~log n)."""
    if hi is None:
        hi = len(keys)
    if lo >= hi:
        return None
    mid = (lo + hi) // 2
    n = Node(keys[mid])
    n.left = from_sorted(keys, lo, mid)
    n.right = from_sorted(keys, mid + 1, hi)
    return n

small = [1, 2, 3, 4, 5]
print("Insert 1,2,3,4,5 in that order:")
draw(build(small)[0])
print("Insert 3,1,4,2,5:")
draw(build([3, 1, 4, 2, 5])[0])

N = 1000
sorted_keys = list(range(1, N + 1))
shuffled = sorted_keys[:]
random.Random(7).shuffle(shuffled)
for name, keys in [("sorted", sorted_keys), ("shuffled", shuffled)]:
    root, total = build(keys)
    print(f"{name:9} n={N} height={height(root)} insert comparisons={total} search(1000) visits={search_cost(root, N)}")
bal = from_sorted(sorted_keys)
print(f"{'rebuilt':9} n={N} height={height(bal)} search(1000) visits={search_cost(bal, N)}")

# recursion limit on a skewed tree
import sys
def inorder_recursive(n, out):
    if n:
        inorder_recursive(n.left, out)
        out.append(n.key)
        inorder_recursive(n.right, out)
print("recursion limit:", sys.getrecursionlimit())
skew, _ = build(list(range(1, 2001)))
try:
    inorder_recursive(skew, [])
    print("recursive inorder on 2000-node skewed tree: ok")
except RecursionError:
    print("recursive inorder on 2000-node skewed tree: RecursionError")

Insert 1,2,3,4,5 in that order:
1
    R:2
        R:3
            R:4
                R:5
Insert 3,1,4,2,5:
3
    L:1
        R:2
    R:4
        R:5
sorted    n=1000 height=1000 insert comparisons=499500 search(1000) visits=1000
shuffled  n=1000 height=25 insert comparisons=11972 search(1000) visits=7
rebuilt   n=1000 height=10 search(1000) visits=9
recursion limit: 1000
recursive inorder on 2000-node skewed tree: RecursionError

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.h = 1                      # height in nodes of the subtree rooted here


def h(n):
    return n.h if n else 0


def update(n):
    n.h = 1 + max(h(n.left), h(n.right))


def rotate_left(x):
    """x's right child y moves up; x becomes y's left child. In-order stays the same."""
    y = x.right
    x.right, y.left = y.left, x
    update(x)
    update(y)
    return y


def rotate_right(y):
    x = y.left
    y.left, x.right = x.right, y
    update(y)
    update(x)
    return x


def insert(n, key):
    """AVL insert: ordinary BST insert, then rotate when a node's two sides differ in height by 2."""
    if n is None:
        return Node(key)
    if key < n.key:
        n.left = insert(n.left, key)
    else:
        n.right = insert(n.right, key)
    update(n)
    balance = h(n.left) - h(n.right)
    if balance > 1:
        if h(n.left.left) < h(n.left.right):
            n.left = rotate_left(n.left)
        return rotate_right(n)
    if balance < -1:
        if h(n.right.right) < h(n.right.left):
            n.right = rotate_right(n.right)
        return rotate_left(n)
    return n


def draw(node, indent="", tag=""):
    print(indent + tag + str(node.key))
    if node.left:
        draw(node.left, indent + "    ", "L:")
    if node.right:
        draw(node.right, indent + "    ", "R:")


def inorder(n):
    return inorder(n.left) + [n.key] + inorder(n.right) if n else []


chain = Node(1)
chain.right = Node(2)
chain.right.right = Node(3)
update(chain.right)
update(chain)
print("chain 1,2,3, height", h(chain))
draw(chain)
chain = rotate_left(chain)
print("after one left rotation at 1, height", h(chain))
draw(chain)
print("in-order still", inorder(chain))

root = None
for k in range(1, 1001):
    root = insert(root, k)
print("AVL, keys 1..1000 inserted in sorted order: height", h(root), "in nodes")
assert inorder(root) == list(range(1, 1001))

chain 1,2,3, height 3
1
    R:2
        R:3
after one left rotation at 1, height 2
2
    L:1
    R:3
in-order still [1, 2, 3]
AVL, keys 1..1000 inserted in sorted order: height 10 in nodes

python3 skewed_bst_demo.py
python3 avl_rotation_demo.py