Number of Ways to Reorder Array to Get Same BST

Number of Ways to Reorder Array to Get Same BST

What is this problem about?

The Number of Ways to Reorder Array to Get Same BST problem asks you to count the number of reorderings of an array (excluding the original) that produce the same Binary Search Tree structure when elements are inserted in the given order. This hard coding problem uses divide and conquer with combinatorics at each recursive split.

Why is this asked in interviews?

DE Shaw and Google ask this because it requires understanding that the relative order of left-subtree elements and right-subtree elements can be freely interleaved (as long as each group's internal order is preserved), while the root must always come first. The multiply of C(left+right, left) at each recursive level gives the total count. The array, union find, math, divide and conquer, BST, memoization, combinatorics, binary tree, dynamic programming, and tree interview pattern is comprehensively tested.

Algorithmic pattern used

Recursive divide + combinatorics. The first element of any valid ordering is always the root. Split remaining elements into left group (< root) and right group (≥ root). Count valid orderings: C(left_size + right_size, left_size) * f(left_group) * f(right_group). This is because we can interleave left and right subsequences in any way that preserves their relative order. Subtract 1 for the original ordering.

Example explanation

arr=[2,1,3]. BST: root=2, left=1, right=3.

• Root=2 (fixed first).
• Left=[1], Right=[3]. Left_size=1, right_size=1.
• C(2,1)=2 interleavings: [2,1,3] and [2,3,1].
• f([1])=1, f([3])=1.
• Total orderings = C(2,1)11=2. Subtract original: 2-1=1.

arr=[3,1,2,4]. Root=3. Left=[1,2], Right=[4]. C(3,2)=3. f([1,2])=1 (only [1,2] gives same BST for this subtree). f([4])=1. Total=311=3. Subtract 1=2.

Common mistakes candidates make

• Not recognizing that within each subtree group, relative order must be preserved.
• Using permutations instead of combinations for interleaving count.
• Not subtracting 1 for the original ordering.
• Off-by-one in the combinatorics formula.

Interview preparation tip

BST reordering problems use the "interleave two sequences" counting formula: C(n+m, n) ways to interleave an n-element and m-element sequence while preserving each sequence's internal order. This appears in shuffle problems and merge counting. Once you derive the recursive structure (root fixed, left and right groups interleaved multiplicatively), implement with memoization and modular combination tables. Practice precomputing Pascal's triangle for fast C(n,k) mod p.