The total number of binary trees possible with height n - 2 havi
The total number of binary trees possible with height n - 2 having n nodes are?
A. (2n - 5) 2<sup>n - 3</sup>
B. (2n - 7)2<sup>n - 3</sup>
C. (n - 3) 2<sup>n - 2</sup>
D. (2n - 7) 2<sup>n - 2</sup>
Please scroll down to see the correct answer and solution guide.
Right Answer is: A
SOLUTION
Solve this Problem using Recurrence relation. First find for height n - 1
P(n) = The number of trees with height ‘n - 1’ having n nodes.
we can see that
Height ‘n - 1’ can be obtained by ‘n - 1’ nodes with height ‘n - 2’ and one root
node,
P(n) = 2 × P(n – 1) + 1
Sub-tree can be either left or right, So Multiplied it by 2;
P(1) = 1;
Solving the Recurrence we will get 2n – 1;
Now to find tree with height n-2, we use recursive relation as
T(n) = 2T(n – 1) + 2n - 2
T(n) = (2n - 5) * 2n - 3
Hence option A is correct.