0
Challenge · 43Trees
Binary search trees
Treesused in ~90% of apps
Add one rule to a tree and it becomes searchable. It is binary search from tier 4 wearing a different shape, and it comes with a trap that catches almost everybody the first time.
Core idea. A binary search tree keeps one promise at every node: everything in the left subtree is smaller, everything in the right subtree is larger. That promise lets you throw away half the tree at each step. It also means the rule applies to whole subtrees, not just to a node and its two children, which is where the classic mistake lives.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
search for a value and watch half the tree disappear
Every value on the left of a node is smaller than it, and every value on the right is larger. Pick a value to look for.
Each comparison throws away everything on one side. That is binary search wearing a different shape.
↑ play a little first, then dig in