DSA: Binary Search Trees
Learn BST properties, insertion, deletion, validation, and classic BST algorithms like LCA, kth smallest, and BST-to-DLL conversion.
BST Properties
A Binary Search Tree is a binary tree where every node satisfies the BST property: all values in its left subtree are strictly less than the node, and all values in its right subtree are strictly greater.
BST Ordering Property
The BST property holds recursively for every node, not just the immediate children.
- Left subtree: all values strictly less than the current node
- Right subtree: all values strictly greater than the current node
- No duplicate keys in a standard BST
- Inorder traversal of any valid BST produces a sorted ascending sequence
| Operation | Average Case | Worst Case (Skewed) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Inorder traversal | O(n) | O(n) |
| Find min / max | O(log n) | O(n) |
Search and Insertion in BST
Both search and insertion follow the same path down the tree: go left if the target is smaller, go right if larger. Insertion places the new node at the first null position encountered.
BST Search and Insert
At each node, one comparison eliminates half the remaining tree (on average), giving O(log n) performance.
- Search: return true at a match; go left if val < node, right if val > node; return false at null
- Insert: same traversal as search; place the new node at the null where search would end
- Both operations share the exact same decision logic
- Recursive and iterative implementations both achieve O(h) time where h is the tree height
BST Insert and Search
C++Inorder output is sorted, confirming the BST property is maintained after all insertions.
Deletion in BST
Deleting a node has three cases: the node is a leaf, the node has one child, or the node has two children. The two-child case replaces the node with its inorder successor (smallest in the right subtree).
Three Deletion Cases
The two-child case is handled by replacing the value with the inorder successor, then deleting the successor from the right subtree.
- Leaf node: delete it and return null
- One child: return the non-null child to bypass the deleted node
- Two children: find the minimum of the right subtree, copy its value, delete that minimum node
- Inorder successor = leftmost node of the right subtree (smallest value greater than current)
BST Deletion (All Three Cases)
C++Node 3 has two children. It is replaced by its inorder successor (4), then 4 is deleted from the right subtree.
Inorder Successor and Predecessor
The inorder successor of a node is the smallest value greater than it. The inorder predecessor is the largest value less than it. Both can be found in O(h) using BST properties.
Successor and Predecessor in BST
Exploit the BST property: when current value is smaller than target, it could be the predecessor, keep going right. When larger, it could be the successor, keep going left.
- Successor: if current > key, save as candidate and go left; if current <= key, go right
- Predecessor: if current < key, save as candidate and go right; if current >= key, go left
- The last saved candidate when reaching null is the answer
- If the node has a right subtree, successor = minimum of that subtree (no traversal up needed)
Inorder Successor and Predecessor
C++One iterative pass saves the best candidate seen so far. No parent pointers or extra memory needed.
Validate a BST
Checking only that each node is greater than its left child and less than its right child is not sufficient. The correct approach passes valid min and max boundaries down every recursive call.
Min-Max Range Validation
Each node must fall strictly within the range inherited from its ancestors, not just be greater or less than its direct parent.
- Root has range (-INF, +INF)
- Going left: upper bound tightens to current node value
- Going right: lower bound tightens to current node value
- Common mistake: only comparing a node to its direct parent instead of the full inherited range
BST Validation with Range Bounds
C++Node 4 is a valid right child of 7 locally, but violates the global rule that everything right of 5 must be greater than 5.
Convert Sorted Array to Balanced BST
Pick the middle element of the sorted array as the root. Recursively apply the same rule to the left half and right half. This guarantees the resulting BST is height-balanced.
Divide and Conquer Build
The middle element becomes the root. Left half builds the left subtree; right half builds the right subtree.
- mid = (lo + hi) / 2 at each recursive call
- Left subtree: subarray from lo to mid - 1
- Right subtree: subarray from mid + 1 to hi
- Height of the resulting BST is O(log n) since both halves are equal in size
Sorted Array to Balanced BST
C++Choosing mid as root each time ensures the tree never becomes skewed. The root will be 4 for a 7-element array.
Kth Smallest Element in BST
Because inorder traversal of a BST yields values in sorted order, the kth smallest element is simply the kth node visited during inorder traversal. This runs in O(h + k) time.
Inorder Count Trick
Maintain a counter during inorder traversal. When the counter reaches k, the current node holds the kth smallest value.
- Traverse left subtree first (smaller values)
- Increment counter when visiting a node
- Return the node value when counter == k
- Short-circuit: stop as soon as k is reached (no need to visit the rest)
Kth Smallest via Inorder
C++Decrement k at each visited node. When k hits 0, the current node is the answer. Early return skips unnecessary traversal.
Lowest Common Ancestor in BST
LCA in a BST is faster than in a general binary tree. Since values are ordered, if both p and q are less than the current node, go left. If both are greater, go right. Otherwise the current node is the LCA.
BST LCA in O(h)
The BST property lets you navigate directly to the LCA without a full postorder scan.
- If both p and q are smaller than root, LCA is in the left subtree
- If both p and q are larger than root, LCA is in the right subtree
- If they split (one on each side) or one equals root, root is the LCA
- Works in O(h) time vs O(n) for a general binary tree
LCA in BST (Iterative)
C++No recursion overhead needed. The split-point condition is the only check required at each step.
Two Sum in BST
Find if any two nodes in a BST sum to a given target. The approach uses inorder traversal to extract the sorted sequence and then applies the two-pointer technique on it.
Inorder + Two Pointers
Inorder traversal of a BST gives a sorted array. Two pointers on the sorted array find a pair summing to target in O(n) time and O(n) space.
- Step 1: inorder traversal to collect all values in a sorted vector
- Step 2: left pointer at index 0, right pointer at the last index
- If sum == target: pair found. If sum < target: move left right. If sum > target: move right left.
- Time: O(n), Space: O(n). An O(h) space BST iterator approach also exists.
Two Sum in BST
C++Inorder gives a sorted array. The two-pointer scan then finds any pair summing to target in one pass.
BST to Sorted Doubly Linked List
Convert a BST to a sorted doubly linked list in-place by treating the left pointer as the prev link and the right pointer as the next link. Inorder traversal wires the nodes in sorted order.
In-Place DLL Conversion
During inorder traversal, maintain a prev pointer. Link prev->right to current and current->left to prev, building the DLL as you go.
- Use a prev pointer (initially null) to track the last linked node
- On visiting a node: set prev->right = curr and curr->left = prev
- Advance prev to curr after linking
- After traversal, find the head by following left pointers from any node back to the start
BST to Sorted DLL In-Place
C++No new nodes are created. Left pointers become prev links; right pointers become next links during inorder traversal.
Knowledge Check
1. Which property must a BST satisfy at every node?
2. What is the average time complexity of search in a balanced BST?
3. When deleting a node with two children from a BST, it is replaced by:
4. The inorder traversal of a valid BST produces:
5. To validate a BST, you pass down:
6. Converting a sorted array to a balanced BST uses which strategy?
7. The inorder successor of a node in a BST is:
8. The LCA of two nodes p and q in a BST can be found by: