Specific height
The first seven positive integers (1 to 7) are to be inserted into an empty binary search tree . In how many ways can they be inserted into the tree, such that the resulting tree has a height 6?
Details and Assumotions
- The height of a tree is the number of edges on the longest downward path between the root and a leaf.
The answer is 64.
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
Also see: When trees are tall
A tall tree is a binary tree of n nodes of height n-1.
Let us consider the generalized problem of a tall binary tree with n nodes.
To make the tree as tall as possible, we require that it has no "branches", i.e, there are no nodes which have both left and right children. This means that we have two choices, to make the entire subtree towards the right, in which case the root element is the minimum, or towards the left, in which case the root element is the maximum.
After we have made that choice, all we need to do is build a rebuild a tall tree with n − 1 nodes and root it according to the choice we made.
So, T r e e s ( n ) = 2 T r e e s ( n − 1 )
It is clear that with a single node there is only a single such tree. Hence, T r e e s ( 1 ) = 1
That gives us the general formula T r e e s ( n ) = 2 n − 1 . Plugging in 7 gives 6 4 .