Made Easy test series DS

Question

Consider a binary tree where for every node ⏐P – Q⏐ ≤ 2. P 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)

Comments

It is nothing but minimum number of nodes in a AVL tree

 $T(n)=T(n-1)+T(n-2)+1 , T(0)=1,T(1)=2$

$T(2)=T(1)+T(0)+1=2+1+1=4$

$T(3)=T(2)+T(1)+1=4+2+1=7$

$T(4)=T(3)+T(2)+1=7+4+1=12$ is the answer

---

in AVL tree max difference left subtree and right subtree can be -1,0,+1...logic of AVL is there but not AVL

---

HINT: Read question One more time, It is saying P-Q<=2  where P and Q are no. of nodes in the left and Right Subtree and Not height of left and right subtree!

---

Similar question: https://gateoverflow.in/3811/gate2005-it-50

https://gateoverflow.in/117248/balanced-tree-minimum-no-of-nodes-for-height-h

Answer 1

9 is right answer.

Comments

I thiink its 8 no need of 1 node in 1st level of left subtree of right node of degree 2

---

@abhishekmehta4u @Arjun @srestha Can someone please tell me why one extra node in right sub tree and what should be correct answer ? 9 or 8? I am getting 8 

---

it is not satisfying the condition for 1 and 0 , hence i think 9 may be correct

Answer 2

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 = 2² . 2^(H-3) + 1 = 2^(H-3)+2 + 1 = 2^(H-1) + 1.

Comments

@tusharp-Why are you taking base condition only $A(3)=5$. $A(0)=1$ is also valid because for height 0, minimum 1 node is required.

---

However $A(1)=2$ also gives the correct constant value for A.But why not $A(0)=1$?

---

First I was confused that empty tree has height $0$ by looking at the best answer from this question on stackoverflow: https://stackoverflow.com/questions/2209777/what-is-the-definition-for-the-height-of-a-tree/2209840#2209840

Later from comments I understood that height of an empty tree is either undefined or $-1$ but definitely not $0$.

The height of an empty tree is not defined.

Source: https://xlinux.nist.gov/dads/HTML/height.html

Conventionally, an empty tree (tree with no nodes, if such are allowed) has height $−1$.

Source: https://en.wikipedia.org/wiki/Tree_(data_structure)