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

Dark Mode

53 votes

Best answer

Correct Option: 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.

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.

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

7

edited
Jan 15, 2019
by rawan

"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.

10

45 votes

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

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.☺

1

16 votes

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$

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$$

0

8 votes

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

= 2^{2 }h(n-2) -2 -1

=2^{3 } h(n-3) -2^{2} -2 -1

=2^{(h-1) }*2-(2^{(h-2) }+2^{(h-3) }...........-2-1)

=2^{h} - 2^{(h-1)}+1 =2^{(h-1)} +1

0