Binary Search Tree
Medium+90 XPKeep left < node < right at every node, and searching becomes one walk straight down — binary search on a tree.
Where it breaks
A BST is only fast when it stays balanced. Sorted input makes it lopsided.See what happens when you don't.
No visualization loaded.
Watch
—
Press Run to begin.
A Binary Search Tree is a tree of numbers with one rule that never breaks: at every node, everything on its left is smaller and everything on its right is bigger. That one rule means to find a number you just keep asking 'smaller or bigger?' and step down one path — you never have to look at the whole tree.
▸What does the 'left < node < right' rule actually buy me?
It tells you which way to turn without looking at anything else. Standing on a node, if your number is smaller you KNOW it can only be down-left, and if it's bigger it can only be down-right. So at every step you throw away a whole half of what's left — the entire other subtree — instead of checking it. That's why a search is a single walk down, not a hunt through every node.
▸How is this related to binary search?
It's the same idea! Binary search on a sorted array keeps cutting the list in half by comparing with the middle. A BST does the exact same cut, but the 'middle' is whatever node you're standing on: go left for smaller, right for bigger. The tree is basically a sorted list folded up so each comparison hands you the next 'middle' for free.
▸Why do people say search is O(log n)... only sometimes?
Each step drops you one level deeper, so the cost is the tree's HEIGHT. If the tree is nicely balanced (left and right roughly even), the height is about log n — doubling the numbers adds just one extra level. That's the fast case.
▸So when is a BST slow (the worst case)?
If you insert numbers already in order — say 1, 2, 3, 4, 5 — each new number is always bigger, so it always goes right. The tree turns into a straight line, a leaning chain with no branching. Now its height is n, and searching it is just walking down a list one node at a time — O(n), no better than scanning an array. Balanced = fast (log n); a line = slow (n).
▸What happens when I insert a new number?
You search for where it WOULD be, using the same smaller/bigger steps, until you walk off the edge into an empty spot — and that's exactly where the new number goes. Insert is just 'search until you fall off the tree, then attach there.' (We skip duplicates so the rule stays clean.)
How the work grows
O(log n) average, O(n) worst is excellent — barely grows. Each compare steps you one level deeper, so search/insert cost = the tree's HEIGHT. A balanced tree is about log n tall (the fast, average case the curve shows). But insert sorted numbers and the tree degenerates into a straight line of height n — then it's no faster than scanning an array. Space is one node per value, O(n).
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.