The Same 31 Numbers, Two Trees: A Binary Search Tree Measured
A binary search tree is supposed to give you O(log n) lookups. Whether it actually does comes down entirely to the order you insert values — and it is easy to hand it the order that quietly ruins it. Here is the cost measured both ways, by the code behind the Data Structure Visualizer.
· 5 min read · every number counted from the shipped visualizer code
Two Simple Ones, One Tricky One
The stack and the queue are the easy ones. A stack is last-in, first-out — push and pop both happen at the top. A queue is first-in, first-out — add at the back, remove from the front. Neither ever searches or shifts anything, so every operation is O(1), constant time, no matter how many items are inside. The catch is that you can only reach the one exposed end; there is no jumping to the middle.
The binary search tree is where it gets interesting. Each node keeps smaller values to its left and larger to its right, so a lookup walks down from the root, comparing once per level, and the cost is simply how deep the target sits. A balanced tree of 31 nodes is only 5 levels deep, so lookups are cheap. But nothing forces a plain BST to stay balanced — and the insertion order decides whether it does.
What We Actually Measured
Take the numbers 1 through 31, build a binary search tree three ways, then search for every value and count the comparisons each lookup makes. Thirty-one is chosen because a perfectly balanced tree of 31 nodes is exactly 5 levels deep — a clean baseline.
Average comparisons per lookup (n = 31)
Same 31 numbers, same tree code. Balanced and random insertion (blue) stay near the log₂(31) ≈ 5 ideal; sorted insertion (grey) triples the lookup cost. Random order isn't perfect, but it is close — you rarely have to balance by hand to get O(log n) behaviour.
The sorted case is the trap. Inserting 1, then 2, then 3, and so on, every new value is larger than everything before it, so it attaches to the far right and the tree grows straight down — height 31, one node per level. Searching for the largest value walks all 31 nodes; the average lookup is 16 comparisons. That is precisely the cost of scanning an unsorted array. The tree structure bought you nothing.
Random insertion, by contrast, kept the tree about 9 levels deep and lookups near 5 comparisons — close to the balanced ideal of 4.2. This is why production libraries never ship a plain BST: they use self-balancing variants (red-black, AVL, B-trees) that rotate nodes on insertion so the height stays near log₂(n) whatever order the data arrives in. The plain tree in the visualizer skips that on purpose, so you can watch it fall over.
Every number here comes from the visualizer's own insert and search functions run on the numbers 1–31 — the same node-by-node path its animation traces. Open the tool, insert a few values in order, and watch the tree lean.
Data structures are one of four interactive algorithm visualizers on the site — the others animate sorting, pathfinding, and game-tree search.
Same measure-first approach, other topics: six sorting algorithms counted and BFS, Dijkstra and A* on one grid.
Tip a Tree Over Yourself
Insert values in order, then in a jumble, and watch the binary search tree go from a straight line to a balanced fan — then push and pop a stack and a queue beside it.
Common questions
Why does insertion order change a binary search tree's speed?
A binary search tree keeps smaller values left and larger values right, so a lookup walks down from the root comparing as it goes — its cost is the depth of the node. Insert values in random order and the tree stays bushy and shallow, roughly log₂(n) deep. Insert them already sorted and every new value is larger than the last, so it hangs off the right side and the tree degenerates into a straight line — a linked list wearing a tree costume. For the numbers 1–31, random insertion averaged 5.3 comparisons per lookup; sorted insertion averaged 16.
What is the worst case for a binary search tree?
A completely unbalanced tree, which happens when you insert already-sorted (or reverse-sorted) data. Building a BST from 1..31 in order produced a tree of height 31 — one node per level — where searching for the deepest value takes all 31 comparisons and the average lookup takes 16. That is O(n), no faster than scanning an unsorted array. The whole point of a search tree, O(log n) lookups, is lost.
How do real databases avoid the degenerate-tree problem?
They use self-balancing trees — red-black trees, AVL trees, or B-trees — that rotate nodes during insertion to keep the height near log₂(n) no matter what order the data arrives in. The plain BST in the visualizer does not self-balance, which is exactly why it is a good teaching tool: it lets you watch the tree tip over into a list when you insert in order.
Why are stack and queue operations O(1)?
Because they only ever touch one end. A stack pushes and pops at the top; a queue enqueues at the back and dequeues from the front. Neither has to search or shift the other elements, so each operation is constant time regardless of how many items are stored. The trade-off is that you give up random access — you can only reach the element at the exposed end.
What is the difference between a stack and a queue?
Order of removal. A stack is last-in, first-out (LIFO): the most recently pushed item comes off first, like a stack of plates. A queue is first-in, first-out (FIFO): items leave in the order they arrived, like a line at a counter. Both add and remove in O(1); they differ only in which end you remove from.
Were these numbers measured or estimated?
Measured. The lookup counts come from building a binary search tree with the visualizer's own insert function for the numbers 1–31, then running its search function for every value and counting the nodes each lookup visits. The random-insertion figures are the mean over 500 seeded shuffles, so they reproduce.