Binary tree vs binary search tree

Both names tend to show up in the same paragraph of the same course, often without a clean line drawn between them, which leaves a reasonable question unanswered: are these two structures, or one structure with an extra condition bolted on? It is the second. A binary search tree is a binary tree that also promises something about where each value sits, and that promise is the only thing separating a structure a lookup can navigate from one it can only wander through.

One rule, and what it buys#

A binary tree is a shape: each node has at most two children, called left and right. Nothing about that shape says anything about what values belong where. A binary search tree adds one rule on top of the shape, and the rule is recursive rather than local — for every node in the tree, not just the root, everything in its left subtree is smaller than that node, and everything in its right subtree is larger. It has to hold at every node because a lookup only ever compares against the node in front of it; if the rule held between a node and its immediate children but broke two levels down, a search still following left-means-smaller would walk straight past a value that was actually there.

That recursive rule is what a lookup spends. At each node, comparing the target against the node’s value rules out an entire subtree — the rest of that subtree cannot hold the answer, because the ordering rule guarantees everything in it sits on the wrong side. A search that starts at the root and keeps taking the branch the comparison points to never has to look at a node it has already ruled out, so it visits one node per level rather than every node in the tree. That cost is expressed as O(h), where h is the tree’s height — the number of edges from root to the farthest leaf — because that is the longest path a lookup can be forced to walk.

The catch is that h depends entirely on shape, and the ordering rule says nothing about shape. Insert values in an order that keeps splitting the remaining range roughly in half and h stays close to the smallest height that many nodes can have. Insert them already sorted — smallest first, or largest first — and every new node has nowhere to go but further down the one branch already growing, so the tree degenerates into something that is structurally a linked list wearing a binary tree’s node type. At that point h equals the number of nodes, the O(h) bound becomes O(n), and the walk that was supposed to skip half the tree at every step is back to visiting all of it. Nothing about the ordering rule prevents that shape; keeping h small on adversarial input is a separate job, and it is the whole reason self-balancing trees exist. The site’s binary search tree visualizer makes the difference easy to see directly: insert the same handful of numbers in a shuffled order and then in sorted order, and the height stat swings from close to the smallest possible to one branch stretched out to the count of nodes.

What a plain binary tree is for#

A binary tree with no ordering rule is not a search tree that someone forgot to finish. It is doing different work, and the work is usually that the shape itself carries the meaning, rather than any left-smaller, right-larger relationship between values. Three ordinary examples make the point. An expression tree represents a formula: each internal node is an operator with (at most) two operands as children, and which subtree nests inside which is what encodes precedence and grouping — evaluating it bottom-up is the whole point, and no value in it is ever “smaller” or “larger” than another in a way the tree cares about. A Huffman tree, built for compression, has each symbol sitting at a leaf, and the path from the root to that leaf — the sequence of left and right turns — is the symbol’s code; left and right encode a bit, not an ordering. A binary heap keeps at most two children per node too, but its rule runs between a parent and its children (the parent is never larger than either child, in a min-heap, or never smaller, in a max-heap), which is a different axis entirely from left-versus-right — a heap can and routinely does have a smaller value sitting to the right of a larger one.

None of the three would gain anything from a binary-search-tree ordering rule, because none of them is answering “is this value present, and where.” Asking whether an expression tree, a Huffman tree or a heap is “sorted” is asking a question those structures were never built to answer — they are binary trees doing real, different work, not search trees that happen to be missing a step.

The type name promises nothing#

The recurring mistake is trusting a type name. A structure called BinarySearchTree looks like it should guarantee the ordering rule the way a compiler guarantees a field’s type, but nothing checks it at read time — the rule is only as good as whatever code last built or edited the tree. An insert function written to respect the rule will keep it intact indefinitely. Anything that builds or edits a tree by a different path does not get the guarantee for free: a node mutated in place rather than removed and reinserted, a tree deserialised from data nobody validated, two subtrees stitched together by hand — all of these can produce an object that satisfies the type and violates the rule at the same time.

When that happens, a lookup does not fail loudly. It takes the branch the (now-wrong) comparison tells it to take, reaches a dead end, and reports the value as not found — even when that value is sitting a few nodes away on the branch the lookup never visited. Nothing about the search logic changes; only the shape it is trusting has quietly stopped matching the assumption it was written against.

Checking the rule on every lookup is not an option — doing that would cost as much as the scan the ordering rule exists to avoid, which defeats the point of using the structure at all. The workable guard is a one-off check, not a standing one: walk the tree in-order and confirm the values that come out never decrease — the in-order pass that does this is the same one that produces sorted output on a valid tree in the first place, which is exactly why it doubles as the check. That check belongs in a test suite, run after whatever built or modified the tree, not on the hot path of every lookup.