3.9k views

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

1. $2^{h-1}$
2. $2^{h-1} + 1$
3. $2^h - 1$
4. $2^h$
in DS
edited | 3.9k views
+3

You can check same question  https://gateoverflow.in/239308/made-easy

It should be B)

Since the difference between the nodes in left and right subtree must hold for every node, until the  last to last to last level, all levels must be fully filled. So, we get $2^{h−1}−1$ nodes (No. of nodes in a complete binary tree of height $h−2$). Now, our aim is to increase two more levels by adding minimum no. of nodes- just add two in nodes one below other to any of the nodes. So, we get $2^{h−1}+1$ nodes - B option.

by Active (1k points)
edited
+13

All levels till h-1th level will be fully filled giving 2h-1-1 nodes and 1 node each at level h and h+1, giving 2h-1+1 nodes.

+1
more details plzzz
+1
All Level till h-1 th level will be full giving 2^(h-1)-1 nodes. Now inorder to have minimum number of nodes with height H should be 1 more than the nodes at height at h-1? so Ans would be 2^(h-1).

E.g For tree of height 3. Till height 2 the tree will be completly filled giving 3 nodes. In height 3 , if we add one more node. We get a tree with height  having min num(i.e. 4) of nodes right?

Please correct me if im wrong.
+6
Let there be n(h) nodes at height h.

In a perfect tree where every node has exactly
two children, except leaves, following recurrence holds.

n(h) = 2*n(h-1) + 1

In given case, the numbers of nodes are two less, therefore
n(h) = 2*n(h-1) + 1 - 2
= 2*n(h-1) - 1

Now if try all options, only option (b) satisfies above recurrence.

Let us see option (B)
n(h) = 2
h - 1 + 1 So if we substitute n(h-1) = 2h-2 + 1, we should get n(h) = 2h-1 + 1 n(h) = 2*n(h-1) - 1 = 2*(2h-2 + 1) -1 = 2h-1 + 1.
+3

"Since the difference between the nodes in left and right subtree must hold for every node, until the  last to last to last level, all levels must be fully filled."

That is not necessarily true. Here's a tree which does not satisfy your constraint, but satisfies the constraint of the question:

The last-to-last-to-last (3rd last) level here, $3 - 5 - 8$, is not full, but the number of nodes in the left and right subtrees of any node is at most 2.

Your answer is still correct, though. We cannot have a tree of height $h$ with less than $2^{h-1} + 1$ nodes.

This question is begging to be solved by a recurrence equation (divide and conquer).

Let's say we have a tree of height $h$ that has the minimum no. of nodes [let's denote the no. of nodes by $n(h)$] that satisfies the constraint given in the problem (that for every node, the difference between.... you get the point. Let's call it OC, short for Original Constraint). Now, if we want to increase the height of this tree by 1, we can do so by attaching a new leaf, but we won't know which leaf to join to, so we add a new root instead and join, to the left of this root, our tree of height $h$. Now, for this new tree with height $h + 1$ to satisfy the OC, we must add as many no. of nodes to the right child of our new root, as are required to maintain our OC property. We can do this with the minimum no. of nodes by adding 2 less than $n(h)$ no. of nodes. So, increasing the height of our tree by one entails adding a new root ($1$) and a right subtree to this root with $n(h) - 2$ nodes.

So our recurrence equation is:

$n(h+1) = n(h) + [1] + [n(h) - 2] = 2n(h) - 1$

in other words,

$n(h) = 2n(h-1) - 1$

Base case: $n(1) = 2$

Find the first few values for $h$ = 2, 3, ..., you'll get the answer.

0

"Since the difference between the nodes in left and right subtree must hold for every node, until the  last to last to last level, all levels must be fully filled."

This line of yours is wrong.

Option Elimination

Take a tree which satisfies given constraint

and eliminate the incorrect options

h=1 n=2

Option A & C eliminated

Option B,D still satisfying

In below img h=2 n=3

Here option D eliminated

So option B is Ans

by Boss (23.8k points)
edited
0
but all conditions are fail if tree has 3 nodes and root has 2 children .by this height=1

but all otions are eliminated
0
@set2018 Yes, a better approach is what Arjun sir has mentioned in selected answer comment.
0

@set2018 Though option elimination method is not recommended, it certainly works for this question. You said that,

but all conditions are fail if tree has 3 nodes and root has 2 children .by this height=1

The example you have taken is wrong. The question is asking about minimum no. of nodes in the tree in terms of height. Clearly, for h=1, tree having 3 nodes with root having 2 children is a maximum condition. The minimum case will be tree having 2 nodes with root having 1 child. Then option elimination works.☺

condition given = difference between the number of nodes in the left and right subtrees is at most 2.
soln --->>
suppose n(h) represents minimum no of nodes in binary tree of height h
by following the given condition
n(0) = 1
n(1)= 2
n(2)= 3
n(3)= 5
n(4)=9
n(5)=17
n(h)=??
--->> by seeing the above pattern a layman can easily guess that n(h)=2n(h-1) -1 {a recurence relation with base condition n(1)=2 for this}
an alternate method to find recurence relation
suppose we have a binary tree with nodes n(h-1) for height h-1 so to build next binary tree of height h we will use tree of height h-1
so that the resultant tree of height h also gives minimum no of nodes
now procedure is starting take a node and make tree of height h-1 {previousely n(h-1)} as left or right sub tree of this root node suppose we are taking this as right sub tree so now this tree is not satisfies our given condition  "difference between the number of nodes in the left and right subtrees is at most 2."
so to we need to add such require no of nodes in left sub tree of root node and this number is determined by the n(h-1) and this number will surely be n(h-1)-2
so RR= n(h)=n(h-1) //for rst +1 //for root + n(h-1)-2 //for lst =2n(h-1)-1  {for h>1}
=n(1)=2 {for h=1 it is base condition}
----->>> now our job is to solve recurence relation
rr = 2n(h-1)-1
= 2h(n-2) -2 -1
=2 h(n-3) -22 -2 -1
=2(h-1) *2-(2(h-2) +2(h-3) ...........-2-1)
=2h - 2(h-1)+1 =2(h-1) +1

by Boss (12.3k points)
edited
0
why is N(4) = 9 ?

N(4) can be made by 7 nodes as
1 root
4 in left sub tree as skewed in left making the height = 4 and
2 in right sub tree
0

@rakeshgsharma how N(4)= 7...???

0
Sorry I was wrong. The above explanations are correct. Please follow them. Thank-you.

For a given node $a$, let the number of nodes in its left sub-tree be $l$ and that on the right sub-tree be $r$. Based on the given constraint $\mid l - r \mid \leq 2.$ For simplicity we can assume $l \geq r$ as this should be similar to assuming $r \geq l$ and won't change the answer. This gives $r \geq l - 2.$

Now, minimum number of nodes in the sub-tree rooted at $a = l + r + 1$

$\qquad = l + l - 2 + 1$

$\qquad = 2l - 1\qquad \to (1).$

Now, lets assume the height of the sub-tree rooted at $a$ to be $h$ and this gives the height of its left (or right) sub-tree $= h - 1.$

If we denote the minimum number of nodes in a binary tree of height $h$ satisfying the given conditions by $N(h),$ we get

$N(h) = 2 N(h-1) - 1$

We know $N(1) = 2.$

So, from $N(h) = 2N(h-1)-1$ we get

$N(2) = 2 . 2 -1 = 3, N(3) = 5, N(4) = 9, N(5) = 17.$

We can see that $N(h) = 2^{h-1} +1.$

(Formal proof given below)

$N(h) = 2N(h-1)-1 = 2 \left[2 N(h-2) -1 \right] - 1$

$\qquad = 2^2 \left[N(h-2) \right] - 2 -1$

$\qquad = 2^2 \left[2N(h-3) - 1 \right] - 2^1 -1$

$\qquad = 2^3 \left[N(h-3) \right] -2^2- 2 -1$

$\qquad \vdots$

$\qquad = 2^{h-1} \left[N(1) \right] - \left[2^{h-2} +\ldots +2^2+ 2^1 +2^0 \right]$

$\qquad = 2^{h-1} \left[2 \right] - \left[2^{h-1} - 1\right]$

$\qquad = 2^{h-1}+1$

by Veteran (425k points)
0

Sir, I also thought like this below and found the same recurrence relation. As the difference between the left and right sub-tree is at most $2$ for each node, if $T(h-1)$ represents nodes of the left sub tree, right sub-tree will have $\{T(h-1)-2\}$ nodes. Besides we have add $1$ for the current node at height $h$. So we can write it as the recurrence relation like below.

$$T(h)=T(h-1)+\{T(h-1)-2\}+1=2T(h-1)-1$$

Just mentioning another approach to solve this problem.

If anything is not proper then please notify. I hope this helps.

by Boss (13.3k points)
edited by
+1
Yes, this is right. But the recurrence becomes very tedious. But, mathematically, this is right. Logically, other answers are better.

Also, we have to take base as H(2) = 1, I tried with H(1) = 0, but it failed

Wrong options

by (13 points)
reshown
0
????
+1
The question clearly mentions that the difference between the number of nodes b/w left and right subtrees is atmost 2, in your case if we consider the root node , it comes as 5-2 =3 >2 , hence the example is wrong