StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Your question is equivalent to the question of counting the number of topological orderings for the given BST.</p> <p>For example, for the BST</p> <pre><code> 10 / \ 5 20 \7 | \ 15 30 </code></pre> <p>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):</p> <pre><code> 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 </code></pre> <p>The case (20, 30, 15) is analogous --- you can check that any one of the following inputs produces the same BST.</p> <p>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</p> <pre><code> l x r x INT(|L|, |R|) </code></pre> <p>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:</p> <pre><code> 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 </code></pre> <p>This solves the problem.</p> <p>Note: this solution assumes that all nodes in the BST have different keys.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload