level 6 · Trees
Binary Search Tree
A tree that keeps one promise — smaller left, bigger right — so it can search fast.
what is it
Start here
A binary search tree branches. Every node has up to two children, and it keeps one simple promise: everything in its left branch is smaller than it, everything in its right branch is bigger.
That promise is worth a lot. To find a value, you start at the top and, at each node, go left if you want something smaller or right if you want something bigger. Every step throws away a whole branch you never have to look at — exactly like binary search, but on a shape that lets you insert and delete easily too.
Watch a value being inserted: it walks down from the root, comparing as it goes, until it falls off the bottom into an empty spot. That's the only spot it could legally go. In a balanced tree, that walk is about log n steps — so searching a million values takes around twenty comparisons.
The catch, which you'll feel if you insert already-sorted values: if the tree grows lopsided, it stretches into a straight line and searching becomes as slow as a plain list. Keeping it balanced is a whole topic of its own (AVL and red-black trees), and it's next on the roadmap.
real-life analogy
Picture it
You think of a number and I guess. Each time, you only tell me 'higher' or 'lower'. I never waste a guess — every answer cuts the possibilities in half. A search tree is that game frozen into a shape: each node is a guess, and left/right is 'lower/higher'.
interactive visualization
Watch it run
These get inserted one by one, then we search for the target.
A binary search tree keeps a promise at every node: smaller values live to the left, bigger values to the right. That one rule is what makes it fast to search.
step 01/22
- comparing
- target · placed
- on the path
space · play ← → · step
| 1 | function insert(root, value) { |
| 2 | if (root === null) return new Node(value); |
| 3 | if (value < root.value) { |
| 4 | root.left = insert(root.left, value); |
| 5 | } else { |
| 6 | root.right = insert(root.right, value); |
| 7 | } |
| 8 | return root; |
| 9 | } |
| 10 | |
| 11 | function search(root, value) { |
| 12 | if (root === null) return false; |
| 13 | if (value === root.value) return true; |
| 14 | if (value < root.value) { |
| 15 | return search(root.left, value); |
| 16 | } |
| 17 | return search(root.right, value); |
| 18 | } |
variables right now
Nothing in play yet — press play.
the dry run · every step, in words
22 stepscomplexity
What it costs
- best case
- O(log n)
- average
- O(log n)
- worst case
- O(n)
- extra memory
- O(n)
Search, insert and delete all cost about the height of the tree. A balanced tree has height log n — beautifully fast. But insert sorted values and the tree degenerates into a line of height n, and everything slows to a crawl. Balance is everything.
- O(1)
- O(log n) · this one
- O(n)
- O(n log n)
- O(n²)
common mistakes
Common traps
Inserting already-sorted data and expecting it to stay fast.
Sorted input builds a tree that's really just a linked list — height n, not log n. That's the worst case, and it's why self-balancing trees exist.
Putting equal values on both sides inconsistently.
Pick one rule — say, equal goes right — and apply it everywhere. Mixing the rule breaks search, because a value could hide on the side you didn't check.
Forgetting the empty-tree case when inserting.
If the root is null, the new value becomes the root. Skip that check and the very first insert crashes.
quiz
Check yourself
Three questions. Get them all right to finish the lesson.
+95 XP01In a binary search tree, where do you find values smaller than a node?
02Searching a balanced BST of 1,000,000 nodes takes about how many steps?
03What happens if you insert values in already-sorted order?
practice
Solve it on LeetCode
You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.