One boss, many reports
Trees as Org Charts
The analogy
A company chart: one person at the top, each person has reports below them, and nobody has two bosses. To find someone you start at the top and take the right branch down — you never search the whole company.
Visualizer
Descending the org chart
step 1 / 7A search tree. Everything left of a node is smaller; everything right is bigger.searching for 40
📖 In depth — the full reference
BST operations — balanced vs neglected
| operation | balanced | degenerate (sorted inserts) | note |
|---|---|---|---|
| search | O(log n) | O(n) | the tree became a linked list in disguise |
| insert | O(log n) | O(n) | same walk as search, plus one link |
| delete | O(log n) | O(n) | 3 cases: leaf, one child, two children (swap with in-order successor) |
| min / max | O(log n) | O(n) | walk all the way left / right |
| in-order walk | O(n) | O(n) | visits every value IN SORTED ORDER — the party trick hashes cannot do |
| range query [a, b] | O(log n + k) | O(n) | k = matches returned; the reason databases use trees |
Tree vocabulary you now own
- root (the top), leaf (no children), height (longest root→leaf path), depth of a node (distance from root), subtree (any node and everything under it).
- BST invariant: EVERYTHING in the left subtree is smaller, EVERYTHING right is bigger — recursively, not just the immediate children.
- A BST's power is the invariant, and its weakness is neglect: feed it sorted input and it degenerates. Self-balancing trees (AVL — Module 5) rotate to prevent this.
- In-order = left, node, right. Pre-order copies trees; post-order deletes them; level-order is BFS with a queue.
Python specifics
- No built-in BST. The standard-library answer to "sorted + fast" is bisect on a sorted list (O(log n) find, O(n) insert) or heapq for priority access (Module 5).
- The de-facto third-party answer is sortedcontainers.SortedList — O(log n) everything, no tree in sight (it is clever chunked lists).
- Nodes here are dicts {v, left, right} to match the exercise; a real implementation would be a class with insert/search methods.
def search(node, t):
if node is None:
return None
if t == node.value:
return node
if t < node.value:
return search(node.left, t)
return search(node.right, t)
# each comparison discards half the treeCheck yourself
Search in a balanced BST costs…
Practice — write it yourself
bst_contains(root, t): nodes are {"v", "left", "right"} dicts. Use the BST rule — smaller goes left, bigger goes right — never search both sides.
Python 3 · runs in your browser · your draft is saved locally
📝 My notessaved in this browser