permutations of BST

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], still our BST structure will 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?

Answer 1

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.

Answer 2

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.