🌱 What Is a Binary Search Tree?
A Binary Search Tree, or BST, is a special type of binary tree that keeps its elements in a sorted order.
This makes searching, inserting, and deleting data very fast — much faster than in an unsorted tree or a list.
But what makes it special?
It follows a simple rule at every node:
👉 Left child < Parent < Right child
That means:
- Every value in the left subtree is smaller than the node’s value.
- Every value in the right subtree is larger than the node’s value.
🌳 Let’s Look at an Example
Imagine this Binary Search Tree:
50
/ \
30 70
/ \ / \
20 40 60 80Here’s how it follows the BST rule:
- The root node is 50.
- Everything left of 50 (30, 20, 40) is smaller than 50.
- Everything right of 50 (70, 60, 80) is greater than 50.
- If you pick 30, its left child 20 is smaller, and its right child 40 is larger.
- The same goes for 70 — its left child 60 < 70, and its right child 80 > 70.
It’s like a perfectly balanced see-saw of numbers!
🌿 Why Is It Called a “Search” Tree?
Because it makes searching lightning fast ⚡
Let’s say you want to find 40 in the above tree.
- Start at the root (50).
- Since 40 < 50, go left.
- Now you’re at 30.
- Since 40 > 30, go right.
- You find 40! 🎯
You didn’t need to look through every element — just followed the logical path.
This is much faster than searching line by line through an unsorted list.
🌸 Everyday Analogy
Think of it like searching a word in a dictionary:
You don’t start from the first page every time.
If you’re looking for “Mango,” you flip somewhere around the middle — maybe near “L.”
Then, if “Mango” is further ahead, you go right. If it’s before “L,” you go left.
That’s exactly how a Binary Search Tree behaves — divide and conquer!
🌺 Basic Operations in a BST
Let’s quickly go over what we can do with a BST:
1. Search
- Start from the root.
- Compare the value you’re looking for with the current node.
- Move left if it’s smaller, or right if it’s larger.
- Continue until you find it or reach a
NULL(meaning it doesn’t exist).
2. Insertion
- Start at the root.
- Compare the new value with the current node.
- Go left if it’s smaller, right if it’s larger.
- Place the new node when you find an empty spot.
Example:
Insert 65 in our tree:
50
/ \
30 70
/ \ / \
20 40 60 80
\
65Since 65 > 60 but < 70, it fits as the right child of 60.
3. Deletion
There are three possible cases when deleting a node:
- The node is a leaf (no children) → just remove it.
- The node has one child → replace it with its child.
- The node has two children → replace it with its inorder successor (the smallest value in the right subtree).
Deletion keeps the BST rules intact.
🌻 Traversing a BST
Tree traversal means visiting every node in some order.
The three common methods are:
- Inorder Traversal (Left → Root → Right)
Gives elements in sorted order!
Example output for our tree:20, 30, 40, 50, 60, 70, 80 - Preorder Traversal (Root → Left → Right)
Useful for creating a copy of the tree. - Postorder Traversal (Left → Right → Root)
Useful for deleting or freeing nodes.
🌼 Diagram – Binary Search Tree Structure
50
/ \
30 70
/ \ / \
20 40 60 80- Left subtree (30, 20, 40) < 50
- Right subtree (70, 60, 80) > 50
That’s the core rule of a BST.
🌻 Advantages of BST
✅ Fast Searching – Average time complexity is O(log n)
✅ Efficient Insertion/Deletion – Keeps data sorted automatically
✅ Easy to Traverse – Especially for sorted output using inorder traversal
✅ Dynamic Size – Can grow or shrink as needed (unlike arrays)
🌸 A Word of Caution
BSTs work best when they’re balanced.
If you keep inserting values in increasing order (like 10, 20, 30, 40…),
the tree will lean to one side — becoming more like a linked list.
This makes it slower (O(n) time).
To fix this, we use balanced BSTs like:
- AVL Trees
- Red-Black Trees
But that’s a story for another day. 🌱
🌷 Summary
| Concept | Description |
|---|---|
| Definition | A binary tree where left < root < right |
| Purpose | Fast searching, inserting, and deleting |
| Rule | Left child smaller, right child larger |
| Traversal (Inorder) | Gives sorted elements |
| Applications | Databases, searching, indexing, symbol tables |
About the Author
