Algorithms

Question 48

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number of nodes in the tree is:

A	2^h-1
B	2^h-1 + 1
C	2^h – 1
D	2^h

AlgorithmsTree TraversalsGATE 2005-IT

Question 48 Explanation:

Let’s take an example,

Above tree satisfies the property given in the question. Hence, only option (B) satisfies it.

Correct Answer: B

Question 48 Explanation:

Let’s take an example,

Above tree satisfies the property given in the question. Hence, only option (B) satisfies it.