Understanding a Binary Search Tree

Understanding a Binary Search Tree

A binary search tree (often shortened to *BST*) is a special way of storing data. Before we can understand it, let's quickly recall what a binary tree is.

A quick reminder: what is a binary tree?

A tree is a way of arranging data where one item sits at the top and other items hang below it, like a family tree turned upside down. Each item is called a node.

In a binary tree, every node can have *at most two* children:

• a left child
• a right child

That's all "binary" means here — *two* possible children. A binary tree spreads out in two directions (left and right), which gives it a nice two-dimensional shape.

So what makes it a *search* tree?

A plain binary tree lets you put any value anywhere. A binary search tree adds one important rule about *where* each value is allowed to go:

> For any node, every value in its left side is smaller, and every value in its right side is larger.

In simple words: smaller numbers always go left, bigger numbers always go right. The tree decides who gets to be the left child and who gets to be the right child based on this comparison. This special ordering is the whole idea behind a BST.

Reading the example tree

Look at this tree, where 50 sits at the top (the top node is called the root):

            50
          /    \
        20      64
       /  \    /  \
     12   25  63   66

Let's check the rule:

• 50 is the root. Everything smaller than 50 (20, 12, 25) is on its left. Everything larger (64, 63, 66) is on its right.
• Look at 20: its left child 12 is smaller than 20, and its right child 25 is larger than 20. The rule holds here too.
• Look at 64: its left child 63 is smaller, and its right child 66 is larger. Again, correct.

Notice that the rule is not just about a node and its direct children — it applies to the *entire* group of values on each side.

Why does this ordering matter?

Because the values are organized, the computer never has to look at everything. When you search for a number, you start at the root and ask one simple question each time: *"Is the number I want smaller or larger than this node?"*

• If it's smaller, go left.
• If it's larger, go right.

For example, to find 25 in the tree above: start at 50 (25 is smaller, go left), reach 20 (25 is larger, go right), and there's 25. Just two comparisons — you completely ignored the entire right half of the tree.

This is why a binary search tree makes searching, inserting, and deleting values extremely fast compared to a generic binary tree where values are placed with no order. Each step throws away a large chunk of the data you no longer need to check.