Chapter 27: DSA Binary Search Trees
DSA Binary Search Trees (BST) – Let’s understand this topic properly, like I’m sitting next to you with a whiteboard, drawing trees step by step, explaining every detail slowly, giving multiple examples, showing how operations work visually, and most importantly telling you why BST is one of the most frequently asked and most powerful data structures in interviews.
What is a Binary Search Tree?
A Binary Search Tree (BST) is a special type of binary tree that follows a very important ordering property:
For every node in the tree:
- All values in the left subtree are less than the node’s value
- All values in the right subtree are greater than the node’s value
- Both left and right subtrees are themselves Binary Search Trees
This ordering rule is what makes BST very powerful — it allows us to search, insert, and delete very efficiently (on average).
Visual Example – A valid BST
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
50 / \ 30 70 / \ / \ 20 40 60 80 / / \ 10 55 65 |
Check the rule:
- Left of 50 → 30,20,40,10 → all < 50
- Right of 50 → 70,60,80,55,65 → all > 50
- Left of 30 → 20,10 → all < 30
- Right of 30 → 40 → > 30
- And so on for every node
Invalid BST examples (very common interview trap)
|
0 1 2 3 4 5 6 7 8 9 10 |
50 / \ 30 70 / \ \ 20 60 80 |
→ Invalid because 60 is in left subtree of 50 but 60 > 50
|
0 1 2 3 4 5 6 7 8 9 10 |
20 / \ 10 30 / 25 |
→ Invalid because 25 is in right subtree of 20 but 25 > 30 (right child rule violated)
Key Properties of BST
| Property | Detail / Consequence |
|---|---|
| In-order traversal | Gives nodes in sorted ascending order |
| No duplicate keys | Usually (some allow duplicates with counts) |
| Search time | O(h) where h = height of tree |
| Best case height | O(log n) → balanced tree |
| Worst case height | O(n) → skewed / degenerate tree |
| Average case (random inserts) | O(log n) |
Most Important BST Operations
1. Search for a value
Very similar to binary search on sorted array
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 |
def search(root, key): if root is None or root.val == key: return root if key < root.val: return search(root.left, key) return search(root.right, key) |
Steps (search 40 in above tree):
Start at 50 → 40 < 50 → go left 30 → 40 > 30 → go right 40 → found!
Time: O(h) → O(log n) balanced, O(n) skewed
2. Insert a new value
We follow the same comparison rule until we find the correct null position
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
def insert(root, key): if root is None: return TreeNode(key) if key < root.val: root.left = insert(root.left, key) elif key > root.val: root.right = insert(root.right, key) return root |
Example — insert 45
Start at 50 → 45 < 50 → left 30 → 45 > 30 → right 40 → 45 > 40 → right (null) → create new node 45
Now tree becomes:
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
50 / \ 30 70 / \ / \ 20 40 60 80 / / \ \ 10 45 55 65 |
3. Delete a node (most tricky operation)
Three cases:
Case 1: Node has no children (leaf) → Just remove it
Case 2: Node has one child → Replace node with its child
Case 3: Node has two children (most important) → Find in-order successor (smallest in right subtree) → Copy successor value to current node → Delete successor (which has at most one child)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
def minValueNode(node): current = node while current.left: current = current.left return current def deleteNode(root, key): if not root: return root if key < root.val: root.left = deleteNode(root.left, key) elif key > root.val: root.right = deleteNode(root.right, key) else: # Node found # Case 1 & 2: 0 or 1 child if not root.left: return root.right elif not root.right: return root.left # Case 3: Two children temp = minValueNode(root.right) root.val = temp.val root.right = deleteNode(root.right, temp.val) return root |
Why BST is so important in interviews
| Reason | Frequency / Importance |
|---|---|
| Sorted order access in O(n) | ★★★★★ |
| Efficient search/insert/delete (balanced) | ★★★★★ |
| Basis for many advanced structures | ★★★★★ |
| Very common medium/hard questions | ★★★★★ |
| Teaches recursion & pointer manipulation | ★★★★★ |
Most Common BST Interview Questions
Easy → Medium:
- Insert into BST
- Search in BST
- Validate Binary Search Tree
- In-order successor / predecessor
- Kth smallest / largest element in BST
Medium → Hard:
- Delete node in BST
- Lowest Common Ancestor in BST
- Construct BST from preorder traversal
- Convert sorted array to BST
- Recover BST (two nodes swapped)
Summary – Binary Search Tree in one line each
- Binary tree with left < node < right property
- In-order traversal gives sorted order
- Search, insert, delete → O(h) time (h = height)
- Balanced BST → O(log n), skewed → O(n)
- Most important tree structure for ordered data
- Foundation for AVL, Red-Black, Treap, B-Tree, etc.
- Appears in almost every company’s interview
Would you like to go deeper into any BST topic next?
Very common follow-up topics:
- Insert & Delete in BST step-by-step dry runs
- Validate BST (multiple methods)
- Kth smallest element in BST
- Lowest Common Ancestor in BST
- Convert sorted array/list to BST
- BST vs Balanced BST (AVL/Red-Black intro)
Just tell me which one you want — I’ll explain it with the same level of detail, visuals, and step-by-step clarity! 😊
