The Product Catalog That Never Finished
#backend-performance — warehouse scanner timeouts
PM: 100,000 SKUs, linear search through an unsorted array. Average 50,000 comparisons per scan. 30–45 seconds per lookup.
The trap: findBySku() is O(n). A BST gives O(log n) — but only if insertion order keeps the tree balanced.
Your task
Implement `insert()` and `search()` in `BinarySearchTreeCatalog` inside `product_catalog.py`: walk the tree by SKU, go left/right, track comparisons.
Book: BST = O(log n) · Prod: sorted bulk insert = linked list O(n) — shuffle or self-balance.
Skills you'll prove
Interview Tip
When asked about search or catalog performance, say: "We had warehouse scanners timing out at 30 seconds per lookup because the catalog was an unsorted array with linear search — O(n) on 100,000 SKUs. I replaced it with a BST keyed by SKU: each comparison eliminates half the tree, so lookups dropped to about 17 comparisons. Important lesson: inserting in sorted order degenerates the BST to a linked list, so we shuffle on bulk load or use a self-balancing tree. That took us from unusable to sub-10ms scans."