A binary search tree stores data so that, at every node, everything smaller sits in the left subtree and everything larger sits in the right subtree — a structure that lets a search eliminate roughly half the remaining data at every step, the same way flipping to the middle of a phone book and discarding half the remaining pages narrows a search fast. Done well, this lets a computer find any one item among a million in around twenty comparisons. Done badly, the exact same data structure can degrade into something no faster than checking every item one by one.
Halving the search space, one comparison at a time
Searching a binary search tree starts at the root and compares the target value against the current node: if it matches, the search is done; if the target is smaller, the search moves to the left subtree; if larger, it moves to the right subtree; and the process repeats. Each comparison, in a well-formed tree, eliminates roughly half of the remaining candidates from consideration, which is why the number of comparisons needed grows only logarithmically with the size of the data — doubling the amount of data adds only one extra comparison step, not double the work, which is an enormously favourable trade-off for large datasets.
Why the shape of the tree is doing all the work
That logarithmic performance depends entirely on the tree being reasonably balanced — roughly the same number of nodes on the left and right side of any given point in the tree. If data is inserted in an already-sorted order, a naively built binary search tree degenerates into something structurally identical to a simple linked list, with every new node attached only as a single right (or left) child of the previous one, and no actual branching at all. Searching that degenerate tree requires checking every single item in the worst case, exactly as slow as an unsorted list — the tree data structure is technically still there, but none of its performance advantage survives the lopsided shape. This is precisely why self-balancing tree variants, like AVL trees and red-black trees, exist: they automatically restructure themselves during insertion and deletion specifically to prevent this kind of degeneration, guaranteeing the tree stays close enough to balanced that its fast, logarithmic search performance holds regardless of what order data happens to arrive in.
What we're still unsure about
The mathematics of balanced versus unbalanced tree performance is precisely, rigorously understood, and self-balancing tree algorithms are well-proven, standard tools in computer science — none of this is a matter of ongoing debate. What varies in practice, and remains a genuine engineering trade-off rather than a settled formula, is choosing the right specific data structure for a given real-world workload: self-balancing trees guarantee good worst-case performance but carry real overhead from the rebalancing work itself, and for some access patterns, alternative structures like hash tables or B-trees (commonly used in databases) outperform balanced binary trees in practice, which is why picking the right structure still requires understanding the specific pattern of reads, writes, and data distribution a given application actually faces.
This sits inside Binary Trees & Binary Search Trees, one of eight topics in Data Structures, one of seven domains in Computer Science, one of seventeen subjects the app can quiz you on.