Find number of permutations of a given sequence of integers which yield the same binary search tree

Question

Given an array of integers arr = [5, 6, 1]. When we construct a BST with this input in the same order, we will have "5" as root, "6" as the right child and "1" as left child.

Now if our input is changed to [5,1,6], our BST structure will still be identical.

So given an array of integers, how to find the number of different permutations of the input array that results in the identical BST as the BST formed on the original array order?

Apparently

Answer 1

Your question is equivalent to the question of counting the number of topological orderings for the given BST.

For example, for the BST

  10
 /  \
5   20
 \7 | \
    15 30

the set of topological orderings can be counted by hand like this: 10 starts every ordering. The number of topological orderings for the subtree starting with 20 is two: (20, 15, 30) and (20, 30, 15). The subtree starting with 5 has only one ordering: (5, 7). These two sequence can be interleaved in an arbitrary manner, leading to 2 x 10 interleavings, thus producing twenty inputs which produce the same BST. The first 10 are enumerated below for the case (20, 15, 30):

 10 5 7 20 15 30
 10 5 20 7 15 30
 10 5 20 15 7 30
 10 5 20 15 30 7
 10 20 5 7 15 30
 10 20 5 15 7 30
 10 20 5 15 30 7
 10 20 15 5 7 30
 10 20 15 5 30 7
 10 20 15 30 5 7

The case (20, 30, 15) is analogous --- you can check that any one of the following inputs produces the same BST.

This examples also provides a recursive rule to calculate the number of the orderings. For a leaf, the number is 1. For a non-leaf node with one child, the number equals to the number of topological orderings for the child. For a non-leaf node with two children with subtree sizes |L| and |R|, both having l and r orderings, resp., the number equals to

  l x r x INT(|L|, |R|)

Where INT is the number of possible interleavings of |L| and |R| elements. This can be calculated easily by (|L| + |R|)! / (|L|! x |R|!). For the example above, we get the following recursive computation:

  Ord(15) = 1
  Ord(30) = 1
  Ord(20) = 1 x 1 x INT(1, 1) = 2  ; INT(1, 1) = 2! / 1 = 2
  Ord(7) = 1
  Ord(5) = 1
  Ord(10) = 1 x 2 x INT(2, 3) = 2 x 5! / (2! x 3!) = 2 x 120 / 12 = 2 x 10 = 20

This solves the problem.

Note: this solution assumes that all nodes in the BST have different keys.

Psychogenic

from where did u get this relations (lrINT(|L|,|R|) and why INT(a,b)=(a+b)! / (a! * b!) – Alcaraz

l x r x INT(|L|, |R|) comes from (1) "l" different ways to order the sequence that produces the left subtree, (2), "r" different ways to order the sequence that produces the right subtree, and (3) INT(|L|, |R|) different ways to mix those two sequences, i.e. interleave them. INT(a,b) = (a+b)!/(a! b!) because among all interleavings of a+b elements, we are interested only in those where the sequence of elements a has a fixed ordering, ditto for sequence of elements b, hence divide by a! and b! separately. – Psychogenic

Answer 2

Thanks for the explanation antti.huima! This helped me understand. Here is some C++:

#include <vector>
#include <iostream>

using namespace std;

int factorial(int x) {
  return (x <= 1) ? 1 : x * factorial(x - 1);
}

int f(int a, int b) {
  return factorial(a + b) / (factorial(a) * factorial(b));
}

template <typename T>
int n(vector<T>& P) {
  if (P.size() <= 1) return 1;
  vector<T> L, R;
  for (int i = 1; i < P.size(); i++) {
    if (P[i] < P[0])
      L.push_back(P[i]);
    else
      R.push_back(P[i]);
  }
  return n(L) * n(R) * f(L.size(), R.size());
}

int main(int argc, char *argv[]) {
  vector<int> a = { 10, 5, 7, 20, 15, 30 };
  cout << n(a) << endl;
  return 0;
}

Tootsie

factorial might have over-flow problem – Radiochemical

Answer 3

This question can be solved easily if you have little knowledge of recursion, permutation and combinations, and familiarity with Binary Search Tree(obviously).

First you build a binary search tree with the given sequence. You can also perform the same operation in the array but tree-visualisation would paint a good picture.

For given sequence arr[1..n], 1st element would stay put as it is in the given array and only arrangement needs to be brought in arr[2..n].

Assume:

bag1 = number of elements in arr[2..n] which are less than arr[0].

and,

bag2 = number of elements in arr[2..n] which are greater than arr[0].

Since the permutation of elements in bag1 in the sequence won't pose a conflict with the numbers present in the bag2 while forming a binary search tree, one can start begin calculating the answer by picking bag1 elements out of (n-1) elements to permutate and then rest ((n-1) - bag1) = bag2 elements can be placed in 1 way only now. Ordering of elements in bag1 should should be same and likewise for bag2 elements in the sequence.

Since each subtree of a binary search tree has to be a BST. Similar process would be operated on each node and multiply the local answer for the node to final answer.

int ans = 1;
int size[1000000] = {0};

// calculate the size of tree and its subtrees before running function "fun" given below.
int calSize(struct node* root){
     if(root == NULL)
          return 0;

     int l = calSize(root->left);
     int r = calSize(root -> right);
     size[root->val] = l+r+1;
     return size[root->val]; 
}

void fun(struct node* root){
     if(root == NULL)
         return;

     int n = size[root->val];
     if(root->left){
         ans *= nCr(n-1, size[root->left]);
         ans *= 1; // (Just to understand that there is now only 1 way 
                   //to distribute the rest (n-1)-size of root->left)
     }

     fun(root->left);
     fun(root->right); 
}

int main(){
     struct node* root;

     //construct tree
     //and send the root to function "fun"

     fun(root);

     cout<<ans<<endl;
     return 0;
}

Greatest

Answer 4

You could do this backwards: Given a BST, enumerate all the arrays of integers which could yield this BST...

Couldn't you (using nondeterminism...)

1. emit root and add it to the emitted set.
2. nondeterministically choose an item from the tree which is not in the emitted set, but whose parent is, and add it to the emitted set and emit it.
3. repeat 2 until all emitted.

The nondeterminism will give you all such arrays. Then you can count them.

Zephyrus

Why is nondeterminism necessary? – Liechtenstein

It's not, really. I was thinking about nondeterminism a lot in 2009. It fits this problem well though - trying one thing, output the result, then roll back to a earlier state (where state is (set of visited nodes, path so far) ). – Zephyrus