707 views

2 Answers

4 votes
4 votes

Well the answer is clearly 144 

The well defined formula for n distinct elements with height n-2 is

$T(n)=2^{n-2}\cdot (n-3) + 2^{n-3}$

Here is the derivation,

First, simply take n-1 nodes and count the number of ways in arranging them so that the height of the BST remains n-2(assuming root at height 0) which is $2^{(n-1)-1} = 2^{n-2}$

Secondly, simply add a node in every non-leaf of our above trees which means in each of our above patterns we can make (n-2) more trees so the formula becomes 

$2^{n-2}\cdot (n-2)$

(n-2) are the number of non-leaf nodes in each of our patterns because only 1 last node will be the leaf

This could be the final equation but sadly there is a problem with this formula

If we add a node to our last non-leaf which is the node above the leaf node would result in two similar pattern of our two tree pattern so instead of adding the node to all the non leaf we instead add it to nodes leaving the last non leaf node so the formula becomes

$2^{n-2}\cdot (n-3)$

and for the remaining $2^{n-2}$ patterns we divide it with 2 to prevent them from counting twice which is $2^{n-2}/2 = 2^{n-3}$

So our total formula becomes

$2^{n-2}\cdot (n-3) + 2^{n-3}$

$2^{7-2}\cdot(7-3) + 2^{7-3}$

$32\cdot4 + 16$

$144$

edited by
2 votes
2 votes

Total node : $1, 2, 3, 4, 5, 6, 7$

height of tree = $5$

so, the root can be either $1, 2, 6, 7$ and only one node has 2 children and the rest node has only one child

Consider Root is 1 (Same for node 7)

  

Total = $1 + 2 + 4 + 8 = 15$ 

Consider root is 2 (Same for node 6)


So total tree = $15 * 2  +  16 * 2 $

                       = $62$


 

edited by