# Number of Ways to Reorder Array to Get Same BST
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-reorder-array-to-get-same-bst
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Tree, Binary Tree, Binary Search Tree
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
Given an array `nums` that represents a permutation of integers from `1` to `n`. We are going to construct a binary search tree (BST) by inserting the elements of `nums` in order into an initially empty BST. Find the number of different ways to reorder `nums` so that the constructed BST is identical to that formed from the original array `nums`.

* For example, given `nums = [2,1,3]`, we will have 2 as the root, 1 as a left child, and 3 as a right child. The array `[2,3,1]` also yields the same BST but `[3,2,1]` yields a different BST.

Return _the number of ways to reorder_ `nums` _such that the BST formed is identical to the original BST formed from_ `nums`.

Since the answer may be very large, **return it modulo** `109 + 7`.

**Example 1:**

![](https://assets.glich.co/dsa/number-of-ways-to-reorder-array-to-get-same-bst/image0.png) 

**Input:** nums = [2,1,3]
**Output:** 1
**Explanation:** We can reorder nums to be [2,3,1] which will yield the same BST. There are no other ways to reorder nums which will yield the same BST.

**Example 2:**

![](https://assets.glich.co/dsa/number-of-ways-to-reorder-array-to-get-same-bst/image1.png) 

**Input:** nums = [3,4,5,1,2]
**Output:** 5
**Explanation:** The following 5 arrays will yield the same BST: 
[3,1,2,4,5]
[3,1,4,2,5]
[3,1,4,5,2]
[3,4,1,2,5]
[3,4,1,5,2]

**Example 3:**

![](https://assets.glich.co/dsa/number-of-ways-to-reorder-array-to-get-same-bst/image2.png) 

**Input:** nums = [1,2,3]
**Output:** 0
**Explanation:** There are no other orderings of nums that will yield the same BST.

**Constraints:**

* `1 <= nums.length <= 1000`
* `1 <= nums[i] <= nums.length`
* All integers in `nums` are **distinct**.

# Approaches
## Recursive Approach with List Partitioning
This approach uses a direct divide-and-conquer strategy. The number of valid reorderings for a sequence `nums` is determined by its root (`nums[0]`) and the elements forming its left and right subtrees. We can recursively calculate the number of ways for the left and right subtrees and combine the results. The key insight is that the elements of the left and right subtrees can be interleaved in any way, as long as their internal relative order is preserved. The number of ways to interleave them is given by a binomial coefficient, which we can precompute.
**Time:** O(N^2). The recursive function `countWays` is called on lists of decreasing sizes. For a list of size `k`, it performs `O(k)` work to partition it. The recurrence relation for the time complexity is `T(n) = T(k) + T(n-1-k) + O(n)`, which solves to `O(n^2)` in the worst case (skewed tree). Precomputing combinations also takes `O(N^2)`. · **Space:** O(N^2). The recursion depth can be up to `O(N)`. At each level, new lists are created for subproblems. The total size of lists stored on the recursion stack can be `O(N^2)` in the worst case (a skewed tree). The `combinations` table also requires `O(N^2)` space.
**Pros:** Conceptually simple and directly models the recursive nature of the problem.; Easy to implement.
**Cons:** High space complexity (`O(N^2)`) due to creating new lists at each recursive call.; The overhead of list creation and copying can make it slower in practice than other `O(N^2)` solutions.
### Explanation
The core of this method is a recursive function, let's call it `countWays(nums)`, which computes the total number of valid permutations for a given sequence `nums` that forms a specific BST structure.

The base case for the recursion is when the input list `nums` has a size of 2 or less. In such cases, the structure is fixed, and there's only one way to arrange the elements, so we return 1.

For a list with more than two elements, the first element `nums[0]` will always be the root of the BST formed by this sequence. We then iterate through the rest of the list (`nums[1:]`) and partition the elements into two new lists: `leftNodes` for all elements smaller than the root, and `rightNodes` for all elements larger than the root. It's crucial that this partitioning preserves the original relative order of elements within each new list.

The problem then breaks down into three parts: arranging the left subtree, arranging the right subtree, and interleaving these two arrangements. The number of ways to arrange the left and right subtrees are found by recursively calling `countWays(leftNodes)` and `countWays(rightNodes)`.

The number of ways to interleave the two sequences of nodes (for the left and right subtrees) is a classic combinatorial problem. If `leftNodes` has size `L` and `rightNodes` has size `R`, we have `L+R` total positions to fill. We need to choose `L` of these positions for the `leftNodes` elements. This can be done in `C(L+R, L)` ways. We can precompute these combination values using Pascal's triangle.

The total number of ways for the current `nums` is the product of these three values: `C(L+R, L) * countWays(leftNodes) * countWays(rightNodes)`, all taken modulo `10^9 + 7`.

Finally, the main function calls `countWays` with the initial `nums` array and subtracts 1 from the result, as the problem asks for the number of *other* reorderings that produce the same BST.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    long[][] combinations;
    long MOD = 1_000_000_007;

    public int numOfWays(int[] nums) {
        int n = nums.length;
        List<Integer> arr = new ArrayList<>();
        for (int num : nums) {
            arr.add(num);
        }

        // Precompute combinations using Pascal's triangle
        combinations = new long[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            combinations[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                combinations[i][j] = (combinations[i - 1][j - 1] + combinations[i - 1][j]) % MOD;
            }
        }

        long totalWays = countWays(arr);
        // The problem asks for the number of ways to reorder, which is total ways - 1
        return (int) ((totalWays - 1 + MOD) % MOD);
    }

    private long countWays(List<Integer> nums) {
        if (nums.size() <= 2) {
            return 1;
        }

        int rootVal = nums.get(0);
        List<Integer> leftSubtree = new ArrayList<>();
        List<Integer> rightSubtree = new ArrayList<>();

        for (int i = 1; i < nums.size(); i++) {
            if (nums.get(i) < rootVal) {
                leftSubtree.add(nums.get(i));
            } else {
                rightSubtree.add(nums.get(i));
            }
        }

        long leftWays = countWays(leftSubtree);
        long rightWays = countWays(rightSubtree);

        int leftSize = leftSubtree.size();
        int rightSize = rightSubtree.size();

        long interleavingWays = combinations[leftSize + rightSize][leftSize];
        
        long result = (interleavingWays * leftWays) % MOD;
        result = (result * rightWays) % MOD;

        return result;
    }
}
```
### Algorithm
*   **Main Idea:** Use a recursive function `countWays(nums)` that calculates the number of valid permutations for a sequence `nums` representing a subtree.
*   **Base Case:** If `nums` has 2 or fewer elements, there's only one way to form the BST. Return 1.
*   **Recursive Step:**
    1.  The first element, `nums[0]`, is the root of the current subtree.
    2.  Partition the remaining elements of `nums` into two new lists: `leftNodes` (elements `< root`) and `rightNodes` (elements `> root`), preserving their relative order.
    3.  Recursively call `countWays(leftNodes)` and `countWays(rightNodes)` to get the number of arrangements for the subtrees.
    4.  The number of ways to interleave the left and right subtree sequences is given by the binomial coefficient `C(leftNodes.size() + rightNodes.size(), leftNodes.size())`.
    5.  The total ways for the current `nums` is `(C(...) * leftWays * rightWays) % MOD`.
*   **Combinations:** Precompute binomial coefficients `C(n, k)` using Pascal's triangle and store them in a 2D array.
*   **Final Result:** The main function calls `countWays` on the initial array and subtracts 1 from the result (to exclude the original ordering).

## Build BST then Count Ways
This approach improves upon the pure recursive one by separating the problem into two distinct phases. First, we explicitly construct the Binary Search Tree from the input array `nums`. This step determines the fixed structure of the tree. Second, we perform a single post-order traversal on the constructed BST. During the traversal, we calculate the size of each subtree and use this information along with precomputed combination values to find the number of valid reorderings for that subtree. This avoids the expensive creation of new lists at each step of the recursion.
**Time:** O(N^2). Building the BST takes `O(N^2)` in the worst case (e.g., for a sorted `nums` array). The traversal to count ways takes `O(N)`. Precomputing combinations takes `O(N^2)`. The total time is dominated by the BST construction and combinations precomputation. · **Space:** O(N^2). The BST requires `O(N)` space. The recursion stack for traversal takes `O(N)` in the worst case. The `combinations` table using Pascal's triangle takes `O(N^2)` space. Note: This can be optimized to `O(N)` space by precomputing factorials and their modular inverses instead of the full combinations table.
**Pros:** More space-efficient than the pure recursive approach. Can achieve `O(N)` space if combinations are computed using factorials.; Cleaner separation of concerns: first building the structure, then performing calculations on it.; Generally faster in practice due to avoiding list manipulation overhead.
**Cons:** The worst-case time complexity is still `O(N^2)` due to BST construction for skewed inputs (like a sorted array).
### Explanation
This method is more structured and generally more efficient, especially in terms of space. It works in two main phases.

**Phase 1: Build the BST**
First, we determine the exact structure of the BST. We define a simple `Node` class and build the tree by inserting each element from the `nums` array in the given order. `nums[0]` becomes the root, and subsequent elements are inserted based on standard BST rules. This construction takes `O(N^2)` in the worst case (for a skewed tree) but `O(N log N)` on average.

**Phase 2: Traverse and Count**
Once the tree is built, its structure is fixed. We can now traverse it to count the number of ways. We use a recursive helper function, say `dfs(node)`, which performs a post-order traversal. This function is designed to return a pair of values for the subtree rooted at `node`: the total number of nodes in that subtree, and the number of ways to reorder the elements of that subtree to form the same structure.

The base case is a `null` node, which represents an empty subtree. It has a size of 0 and there is 1 way to arrange it (the empty arrangement).

For any given node, `dfs` first recursively calls itself on the left and right children. This gives us the sizes and way counts for the left and right subtrees, say `(leftSize, leftWays)` and `(rightSize, rightWays)`. The total number of nodes in the current subtree is `1 + leftSize + rightSize`. The number of ways to reorder the elements of this subtree is calculated using the same combinatorial formula as before: `C(leftSize + rightSize, leftSize) * leftWays * rightWays`. The binomial coefficients `C(n, k)` are precomputed.

The `dfs` call on the root of the entire BST will yield the total number of permutations that form the identical tree. We subtract 1 from this total to get the final answer.

This approach is more space-efficient because we are not creating copies of lists. The space for the BST and recursion stack is `O(N)`, and if we use factorials to compute combinations, the total space complexity can be `O(N)`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
    }

    // A pair to return both size and ways from the recursive helper
    static class Pair {
        int size;
        long ways;
        Pair(int s, long w) { size = s; ways = w; }
    }

    long[][] combinations;
    long MOD = 1_000_000_007;

    public int numOfWays(int[] nums) {
        int n = nums.length;
        if (n <= 2) return 0;

        // Phase 1: Build BST
        Node root = new Node(nums[0]);
        for (int i = 1; i < n; i++) {
            insert(root, nums[i]);
        }

        // Precompute combinations table
        combinations = new long[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            combinations[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                combinations[i][j] = (combinations[i - 1][j - 1] + combinations[i - 1][j]) % MOD;
            }
        }

        // Phase 2: Traverse and count ways
        Pair result = countWays(root);
        return (int)((result.ways - 1 + MOD) % MOD);
    }

    private void insert(Node node, int val) {
        while (true) {
            if (val < node.val) {
                if (node.left == null) {
                    node.left = new Node(val);
                    return;
                }
                node = node.left;
            } else {
                if (node.right == null) {
                    node.right = new Node(val);
                    return;
                }
                node = node.right;
            }
        }
    }

    private Pair countWays(Node node) {
        if (node == null) {
            return new Pair(0, 1L); // {size, ways}
        }

        Pair leftResult = countWays(node.left);
        Pair rightResult = countWays(node.right);

        int leftSize = leftResult.size;
        int rightSize = rightResult.size;
        long leftWays = leftResult.ways;
        long rightWays = rightResult.ways;

        int totalSize = leftSize + rightSize + 1;
        
        long interleavingWays = combinations[leftSize + rightSize][leftSize];
        
        long totalWays = (interleavingWays * leftWays) % MOD;
        totalWays = (totalWays * rightWays) % MOD;

        return new Pair(totalSize, totalWays);
    }
}
```
### Algorithm
*   **Phase 1: Build BST**
    1.  Define a `Node` class for the BST nodes.
    2.  Create the BST by inserting elements from the input `nums` array one by one, starting with `nums[0]` as the root.
*   **Phase 2: Count Ways via Traversal**
    1.  Precompute binomial coefficients `C(n, k)`. This can be done with an `O(N^2)` Pascal's triangle or, more efficiently for space, with `O(N)` precomputation of factorials and their modular inverses.
    2.  Implement a recursive traversal function, `dfs(node)`, that returns a pair: `{subtree_size, ways_for_subtree}`.
    3.  **Base Case:** For a `null` node, `dfs` returns `{size: 0, ways: 1}`.
    4.  **Recursive Step:** For a non-null `node`, call `dfs` on its left and right children to get `(leftSize, leftWays)` and `(rightSize, rightWays)`.
    5.  Calculate the results for the current node: `totalSize = 1 + leftSize + rightSize` and `totalWays = C(leftSize + rightSize, leftSize) * leftWays * rightWays % MOD`.
    6.  Return `{totalSize, totalWays}`.
*   **Final Result:** Call `dfs(root)` and subtract 1 from the returned number of ways.

# Solutions
### Java

```java
class Solution {
private
  int[][] c;
private
  final int mod = (int)1 e9 + 7;
public
  int numOfWays(int[] nums) {
    int n = nums.length;
    c = new int[n][n];
    c[0][0] = 1;
    for (int i = 1; i < n; ++i) {
      c[i][0] = 1;
      for (int j = 1; j <= i; ++j) {
        c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
      }
    }
    List<Integer> list = new ArrayList<>();
    for (int x : nums) {
      list.add(x);
    }
    return (dfs(list) - 1 + mod) % mod;
  }
private
  int dfs(List<Integer> nums) {
    if (nums.size() < 2) {
      return 1;
    }
    List<Integer> left = new ArrayList<>();
    List<Integer> right = new ArrayList<>();
    for (int x : nums) {
      if (x < nums.get(0)) {
        left.add(x);
      } else if (x > nums.get(0)) {
        right.add(x);
      }
    }
    int m = left.size(), n = right.size();
    int a = dfs(left), b = dfs(right);
    return (int)((long)a * b % mod * c[m + n][n] % mod);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numOfWays(vector<int> &nums) {
    int n = nums.size();
    const int mod = 1e9 + 7;
    int c[n][n];
    memset(c, 0, sizeof(c));
    c[0][0] = 1;
    for (int i = 1; i < n; ++i) {
      c[i][0] = 1;
      for (int j = 1; j <= i; ++j) {
        c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
      }
    }
    function<int(vector<int>)> dfs = [&](vector<int> nums) -> int {
      if (nums.size() < 2) {
        return 1;
      }
      vector<int> left, right;
      for (int &x : nums) {
        if (x < nums[0]) {
          left.push_back(x);
        } else if (x > nums[0]) {
          right.push_back(x);
        }
      }
      int m = left.size(), n = right.size();
      int a = dfs(left), b = dfs(right);
      return c[m + n][m] * 1ll * a % mod * b % mod;
    };
    return (dfs(nums) - 1 + mod) % mod;
  }
};

```

### Python

```python
class Solution:
    def numOfWays(self, nums: List[int]) -> int: def dfs(nums): if len(nums) < 2: return 1 left = [x for x in nums if x < nums[0]] right = [x for x in nums if x > nums[0]] m, n = len(left), len(right) a, b = dfs(left), dfs(right) return (((c[m + n][m] * a) % mod) * b) % mod n = len(nums) mod = 10 ** 9 + 7 c = [[0] * n for _ in range(n)] c[0][0] = 1 for i in range(1, n): c[i][0] = 1 for j in range(1, i + 1): c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod return (dfs(nums) - 1 + mod) % mod

```