# Number of Ways to Reorder Array to Get Same BST

This page explains Java solution to problem `Number of Ways to Reorder Array to Get Same BST` using `Dynamic Programming` algorithm.

## Problem Statement

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 `10^9 + 7`.

Example 1:

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:

Input: [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:

Input: nums = [1,2,3]
Output: 0

Example 4:

Input: nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]
Output: 216212978
Explanation: The number of ways to reorder nums to get the same BST is 3216212999. Taking this number modulo 10^9 + 7 gives 216212978.

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class NumberOfWaysToReorderArrayToGetSameBst {
private long[][] pascal;
private int MOD = (int)1e9 + 7;

public int numOfWays(int[] nums) {
int n = nums.length;
generatePascal(n + 1);

List<Integer> numbers = new ArrayList<>();
for(int i = 0; i < nums.length; i++) numbers.add(nums[i]);

//-1 because one permutation is already given as an input
return (int)helper(numbers) - 1;
}

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

int root = nums.get(0);
List<Integer> left = new ArrayList<>();
List<Integer> right = new ArrayList<>();

for(int i = 1; i < nums.size(); i++) {
int num = nums.get(i);
}

/**
How many different ways we can arrange left.size() elements in left.size() + right.size() elements

Let's say we have [3, 4, 5, 1, 2] as original array with root value is 3

[1, 2] left sub-tree, left.size() = 2
[4, 5] right sub-tree, right.size() = 2

In all of below permutations, we keep relative position in left & right subtree,
But we can absolute position
[1, 2, 4, 5]
[1, 4, 2, 5]
[1, 4, 5, 2]
[4, 1, 2, 5]
[4, 1, 5, 2]
[4, 5, 1, 2]
*/
return pascal[left.size() + right.size()][left.size()] % MOD *
helper(left) % MOD *
helper(right) % MOD;
}

private void generatePascal(int n) {
pascal = new long[n][n];
for(int row = 0; row < n; row++) pascal[row][0] = pascal[row][row] = 1;

for(int row = 2; row < n; row++) {
for(int col = 1; col < row; col++) {
pascal[row][col] = (pascal[row - 1][col] + pascal[row - 1][col - 1]) % MOD;
}
}
}
}
``````

## Time Complexity

O(N2) Where
N is number of elements in an input array nums

## Space Complexity

O(N * N) Where
N is number of elements in an input array nums