Root out the roots III
How many ways are there to construct a binary search tree from these vertices by inserting them one by one?
Two constructions are considered different if the order in which any two nodes were inserted differ. Clarifications:
- No node can be selected more than once.
- Each BST must contain all of the ten nodes.
- You can randomly select any of the nodes one by one to form a BST.
The problem is a part of this set
The answer is 3628800.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Every unique permutation of n unique node values gives a unique way of building a B S T . For example, having the following nodes 2 , 3 , 5 ; there can be 3 ! = 6 ways to build a B S T since there are following 6 permutations of those numbers; {2,3,5}, {2,5,3}, {3,2,5}, {3,5,2}, {5,2,3}, and {5,3,2}. Each of the permutations give us a unique way to build the B S T . Similarly, there are 1 0 ! unique ways to build a B S T from 1 0 unique numbers.