StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The number of permutations of nodes you have to check is 11! = 39,916,800, so you could just write a program to brute-force this. Here's a skeleton of one, written in C++:</p> <pre><code>vector<int> values = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}; unsigned numSuccesses = 0; do { if (bstHeightOf(values) == 3) values++; } while (next_permutation(values.begin(), values.end()); </code></pre> <p>Here, you just need to write the <code>bstHeightOf</code> function, which computes the height of a BST formed by inserting the given nodes in the specified order. I'll leave this as an exercise.</p> <p>You can prune down the search space a bunch by using these observations:</p> <ol> <li>The maximum number of nodes in a BST of height 2 is 7.</li> <li>The root can't be 1, 2, 3, 9, 10, or 11, because if it were, one subtree would have more than 7 nodes in it and therefore the overall tree would have height greater than three.</li> </ol> <p>Given that you know the possible roots, one option would be to generate all BSTs with the keys {1, 2, 3, ..., 11} (not by listing off all orderings, but by listing off all trees), filter it down just to the set of nodes with height 3, and then use <a href="https://stackoverflow.com/questions/17119116/how-many-ways-can-you-insert-a-series-of-values-into-a-bst-to-form-a-specific-tr">this recursive algorithm</a> to count the number of ways each tree can be built by inserting values. This would probably be significantly faster than the above approach, since the number of trees to check is much lower than the number of orderings and each tree can be checked in linear time.</p> <p>Hope this helps!</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