Introduction

Many different insertion orders can build the same binary search tree. The key idea is that the first element fixes the root, the left-subtree values must stay relative to the left subtree, the right-subtree values must stay relative to the right subtree, and the two sides can then be interleaved in combinatorially many ways.

Split the Sequence by the Root

In BST insertion, the first value in the sequence becomes the root. Every later value smaller than the root belongs somewhere in the left subtree, and every later value larger than the root belongs somewhere in the right subtree.

For example, in:

[4, 2, 1, 3, 6, 5, 7]

the split is:

• root: 4
• left subsequence: [2, 1, 3]
• right subsequence: [6, 5, 7]

Any other permutation that produces the same BST must still respect that split. It cannot suddenly place a right-subtree value into the left side of the tree.

Count the Interleavings

Suppose the left side has L values and the right side has R values. After fixing the root, there are L + R positions remaining. Choosing which L of those positions are occupied by left-subtree values gives:

C(L + R, L)

ways to weave the left and right subsequences together.

But that is only part of the answer. The left subsequence itself must still produce the same left subtree, and the right subsequence must still produce the same right subtree. So the full recurrence is:

count(values) = C(L + R, L) x count(left) x count(right)

That is why this is a recursive combinatorics problem rather than a single binomial coefficient.

Implement the Recurrence in Python

1from math import comb
2
3def count_same_bst_orders(values: list[int]) -> int:
4    if len(values) <= 2:
5        return 1
6
7    root = values[0]
8    left = [x for x in values[1:] if x < root]
9    right = [x for x in values[1:] if x > root]
10
11    return (
12        comb(len(left) + len(right), len(left))
13        * count_same_bst_orders(left)
14        * count_same_bst_orders(right)
15    )
16
17print(count_same_bst_orders([2, 1, 3]))
18print(count_same_bst_orders([4, 2, 1, 3, 6, 5, 7]))

For [2, 1, 3], the answer is 2, because both [2, 1, 3] and [2, 3, 1] build the same BST.

Why Relative Order Still Matters Inside Each Side

The left and right values are not free to permute arbitrarily. For example, if the left subsequence is [2, 1, 3], not every reordering of those three values produces the same left subtree.

That is why the recursive part is essential. The combination counts only how many ways the left and right subsequences can be interleaved. It does not enforce subtree structure by itself.

So the logic is:

• recurse to count valid left-subtree orders
• recurse to count valid right-subtree orders
• multiply by the number of valid interleavings between those two subsequences

Practical Notes

This approach assumes the values are distinct. If duplicates are allowed, you need an extra rule for where equal keys go, because duplicate-handling policy changes the tree shape and the counting logic.

Some programming problems also ask for the number of reorderings other than the original input. In that case, subtract one at the end:

result = count_same_bst_orders([4, 2, 1, 3, 6, 5, 7]) - 1
print(result)

That detail changes the final numeric answer, so it is worth checking the exact wording of the problem.

Common Pitfalls

• Forgetting that the first element must remain the root for any valid reorder.
• Counting only left-right interleavings and ignoring recursive subtree constraints.
• Assuming the method works unchanged when duplicates are present.
• Forgetting whether the problem wants all valid orders or only alternatives excluding the original one.
• Recomputing combinations inefficiently instead of using a helper such as math.comb.

Summary

• The first inserted value fixes the BST root.
• Split the remaining sequence into left and right subsequences relative to that root.
• Count the ways to interleave those subsequences with a binomial coefficient.
• Multiply by the recursive counts for the left and right subtrees.
• If the problem asks for alternative reorderings only, subtract one from the full count at the end.