Binary Search Tree

Imagine guessing a number between one and one hundred. One yes-or-no question cuts the possibilities in half: fifty remain, then twenty-five. What if finding a single name in a million worked the same way? That's the problem a binary search tree solves.

A binary search tree is made of nodes. The top node is the root, here holding 50. Like a tournament bracket, each node can branch two ways: a left child and a right child. A node with no children is a leaf.

That branching shape is what makes searching fast. Think of a binary search tree like a game of higher or lower. At every node, you compare your number with the value on the node. If it's smaller, you move left.

If it's larger, you move right. One comparison, one decision, and the tree halves the remaining path. Here's a tree with some numbers in place. Let's insert 40.

We start at the root, which is 50. 40 is smaller than 50, so we take the left branch. Now we're at 30. 40 is larger than 30, so we take the right branch.

The right branch of 30 is empty. That's the signal — 40 belongs right there. Now let's search for 60. Start at the root again.

60 is larger than 50, so we go right. Now at 70. 60 is smaller than 70, so we go left. We arrive at 60.

Found it. Notice we never looked at the numbers 20 or 80 — the tree's structure kept us on the right path. Every operation in a binary search tree follows the same two steps: compare, then move left or right. Keep going until you find a match or an empty branch.

That's the whole idea. At each node, go left for smaller and right for larger — one comparison, and half the remaining tree disappears. Searching for 40 is like running a basketball play. Start at the root, 50.

40 is less than 50, so we cut left. Now at 30. 40 is greater than 30, so we cut right. And there's 40.

Each comparison moved us closer. Let's search this tree for 7. We start at the root, 8. Seven is less than 8, so we move left.

Now we're at 3. Seven is greater than 3, so we move right. That puts us at 6. Seven is greater than 6, so we move right again.

And there it is: 7. Each comparison gives a left-or-right answer and cuts the search in half — just like twenty questions. Here is the whole map. Start at the root.

If the value is smaller, go left; if larger, go right. Each step skips about half the remaining tree. So when a binary search tree finds a value fast, it's not a magic trick—it's just a tree that keeps order.