Course contentsShow
← Computer Science
Lesson 528 of 2,87212. Binary Search TreesFree lesson

BST with Duplicate Keys

Analyzing performance implications when allowing duplicate values in a BST structure.

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:

  1. Store duplicates to the left (or right) - Modify the invariant to left ≤ root < right
  2. 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.