Introduction

Whether duplicates in a binary search tree are allowed depends on the tree's insertion rule. Some BST implementations reject duplicates, some always send equal values to one side, and some store a count in each node. Because of that, the right duplicate-detection strategy starts with a simple question: are you checking a valid BST for repeated values, or are you checking an arbitrary tree-like structure that may already violate BST ordering?

Use In-Order Traversal for a Valid BST

If the tree really is a valid BST, an in-order traversal visits values in sorted order. That makes duplicate detection easy. You only need to compare each visited value with the previous one.

1class Node:
2    def __init__(self, value, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6
7
8def has_duplicate_bst(root):
9    prev = [None]
10    found = [False]
11
12    def inorder(node):
13        if node is None or found[0]:
14            return
15
16        inorder(node.left)
17
18        if prev[0] is not None and prev[0] == node.value:
19            found[0] = True
20            return
21
22        prev[0] = node.value
23        inorder(node.right)
24
25    inorder(root)
26    return found[0]

This runs in O(n) time because every node is visited once. The extra space is O(h) from recursion, where h is the tree height.

Why This Works

In a valid BST, the left subtree contains smaller values and the right subtree contains larger values according to the chosen comparison rule. That means in-order traversal produces a non-decreasing sequence. If a value appears twice, the duplicates will appear next to each other in that traversal order.

That is the crucial insight. You do not need a hash set if BST ordering is trustworthy.

Use a Set if the Tree Might Already Be Broken

If the structure may violate BST rules, the in-order sorted-order guarantee disappears. In that case, the safest general strategy is to traverse every node and track seen values in a set:

1def has_duplicate_any_tree(root):
2    seen = set()
3
4    def walk(node):
5        if node is None:
6            return False
7
8        if node.value in seen:
9            return True
10
11        seen.add(node.value)
12        return walk(node.left) or walk(node.right)
13
14    return walk(root)

This is still O(n) time, but it uses O(n) extra space in the worst case. It is more general because it does not rely on any ordering property.

Another Design: Store Counts Instead of Repeated Nodes

If duplicates are expected by design, repeatedly inserting equal-valued nodes can complicate search rules. A cleaner design is often to store a count per key:

1class CountNode:
2    def __init__(self, value):
3        self.value = value
4        self.count = 1
5        self.left = None
6        self.right = None

Then insertion increments count when the value already exists instead of creating another node. In that model, finding duplicates becomes trivial: any node with count > 1 represents duplicates.

This is often easier to reason about than deciding whether equal values should go left or right forever.

Think About the Real Goal

Sometimes the question is not "does the tree contain duplicates" but "where are the duplicates" or "how many duplicates exist." The traversal strategy remains similar, but the output changes:

• boolean result if you only need detection
• list of repeated keys if you need reporting
• count frequencies if you need auditing

Once you know the exact goal, the implementation becomes more obvious.

Common Pitfalls

• Using in-order traversal on a structure that is no longer a valid BST.
• Forgetting to define how duplicates are represented in the tree design.
• Assuming duplicates must be adjacent in traversal order when the BST property is already broken.
• Using a full hash set when a previous-value comparison would work on a valid BST.
• Solving for detection only when the real requirement is frequency counting or duplicate reporting.

Summary

• For a valid BST, in-order traversal plus previous-value comparison is the most efficient duplicate check.
• If the tree might violate BST ordering, use a set-based traversal instead.
• Both approaches run in O(n) time, but the set approach uses more memory.
• If duplicates are expected, storing a count per node is often cleaner than inserting repeated nodes.
• Choose the strategy based on whether the BST property can be trusted and what result you actually need.