A binary search tree is a data structure where each node has two child nodes at most, with the left child having a smaller value than the node and the right child having a larger value. The order in which elements are inserted into a binary search tree determines the tree’s shape.

So, without further ado, let’s jump into the problem statement.

Problem statement

Given an array “nums[]” of size ‘n’, which stores the elements from the range [1, n], the order of the elements in the array tells the order in which nodes are inserted into the Binary search tree, The task is to count permutations of the array that give the same binary search tree. As the number of such permutations can be large, Output it modulo 10^9 + 7.

Example

Input

n = 4
nums[] = {2, 1, 4, 3};

Output

3

Explanation

The following BST will be generated by inserting nodes in the given order:

The following arrays will yield the same BST, which will make the count of permutations 6:

[2, 1, 4, 3] (Given)

[2, 4, 3, 1]

[2, 4, 1, 3]

Now let’s make BST using the second array - [2, 4, 3, 1].

First, we insert 2. Currently, the tree is just a single node 2:

Then we insert 4. It has to go on the right of 2 as it is larger. The tree becomes:

Then we insert 3. As 3 is smaller than 4, it goes to the left of 4. The tree becomes:

Then we insert 1. The tree becomes:

All the listed arrays will result in the same BST.

Approach

The main idea of the approach is to recursively count the number of permutations of the input array that can form the same binary search tree. The approach is based on the following observation: For a given binary search tree, any permutation of its nodes that preserves the relative ordering of the nodes in the tree will also form the same binary search tree.

Let’s see the algorithm step-by-step:

Algorithm

The first element on the input array is BST’s root.

The remaining elements of the array are then divided into two sub-sequences, one for the left subtree and the other for the right subtree. If the element is smaller than the root, it belongs to the left subtree, or else it belongs to the right subtree.

The number of permutations for the two subtrees is calculated recursively. The answer for subtrees can be combined using the product of permutations of the left subtree, permutations of the right subtree, and ways to interleave these two permutations preserving their relative order.

The base case of recursion is based on the fact that if the input array size is less than or equal to 2, only one permutation can result in the same BST.

In how many ways can we interleave two permutations, one of size A and the other of size B, preserving their relative ordering?

There are A+B total positions. If we put A elements from the left array in randomly chosen A positions (but in order) from total A+B positions, we can put the elements from the right array in leftover B positions. (Equivalently, we could also have chosen to fill B arbitrary positions from elements of the right array and fill the elements of the left array in whatever positions are left.). Thus ways to interleave the two permutations are nCr where n is the total number of positions, n = A+B, and r is the number of elements in the left array (left subtree), r = A.

This results in the following recurrence relation:

where,

left = elements in the left sub-sequence of subtree ‘nums’.

right = elements in the right sub-sequence of subtree ‘nums’.

A = length of the left array.

B = length of the right array.

A+B = size of the nums array.

Note: We need to use dynamic programming to precompute the values of nCr or C(n, r) (the number of ways to choose r elements from a set of n elements) using Pascal's Triangle algorithm. This will allow us to efficiently compute the number of ways to interleave the two subtrees in step 3. Pascal’s triangle can be precomputed in the ‘main’ function.

Pascal’s triangle uses the following recurrence: C(n, r) = C(n - 1, r - 1) + C(n - 1, r).

Dry Run

Let’s dry-run the algorithm for the array [3, 1, 5, 4, 2, 6], and observe the recursion tree.

Code

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
vector<vector<long long>> C;
// Computing pascal's triangle for finding nCr
void fillPascalTriangle(int size) {
C.resize(size + 1);
for (int i = 0; i <= size; ++i) {
C[i].resize(i + 1);
// Set value of nCr = 1, for r = 0 and r = n
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; ++j)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
}
int countPermutations(vector<int> &nums) {
int n = nums.size();
if (n <= 2)
return 1;
// find left sub-sequence elements and right sub-sequence elements
vector<int> left_subtree, right_subtree;
/*
The first element is the root of BST.
The elements smaller than the root form the left subtree of the root node.
The elements larger than the root form the right subtree of the root node.
*/
for (int i = 1; i < n; ++i) {
if (nums[i] < nums[0])
left_subtree.push_back(nums[i]);
else
right_subtree.push_back(nums[i]);
}
// recursion with left subtree and right subtree
long long left_res = countPermutations(left_subtree);
long long right_res = countPermutations(right_subtree);
int left = left_subtree.size(), right = right_subtree.size();
/*
Look up value from the table and multiply them together
C[left + right][left] = ways to interleave both subtrees keeping the relative ordering of elements the same
*/
int ans = (C[left + right][left] * left_res % MOD) * right_res % MOD;
return ans;
}
int main() {
vector<int> a = {2, 1, 4, 3};
int n = a.size();
// Fill Pascal's triangle
fillPascalTriangle(n);
// Count Permutations
cout << countPermutations(a) << endl;
}

Output:

3

Complexity Analysis

Time Complexity

The algorithm’s time complexity is O(n^2) in the worst case, where ‘n’ is the size of the given array. Pascal’s triangle can also be precomputed in O(n^2). Each recursive call takes O(n) time since we are iterating the entire array to push elements in the left and right subtree. Additionally, the function makes two recursive calls on the left and right subtrees, each of size at most n - 1, which makes the time complexity O(n^2) as the maximum depth of the recursion tree is n.

Space Complexity

The algorithm’s space complexity is O(n^2) because Pascal's triangle lookup table is used to compute the number of ways to interleave the left and right subtrees. Also, the recursive calls create subarrays for the left and right subtrees, which also use O(n) space, thus using O(n^2) space for the entire recursion tree.

Frequently Asked Questions

What is a Binary Search tree?

A binary search tree is a tree data structure where each node has at most two children, and the value of every node in the left subtree is less than the value of its parent node, while the value of every node in the right subtree is greater than the value of its parent node.

What is the Time and Space complexity to compute Pascal’s triangle?

Time complexity - O(n^2)

Space complexity - O(n^2)

where n is the size of the array since we are precomputing the entire table, and it has n*(n+1)/2 elements, which have to be computed and stored.

What is the recurrence relation in Pascal’s triangle?

The recurrence relation used to generate Pascal's triangle is as follows:

C(n, r) = C(n - 1, r - 1) + C(n - 1, r)

where C(n, r) is the value at the nth row and rth column of Pascal's triangle.

The base cases for the recurrence relation are

C(n, 0) = 1 for all n >= 0

C(n, n) = 1 for all n >= 0

How do you determine if two BSTs are equal?

Identical BSTs have the same structure, the same values for each node, and the same key-value pairs.

Why is it possible that two different arrays generate the same BST?

Different arrays can generate the same binary search tree because the structure of the tree is determined by order of insertion of the elements into the tree, rather than their values.

Thus, multiple ways exist to insert the same set of elements into the tree while maintaining the binary search tree property.

Conclusion

In this article, we solved the problem statement to Count permutations of the given array that generates the same Binary Search Tree (BST). Along with the solution, we also discussed the time and space complexity of the solution.

If you want to learn more about Binary search trees and want to practice some questions which require you to take your basic knowledge on these topics a notch higher, then you can visit our Guided Path for arrays on Coding Ninjas Studio. To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.