Why should you care?
Imagine you have thousands or millions of numbers and frequently need to:
- Search for a value
- Insert new values
- Delete existing values
- Keep values organized
An unsorted array may require O(n) searching.
A sorted array can provide fast binary search, but inserting or deleting elements can require shifting many values.
A Binary Search Tree (BST) provides a different approach: it organizes values structurally so that searching can skip large portions of the tree.
A well-balanced BST can provide:
Search → O(log n)
Insert → O(log n)
Delete → O(log n)
That makes BSTs an important bridge between trees and efficient searching algorithms.
The Problem
Suppose we have these numbers:
50, 30, 70, 20, 40, 60, 80
If they're stored in an unsorted array:
50 30 70 20 40 60 80
Searching for 60 might require checking several elements.
We could sort the array first:
20 30 40 50 60 70 80
Then binary search can find values efficiently.
But what happens when we frequently insert and delete values?
Maintaining a sorted array can become expensive because elements may need to be shifted.
We need a structure that maintains an ordered relationship between values while allowing dynamic insertion and deletion.
That's the problem a Binary Search Tree addresses.
The Concept
A Binary Search Tree is a binary tree with an ordering rule.
For every node:
Left subtree < Node < Right subtree
For example:
50
/ \
30 70
/ \ / \
20 40 60 80
Look at node 50:
Values smaller than 50 → left
Values larger than 50 → right
Look at node 30:
20 < 30
40 > 30
Look at node 70:
60 < 70
80 > 70
This ordering rule allows us to make decisions while searching.
Simple Explanation
Imagine a guessing game.
I choose a number between 1 and 100.
You guess:
50
I say:
"Your number is higher."
You immediately eliminate all numbers below 50.
Now you guess:
75
I say:
"Your number is lower."
Now you've eliminated another large portion.
A BST works similarly.
Suppose we're searching for 60:
50
/ \
30 70
/ \
60 80
Start at 50.
60 > 50
So we don't need to search the left subtree.
Go right:
70
/
60
Then:
60 < 70
Go left:
60 → FOUND
Instead of examining every node, we followed only the relevant path.
Real-world Analogy
Imagine a dictionary.
Suppose you want to find the word "tree".
You don't start at the first word and read every word until reaching tree.
You open somewhere near the middle.
If the words are alphabetically earlier:
A ... M
you move forward.
If they're later:
T ... Z
you move backward.
You repeatedly eliminate large portions of the search space.
A BST applies the same fundamental idea to numerical or comparable data:
Smaller → Left
Larger → Right
Code Example
Let's create a simple BST node in Java:
class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
}
}
Now let's implement insertion:
Node insert(Node root, int value) {
if (root == null)
return new Node(value);
if (value < root.data)
root.left = insert(root.left, value);
else if (value > root.data)
root.right = insert(root.right, value);
return root;
}
We can build a tree:
Node root = null;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 70);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 60);
root = insert(root, 80);
The resulting tree is:
50
/ \
30 70
/ \ / \
20 40 60 80
Searching
We can search for a value like this:
boolean search(Node root, int value) {
if (root == null)
return false;
if (root.data == value)
return true;
if (value < root.data)
return search(root.left, value);
return search(root.right, value);
}
For:
search(root, 60);
the path is:
50
↓
70
↓
60
↓
FOUND
The BST doesn't randomly search the tree.
The ordering rule tells it where not to search.
Common Mistakes
Mistake 1: Thinking every binary tree is a BST
A binary tree:
50
/ \
80 20
is perfectly valid as a binary tree.
But it is not a valid BST because:
80 > 50
yet 80 is on the left.
A BST must maintain its ordering rule.
Binary Tree:
At most 2 children
BST:
At most 2 children
+
Ordering rule
Mistake 2: Assuming a BST is always O(log n)
This is one of the most important misconceptions.
Consider:
10
\
20
\
30
\
40
\
50
This is technically a valid BST.
But it has become essentially a linked list.
Searching for 50 requires:
10 → 20 → 30 → 40 → 50
So the complexity becomes:
O(n)
A BST provides O(log n) operations when its height is approximately logarithmic, typically when the tree is reasonably balanced.
Mistake 3: Assuming inorder traversal gives sorted values for every tree
This property is specific to a valid BST.
For:
50
/ \
30 70
/ \ / \
20 40 60 80
inorder traversal:
Left → Root → Right
produces:
20 30 40 50 60 70 80
This works because the BST ordering rule guarantees it.
A random binary tree does not necessarily produce sorted output through inorder traversal.
Advanced Notes
1. BST search complexity
The complexity of searching depends on the height of the tree.
For a balanced BST:
50
/ \
30 70
/ \ / \
20 40 60 80
The height is approximately:
log₂(n)
Therefore:
Search → O(log n)
But for an unbalanced tree:
50
\
60
\
70
\
80
the height approaches n:
Search → O(n)
So the key factor isn't simply "Is it a BST?"
It's:
How tall is the BST?
2. Insertion
Suppose we insert 65:
50
/ \
30 70
/ \
60 80
Start at 50:
65 > 50 → right
At 70:
65 < 70 → left
At 60:
65 > 60 → right
So:
50
/ \
30 70
/ \
60 80
\
65
Again, insertion follows the same comparison process as searching.
3. Deletion
Deletion is more complicated because there are three cases.
Case 1: Node is a leaf
50
/
30
Delete 30:
50
Simple.
Case 2: Node has one child
50
/
30
\
40
Delete 30.
We can connect its parent directly to its child:
50
/
40
Case 3: Node has two children
Consider:
50
/ \
30 70
/ \
60 80
If we delete 70, we can't simply remove it because it has two children.
A common solution is to replace it with its inorder successor—the smallest value in its right subtree.
Here:
70's right subtree:
80
So 80 can replace 70.
More generally:
Inorder successor
=
Smallest value in right subtree
Another valid approach uses the inorder predecessor, the largest value in the left subtree.
4. Inorder traversal
One of the most useful properties of a BST is:
Inorder traversal produces values in sorted order.
For:
50
/ \
30 70
/ \ / \
20 40 60 80
Inorder means:
Left → Root → Right
Result:
20 → 30 → 40 → 50 → 60 → 70 → 80
This is one of the most important properties to remember about BSTs.
5. Balanced BSTs
To maintain efficient operations, we want the tree to remain relatively balanced.
For example:
Balanced:
50
/ \
30 70
/ \ / \
20 40 60 80
Compared with:
Unbalanced:
10
\
20
\
30
\
40
Self-balancing BSTs automatically restructure themselves when necessary.
Important examples include:
- AVL trees
- Red-Black trees
These maintain height around O(log n).
Java's TreeMap and TreeSet, for example, are based on a Red-Black tree implementation.
6. BST vs Binary Search
These concepts are related but different.
Binary search is an algorithm:
Sorted Array
↓
Binary Search
↓
O(log n) search
A BST is a data structure:
Tree Structure
↓
BST Ordering
↓
Efficient Search
Both exploit the same fundamental idea:
Compare and eliminate an entire region of possibilities.
But their trade-offs differ.
| Feature | Sorted Array | BST |
|---|---|---|
| Search | O(log n) | O(log n)* |
| Insert | O(n) | O(log n)* |
| Delete | O(n) | O(log n)* |
| Random access | O(1) | O(n) |
| Dynamic structure | Limited | Good |
* Assumes a balanced BST.
The Bigger Picture
BSTs connect several concepts we've already learned:
Arrays
↓
Binary Search
↓
Trees
↓
Binary Trees
↓
Binary Search Trees
↓
Balanced Trees
There's also a powerful connection between BSTs and the algorithms you've already encountered.
A sorted array uses:
Compare
↓
Discard half
↓
Compare
↓
Discard half
A balanced BST does something conceptually similar:
50
/ \
discard continue
left ↓
70
/ \
continue discard
↓
60
Both structures are built around reducing the search space.
BSTs also lead to more advanced structures:
BST
├── AVL Tree
├── Red-Black Tree
├── Splay Tree
└── Other balanced search trees
These structures are important because real-world systems need efficient performance even when data arrives in unfavorable orders.
The Most Important Mental Model
At every node, a BST asks one question: "Is the value smaller or larger than me?"
Then:
Smaller → Go LEFT
Larger → Go RIGHT
Equal → FOUND
Visualize it as a decision tree:
50
/ \
< 50 > 50
/ \
30 70
/ \ / \
<30 >30 <70 >70
Every comparison directs you toward the only subtree that can contain the value.
That's the fundamental power of a BST.
Summary
A Binary Search Tree is a binary tree that maintains an ordering relationship between its nodes.
The key ideas are:
- Values smaller than a node go to the left.
- Values larger than a node go to the right.
- Searching follows comparisons down a single path.
- A balanced BST provides approximately O(log n) search, insertion, and deletion.
- An unbalanced BST can degrade to O(n).
- Inorder traversal of a valid BST produces values in sorted order.
- Deletion has three cases: leaf, one child, and two children.
- Self-balancing trees such as AVL and Red-Black trees maintain efficient height.
- BSTs apply the same fundamental idea as binary search: use comparisons to eliminate unnecessary search space.
A Binary Search Tree turns ordering into structure—by placing smaller values on one side and larger values on the other, it transforms a collection of data into a decision path that can make searching dramatically more efficient.
Top comments (0)