Binary Search Tree

A binary search tree turns the halving idea from binary search into an actual structure. Every node holds one value, with everything smaller sitting in its left subtree and everything larger in its right. To find a value you start at the root and compare: equal and you are done, smaller and you go left, larger and you go right. Each step throws away a whole subtree, so on a balanced tree you reach any value in about log n comparisons — the same reach as binary search on the array.

The catch is the word balanced. The tree here is built from the sorted values by repeatedly taking the middle element as the node, so the two sides always stay even and the height stays around log n. Build a tree the naive way instead — inserting values one after another in sorted order — and every new value hangs off the right of the last one: the tree degenerates into a long spindly chain, and searching it is back to O(n), no better than scanning a list. That failure mode is the whole reason self-balancing trees like AVL and red-black trees exist, and why a plain BST is more of a teaching tool than something you would reach for in production.

So why keep values in a tree at all when a sorted array binary-searches just as fast? Because a tree is cheap to change. Inserting into the middle of a sorted array means shifting everything after it along by one; splicing a new node into a tree is a couple of pointer updates. When the data keeps changing and you still want fast lookups, a balanced tree earns its keep. When it is static, the array usually wins.

Watch the highlighted path trace down from the root while the subtree it rules out fades away, and the ring marks the node it is comparing right now. Type a value into the search box to look for something specific, or leave it empty and let the Target menu pick one that is present or falls in a gap. Data switches between numbers and words, and New array deals a fresh sorted set.