Count permutations of the given array that generates the same Binary Search Tree (BST)

Apoorv
Last Updated: May 13, 2022

Problem statement

Given an array “perm[]” of size ‘N’ which stores the elements in the range from 1 to N, the order of the elements in the array tells the order in which nodes are inserted into the Binary search tree, The final task is to count permutations or to tell the total number of ways in which the array can be rearranged to give the same binary search tree

 

Example

Input perm = {3, 4, 5, 1, 2};

The following arrays will yield the same BST which will make count permutations to 5: 

[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]

 

Explanation:

First to insert is 3. The tree is just a single node 3

Then we insert 4. Has to go on the right of 3. The tree is

 

       3

         \

          4

 

Then we insert 1. (Again note that we have to insert in the same order as the input array. I'll repeat this several times :D)

 

       3

       / \

      1  4

 

Then 5

          3

          / \

        1   4

               \

                 5

 

Then 2

            3

            / \

          1   4

           \     \

           2     5

Try similarly with other listed arrays and you will see that all those combinations will lead to same BST

 

So, for this BST,

choose 3 as root (the element which is first in insertion order)

[1, 2] will be in the left subtree. Maintaining order is important to ensure that we generate the same BST. Let m = left.size()

[4,5] in right subtree. Let n = right.size()

find ways to interleave them.The number of ways is just interleavings of left and right. 

How many ways are there to interleave left and right?

There are m + n total positions. If we put m elements from left in randomly chosen m positions (but, in order), we can put the rest in other (right ;-)) positions. (Equivalently, we could also have chosen to fill n arbitrary positions from right and fill remaining from whatever positions are left.)

 

Approach

The concept is to fix the root node first, then count permutations or the number of ways to rearrange the elements of the left subtree and the elements of the right subtree in such a way that the relative order within the left and right subtrees is the same.So the no of ways in which root node can be fixed is total combinations with respect to the number of nodes in left that is nCr where n is the total number of nodes and r is the number of nodes which are in left or we can also use nC(n-r) here (n-r) is the number of nodes in right.After fixing the root node for every combination there can be a count for subtree which we can calculate using recursion for left and right subtree respectively. So the total permutations will be product of total combinations , count for left subtree and count for right subtree for a given combination.

Recurrence relation

countPerm(perm) = countPerm(left) * countPerm(right) * combinations(size, L)

Where ‘L’ is the no of elements in left subtree and ‘size’ is the total size of the array  .

Algorithm

  • Make a dummy array to precompute the factorial of all the values from 1 to N
  • Make a combination function which will calculate the value of nCr that is (n!) / (n - r)! * r!
  • Fix the BST root node, and separate the elements on the basis of root node by pushing elements having value less that root node in leftsubtreearray and pushing other elements in right subtreearray 
  • Maintain the relative order amongst the elements of the left and right subtrees to construct identical BST.
  • Using the above-mentioned recurrence relation, calculate the number of ways to rearrange the array to generate BST.

Code:

#include <bits/stdc++.h>
using namespace std;
 
// Pre Computing the factorial
void factorial(int dummy[], int size)
{
    dummy[0] = 1;
    for (long long int i = 1; i < size; i++) {
        dummy[i] = dummy[i - 1] * i;
    }
}
 
 
// Function to tell total possible ways to fix root that is ncr ways
int combinations(int dummy[], int size, int temp)
{
    if (temp > size)
        return 0;
 
    // nCr= factorial(n)/(factorial(r)*factorial(n-r))
    int ans = dummy[size] / dummy[temp];
    ans /= dummy[size - temp];
 
    return ans;
}
 
// Count permutations that generates same BST
int countPerm(vector<int>& perm, int dummy[])
{

    // Store the size of the array
    int N = perm.size();
 
    // Base case
    if (N <= 2) {
        return 1;
    }
 
    vector<int> leftSubTree,rightSubTree;
 
    // Store the root node
    int root = perm[0];
 
    for (int i = 1; i < N; i++) {

        // Pushing elements in left and right subtree accordingly
        perm[i] < root?leftSubTree.push_back(perm[i]):rightSubTree.push_back(perm[i]);
    }
 
    // Store the size of leftSubTree and right subtree
    int N1 = leftSubTree.size();
    int N2 = rightSubTree.size();
 
    // Recurring on left and right subtree to calculate answers from left and right subtrees
    return combinations(dummy, N - 1, N1)*countPerm(leftSubTree,dummy)*countPerm(rightSubTree,dummy);

}
 
int main()
{
 
    // Input array and size
    vector<int> arr = { 3, 4, 5, 1, 2};
    int size = 5;
 
    // Dummy array to store factorial
    int dummy[size];

    // Filling dummy array with factorial upto size
    factorial(dummy, size);
   
    // Count permutations
    cout << countPerm(arr, dummy);
 
    return 0;
}

Output:

6

 

Time Complexity 

O(N^2)
The time complexity to Count permutations of the given array that generates the same Binary Search Tree (BST) will be O(N ^ 2) where ‘N’ is the size of the given array since we are using the recursive call to solve the problem which will cost O(N) time complexity but in every recursive call we are iterating in entire array to push the element in left and right subtree which will again cost O(N) time so the overall time complexity will be O(N * N).

Space Complexity 

O(N)

The Space complexity to Count permutations of the given array that generates the same Binary Search Tree (BST) will be O(N) where ‘N’ is the size of the given array since we are making a dummy array to precompute the value of factorial for all the values from 1 to N.

Frequently Asked Questions

 

1.Time complexity and space complexity to calculate factorial?

Time complexity - O(N)

Space complexity - O(N)

 Where N is the size of the array since we are linearly iterating in a dummy array to precompute the value of factorial 

2.What is a Binary search tree?

A genric tree with at most two child nodes for every node, the left subtree has a value less than the root node, and the right subtree has a value greater than the root node. 

 

3.How is the combination calculated for the root node in recurrence relation?

So the no of ways in which root node can be fixed is total combinations with respect to the number of nodes in left that is nCr where n is the total number of nodes and r is the number of nodes which are in left or we can also use nC(n-r) here (n-r) is the number of nodes in right so we can use any of these two combination’s formula for our recurrence relation. 

 

Key Takeaways

 

In this blog, 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  CodeStudio.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 Apoorv

 

Was this article helpful ?
1 upvote