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

Handling Duplicate Keys

Discuss strategies for duplicates: disallow them, store in left, store in right, or use counts.

Handling Duplicate Keys

You'll learn: What options exist when a duplicate key tries to enter a Binary Search Tree.

When implementing a BST, you must decide what happens if someone tries to insert a key that already exists. There's no universal "correct" answer—different applications have different needs.

The Four Main Strategies

1. Disallow Duplicates

Simply reject the insertion if the key exists. Return false or throw an error. This keeps the BST clean and simple—each key appears exactly once.

Analogy: Like a club with strict "no re-entry" rules.

2. Store in Left Subtree

Treat duplicates as "less than or equal to" and always place them in the left child's subtree. Your BST invariant becomes: left ≤ root < right.

Analogy: When two people have the same ticket number, you consistently send them to the left line.

3. Store in Right Subtree

The mirror approach: treat duplicates as "greater than or equal to" and place them right. Your invariant becomes: left < root ≤ right.

Analogy: Same situation, but you always send duplicates to the right line.

4. Use a Count Field

Store a counter in each node. When a duplicate arrives, increment the count instead of adding a new node. This saves space when you have many duplicates.

Analogy: Instead of writing "apple, apple, apple" on separate cards, write "apple (×3)" on one card.

Choosing Your Strategy

  • Disallow: Best when keys represent unique identifiers (employee IDs, usernames)
  • Left/Right: Simple to implement, but can unbalance the tree with many duplicates
  • Count: Most space-efficient for high-duplicate datasets (word frequency counters)

Key Takeaway: BSTs don't inherently handle duplicates—you must choose a strategy based on your application's requirements, trading off between simplicity, space efficiency, and operational needs.