BST with Duplicate Keys
You'll learn how allowing duplicate values in a Binary Search Tree affects insertion, search, and deletion performance.
The Core Problem
Standard BSTs typically disallow duplicates to maintain the clean property: left < root < right. But what if your application needs to store duplicate values—like tracking multiple purchases of the same amount? You have two main options:
- Store duplicates to the left (or right) - Modify the invariant to left ≤ root < right
- Keep a count field in each node - One node per unique value, with a counter
Both approaches work, but they impact performance differently.
Performance Implications
Storing duplicates as separate nodes:
- Worst case gets worse: If you insert the same value repeatedly, you create a long chain in one direction (like a linked list), degrading search/insertion from O(log n) to O(n)
- Space overhead: More nodes mean more memory for pointers
- Deletion complexity: You might need to remove only one duplicate, requiring you to traverse duplicates
Using a count field:
- Better height preservation: Tree height depends on unique values, not total elements
- More compact: One node stores many occurrences
- Simpler operations: Insertion just increments a counter; deletion decrements (remove node when count hits zero)
- Caveat: Finding the "kth smallest element" becomes trickier—you must account for counts when traversing
Practical Impact
If duplicates are rare, separate nodes work fine. But with many duplicates (like logging timestamps or transaction amounts), the count-based approach dramatically improves balance and performance by keeping the tree shallow.
Key Takeaway:
Allowing duplicate keys in a BST can degrade performance to O(n) if stored as separate nodes; using a count field per node maintains better tree height and performance while handling duplicates efficiently.