Count Permutations of the given Array that Generates the Same Binary Search Tree (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

1. The first element on the input array is BST’s root.
2. 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.
3. 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;
}

You can also try this code with Online C++ Compiler

Run Code

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

1. C(n, 0) = 1 for all n >= 0
2. 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.

Recommended Reading:

• Median of Nodes From a Given Range in BST
• Remove BST Nodes Having a Value in Given Range
• Kth Smallest Element in a Perfect Binary Search Tree
• Kth Smallest Element in BST
• Print All Odd Nodes of the Binary Search Tree
• Count BST Nodes that Lie in a Given Range
• Count Pairs Violating the BST Property
• Flattening BST in a Sorted List

Recommended Problems -

• Rearrange Array Alternately
• Sum Of Two Arrays
• Merge K Sorted Arrays

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.

By Akshat