Binary Search Tree (BST)
A Binary Search Tree (BST) is a special type of Binary Tree where nodes are arranged in a specific order.
The main idea is:
Left subtree < Root < Right subtree
This ordering makes searching, insertion, and deletion much more efficient than in a normal binary tree—especially when the tree is balanced.
1. What is a BST?
Consider this tree:
50 / \ 30 70 / \ / \ 20 40 60 80
For every node:
- Values on the left are smaller.
- Values on the right are larger.
For example:
50 / \ < 50 > 50
At node 30:
30 / \ < 30 > 30
At node 70:
70 / \ < 70 > 70
This rule applies recursively to every subtree.
2. BST vs Binary Tree
This is very important.
Binary Tree
A binary tree only says:
Each node can have at most two children.
Example:
50 / \ 80 20
This is a valid binary tree.
But it is not a BST because:
80 > 50
yet 80 is on the left.
BST
A BST additionally requires:
Left < Root < Right
Example:
50 / \ 30 70
This is both a binary tree and a BST.
3. BST Node in C++
A BST node is similar to a normal binary-tree node.
struct Node { int data; Node* left; Node* right; Node(int value) { data = value; left = nullptr; right = nullptr; } };
4. Creating a BST
Suppose we want to insert:
50, 30, 70, 20, 40, 60, 80
The final tree becomes:
50 / \ 30 70 / \ / \ 20 40 60 80
5. Insertion in BST
This is one of the most important BST operations.
Suppose we want to insert 40.
Start at root:
40 vs 50
Since:
40 < 50
go left.
50 / 30
Now:
40 > 30
go right.
50 / 30 \ 40
40 finds an empty position, so insert it there.
C++ insertion
Node* insert(Node* root, int value) { if (root == nullptr) { 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; }
Example
Node* root = nullptr; 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);
Result:
50 / \ 30 70 / \ / \ 20 40 60 80
6. Searching in BST
This is where BST becomes powerful.
Suppose we want to find:
60
Start at 50.
60 > 50
So we only go right.
50 \ 70
Now:
60 < 70
So go left.
70 / 60
Found!
We didn't need to check every node.
C++ Search
bool search(Node* root, int target) { if (root == nullptr) { return false; } if (root->data == target) { return true; } if (target < root->data) { return search(root->left, target); } return search(root->right, target); }
Usage:
if (search(root, 60)) { cout << "Found"; } else { cout << "Not Found"; }
7. Why BST Search is Faster
Imagine:
50 / \ 30 70 / \ / \ 20 40 60 80
Searching for 60:
50 ↓ 70 ↓ 60
Only 3 nodes were visited.
We eliminated half of the possible directions at each step.
This is similar to the idea behind binary search.
8. Minimum Value in BST
In a BST:
The minimum value is the leftmost node.
Example:
50 / \ 30 70 / 20
Keep moving left:
50 → 30 → 20
So:
Minimum = 20
C++
Node* findMin(Node* root) { if (root == nullptr) { return nullptr; } while (root->left != nullptr) { root = root->left; } return root; }
9. Maximum Value in BST
Similarly:
The maximum value is the rightmost node.
50 / \ 30 70 \ 80
Move right:
50 → 70 → 80
Therefore:
Maximum = 80
C++
Node* findMax(Node* root) { if (root == nullptr) { return nullptr; } while (root->right != nullptr) { root = root->right; } return root; }
10. Inorder Traversal of BST
This is extremely important.
For a binary tree:
Inorder = Left → Root → Right
For a BST, inorder traversal produces values in sorted order.
Example:
50 / \ 30 70 / \ / \ 20 40 60 80
Inorder:
20 30 40 50 60 70 80
Notice:
20 < 30 < 40 < 50 < 60 < 70 < 80
Therefore:
Inorder traversal of a BST gives sorted order.
C++
void inorder(Node* root) { if (root == nullptr) { return; } inorder(root->left); cout << root->data << " "; inorder(root->right); }
11. Deletion in BST
Deletion is the most important and slightly difficult BST operation.
There are 3 cases.
Case 1: Delete a Leaf Node
A leaf has no children.
Example:
50 / \ 30 70 / \ 20 40
Delete 20.
Since 20 has no children:
50 / \ 30 70 \ 40
Simply remove it.
Case 2: Delete a Node With One Child
Example:
50 / 30 / 20
Delete 30.
30 has one child:
20
So connect 50 directly to 20.
50 / 20
The child takes the deleted node's position.
Case 3: Delete a Node With Two Children ⭐
This is the important case.
Consider:
50 / \ 30 70 / \ / \ 20 40 60 80
Delete:
50
It has two children.
We need a replacement.
We can use either:
Inorder successor
The smallest value in the right subtree.
Right subtree:
70 / \ 60 80
Smallest value = 60.
So replace 50 with 60.
60 / \ 30 70 / \ \ 20 40 80
Or inorder predecessor
The largest value in the left subtree.
Left subtree:
30 / \ 20 40
Largest value = 40.
Both methods can work.
12. BST Delete Code
Node* deleteNode(Node* root, int key) { if (root == nullptr) { return nullptr; } // Search for the node if (key < root->data) { root->left = deleteNode(root->left, key); } else if (key > root->data) { root->right = deleteNode(root->right, key); } // Node found else { // Case 1: No child if (root->left == nullptr && root->right == nullptr) { delete root; return nullptr; } // Case 2: Only right child if (root->left == nullptr) { Node* temp = root->right; delete root; return temp; } // Case 2: Only left child if (root->right == nullptr) { Node* temp = root->left; delete root; return temp; } // Case 3: Two children Node* temp = findMin(root->right); root->data = temp->data; root->right = deleteNode(root->right, temp->data); } return root; }
This handles all three cases.
13. Complete BST Example
#include <iostream> using namespace std; struct Node { int data; Node* left; Node* right; Node(int value) { data = value; left = nullptr; right = nullptr; } }; Node* insert(Node* root, int value) { if (root == nullptr) { 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; } bool search(Node* root, int target) { if (root == nullptr) { return false; } if (root->data == target) { return true; } if (target < root->data) { return search(root->left, target); } return search(root->right, target); } void inorder(Node* root) { if (root == nullptr) { return; } inorder(root->left); cout << root->data << " "; inorder(root->right); } Node* findMin(Node* root) { while (root->left != nullptr) { root = root->left; } return root; } Node* deleteNode(Node* root, int key) { if (root == nullptr) { return nullptr; } if (key < root->data) { root->left = deleteNode(root->left, key); } else if (key > root->data) { root->right = deleteNode(root->right, key); } else { if (root->left == nullptr) { Node* temp = root->right; delete root; return temp; } if (root->right == nullptr) { Node* temp = root->left; delete root; return temp; } Node* temp = findMin(root->right); root->data = temp->data; root->right = deleteNode(root->right, temp->data); } return root; } int main() { Node* root = nullptr; 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); cout << "Inorder: "; inorder(root); cout << "\n"; cout << "Search 60: "; if (search(root, 60)) cout << "Found"; else cout << "Not Found"; root = deleteNode(root, 50); cout << "\nAfter deleting 50: "; inorder(root); return 0; }
Output:
Inorder: 20 30 40 50 60 70 80 Search 60: Found After deleting 50: 20 30 40 60 70 80
14. BST Complexity ⭐
Let h = height of the tree.
| Operation | Average / Balanced | Worst Case |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Minimum | O(log n) | O(n) |
| Maximum | O(log n) | O(n) |
| Inorder traversal | O(n) | O(n) |
Why can it become O(n)?
Because a BST can become skewed.
15. Balanced BST
Good BST:
50 / \ 30 70 / \ / \ 20 40 60 80
Height is relatively small.
Searching is approximately:
O(log n)
16. Skewed BST ⚠️
Suppose we insert values in this order:
10 20 30 40 50 60
The tree becomes:
10 \ 20 \ 30 \ 40 \ 50 \ 60
It looks like a linked list.
Now searching for 60 requires:
10 → 20 → 30 → 40 → 50 → 60
Therefore:
O(n)
So a normal BST does not guarantee O(log n).
17. BST vs Binary Search
Don't confuse these two.
Binary Search
Algorithm used mainly on a sorted array:
[10, 20, 30, 40, 50, 60]
It repeatedly checks the middle.
Complexity:
O(log n)
Binary Search Tree
A data structure where values are organized:
40 / \ 20 60
Search follows left/right pointers.
Balanced BST:
O(log n)
Worst case:
O(n)
18. BST vs Heap
These are also different.
BST
Left < Root < Right
Example:
50 / \ 30 70
Used for:
- Searching
- Ordered data
- Finding predecessor/successor
- Maintaining sorted data
Heap
A heap is usually a complete binary tree.
Min-heap:
10 / \ 20 30
Parent is smaller than children.
Used for:
- Priority queues
- Finding minimum/maximum quickly
- Heap sort
19. Important BST Properties
Remember these:
Property 1
Left subtree < Root
Property 2
Right subtree > Root
Property 3
The rule applies recursively to every subtree.
Property 4 ⭐
Inorder traversal → Sorted order
Property 5
Minimum:
Leftmost node
Property 6
Maximum:
Rightmost node
Property 7
Balanced BST operations:
Search → O(log n) Insert → O(log n) Delete → O(log n)
Property 8
Worst-case skewed BST:
Search → O(n) Insert → O(n) Delete → O(n)
20. Real-Life Analogy
Imagine a dictionary arranged alphabetically.
You want to find:
"Computer"
You don't start from the first word and check every word.
You use ordering to decide:
Too early? → Go right Too late? → Go left
A BST uses a similar idea:
Target < current → LEFT Target > current → RIGHT Target == current → FOUND
21. Most Important BST Problems
After learning the basic operations, common interview/DSA problems include:
- Search in BST
- Insert into BST
- Delete from BST
- Find minimum
- Find maximum
- Validate a BST
- Find height of BST
- Find kth smallest element
- Find kth largest element
- Find inorder successor
- Find inorder predecessor
- Lowest Common Ancestor (LCA)
- Convert sorted array to BST
- Balance a BST
- Two Sum in BST
- Recover a corrupted BST
🧠 Final Mental Model
Think of a BST like this:
BST | ---------------- | | Left side Right side smaller larger | | -------- Root -- | Search/Insert left or right
The three most important things to remember are:
1. Left < Root < Right 2. Inorder traversal = Sorted order 3. Balanced BST: Search / Insert / Delete = O(log n)
And the roadmap now becomes:
Trees ↓ Binary Tree ↓ BST ↓ Heap ↓ Priority Queue ↓ Trie