Redirected
reopened by
2,378 views
0 votes
0 votes

Consider a binary tree where for every node ⏐P – Q⏐ ≤ 2. represents number of nodes in left sub tree for node S and Q represents the number of nodes in right sub tree for node S for h > 0. The minimum number of nodes present in such binary tree of height h = 4 _________. (Assume root is at height 0)

reopened by

2 Answers

Best answer
5 votes
5 votes

9 is right answer.

selected by
21 votes
21 votes

the original image https://drive.google.com/open?id=1-Erqg7Y2xqXJL5YFyDZNh_GJ2Bxto7pT

But now i am interested to find it in general height.

we know that the no.of nodes of right side should be less than 2 at maximum only

===> for minimum no.of nodes, i consider  no.of right subtree nodes = no.of left subtree nodes - 2

===> Total nodes in that tree = no.of left subtree nodes + no.of right subtree nodes + 1 ( root node)

                                           = no.of left subtree nodes + ( no.of left subtree nodes - 2 ) + 1

                                           = no.of left subtree nodes + no.of left subtree nodes - 2  + 1

                                           = 2 * no.of left subtree nodes - 1

what is no.of nodes in left subtree ?

it should be equal to no.of nodes in h-1, where h is height of your tree

Total nodes in that tree = 2 * no.of left subtree nodes - 1

                         N(H) = 2 * ( N(H-1) ) - 1

for solving this recurrence relation, the base condition is N(H=3) = 5

using Back Substitution, we an solve it, the final value we can get

N(H) = 4 . 2(H-3) + 1 = 22 . 2(H-3) + 1 = 2(H-3)+2 + 1 = 2(H-1) + 1.

Related questions

1 votes
1 votes
1 answer
1
Nishisahu asked Dec 25, 2021
1,187 views
Suppose there are $11$ nodes in a binary tree. Find the number of unlabeled binary trees if the number of nodes either in the left sub tree or in the right sub tree is di...
2 votes
2 votes
3 answers
2
0 votes
0 votes
0 answers
4