The Structure of a Binary Search Tree

What Is a Binary Search Tree?

A binary tree is a tree where every node can have at most two children — a left child and a right child. A binary search tree (often shortened to BST) is a special kind of binary tree that follows one extra rule. This rule is called the binary search property, and it is what makes the tree so useful.

Think of a node as a box that holds a value (we call this value its data). The binary search property says that for *every* node N in the tree:

• Everything in the left subtree is smaller than N. All the values stored below N on the left side are *less than* the value in N.
• Everything in the right subtree is larger than N. All the values stored below N on the right side are *greater than* the value in N.

A "subtree" simply means a node together with all the nodes hanging beneath it. So this rule is not just about a node's two direct children — it applies to *all* the descendants on each side.

Why This Rule Matters

This one rule is a quiet superpower. Because smaller values always go left and larger values always go right, you always know which direction to walk when you are looking for something. You never have to check both sides — you pick a direction and keep going.

Almost every operation you will learn later (searching, inserting, deleting) leans on this property to run blazingly fast. Instead of checking every node one by one, you can throw away half of the remaining tree at each step. That is what makes a BST so powerful.

A Concrete Example

Here is a binary search tree:

            50
          /    \
        20      64
       /  \    /  \
     12   35  63   80

Let's check the rule at a few nodes to see why this really is a binary search tree:

• At the root 50: Everything on the left (20, 12, 35) is less than 50. Everything on the right (64, 63, 80) is greater than 50. ✅
• At node 20: Its left child 12 is less than 20, and its right child 35 is greater than 20. ✅
• At node 64: Its left child 63 is less than 64, and its right child 80 is greater than 64. ✅

Because the property holds at every node — not just one — this tree is a valid binary search tree.

One Important Distinction

Keep this line in your head:

> All binary search trees are binary trees, but not all binary trees are binary search trees.

Any tree where nodes have at most two children is a binary tree. But it only earns the name *binary search tree* if it also obeys the binary search property — smaller on the left, larger on the right — at every single node. Break that rule at even one node, and it stops being a BST.