Introduction

For a fixed BST shape, many different insertion orders can produce the same tree. The key rule is that the root must be inserted first, and within the remaining sequence the relative order of nodes in the left subtree and right subtree must each be preserved.

Core Sections

Why multiple insertion orders can lead to the same BST

Suppose the final BST is:

    3
   /   1   5
   \       2   7

If you insert 3 first, then any valid interleaving of the left-subtree insertion order and the right-subtree insertion order can still reproduce the same final tree, as long as each side keeps its internal order constraints.

For example, these are both valid:

• '3, 1, 2, 5, 7'
• '3, 5, 1, 7, 2'

Both produce the same BST because all left-subtree values remain less than 3, all right-subtree values remain greater than 3, and the insertion order inside each subtree is still compatible with that subtree's shape.

The recursive counting rule

If a tree has:

• 'L nodes in the left subtree'
• 'R nodes in the right subtree'

and the number of valid insertion sequences for those subtrees is count(left) and count(right), then the total number of valid sequences for the whole tree is:

choose(L + R, L) * count(left) * count(right)

The binomial coefficient counts how many ways you can interleave the left and right subtree insertion sequences while preserving each side's internal order.

Example calculation

Consider this BST:

    2
   /   1   3

The left subtree has one node and the right subtree has one node.

• 'count(left) = 1'
• 'count(right) = 1'
• 'choose(2, 1) = 2'

So the valid insertion orders are:

• '2, 1, 3'
• '2, 3, 1'

That matches the formula exactly.

Recursive implementation in Python

1from math import comb
2
3class Node:
4    def __init__(self, value, left=None, right=None):
5        self.value = value
6        self.left = left
7        self.right = right
8
9
10def count_sequences(node):
11    if node is None:
12        return 1, 0
13
14    left_count, left_size = count_sequences(node.left)
15    right_count, right_size = count_sequences(node.right)
16
17    ways_to_merge = comb(left_size + right_size, left_size)
18    total = ways_to_merge * left_count * right_count
19    size = 1 + left_size + right_size
20    return total, size
21
22
23root = Node(2, Node(1), Node(3))
24print(count_sequences(root)[0])

This prints the number of insertion sequences that generate the given BST shape.

Generating the actual sequences

Counting is much easier than listing every valid permutation. To generate the sequences themselves, you recursively generate all valid left sequences and right sequences, then weave them together while preserving internal order.

That is feasible for small trees, but the total number of sequences grows quickly. For anything beyond toy sizes, it is usually better to count them rather than materialize them all.

Common Pitfalls

• Treating the problem like ordinary permutation generation and ignoring the ordering constraints inside each subtree.
• Forgetting that the root must always be first in any insertion sequence that produces the same BST.
• Counting interleavings without multiplying by the valid sequence counts of the left and right subtrees.
• Trying to generate every sequence for large trees when the number of valid orders grows combinatorially.
• Confusing the number of possible BST shapes with the number of insertion orders for one fixed BST.

Summary

• Many insertion orders can produce the same BST, but they must preserve subtree ordering constraints.
• The root value must appear first.
• The total count is choose(L + R, L) * count(left) * count(right).
• Counting valid orders is usually more practical than generating them all.
• The problem is recursive because each subtree has the same structure-and-interleaving logic.