GATE CSE 1997 | Question: 16

Question

A size-balanced binary tree is a binary tree in which for every node the difference between the number of nodes in the left and right subtree is at most $1$. The distance of a node from the root is the length of the path from the root to the node. The height of a binary tree is the maximum distance of a leaf node from the root.

• A. Prove, by using induction on h, that a size-balance binary tree of height $h$ contains at least $2^h$ nodes.

• B. In a size-balanced binary tree of height $h \geqslant  1$, how many nodes are at distance $h-1$ from the root? Write only the answer without any explanations.

Comments

Please clear my doubt I think instead of atleast it should be at most ?

---

When we have h=3 then we have 7 nodes in AVL Tree. then how do we have at least 2^h nodes?

---

@iarnav But its not AVL tree it's size balanced tree...In AVL it depends on diff. height of Left subtree and right subtree..

@Deepesh Pai No it should be atleast only because max. no of nodes in a tree can be $(2^{h+1}-1)$

---

for 2 part of the question 

Answer 1

1. Prove, by using induction on $h$, that a size-balanced binary tree of height h contains at least $2^h$ nodes.
   When
   $h = 0$ ……… least no. of nodes $= 2 ^ 0 = 1$
   $h = 1$ ……… least no. of nodes $= 2 ^ 1 = 2$
   $h = 2$ ……… least no. of nodes $= 2 ^ 2 = 4$
   Assume that the rule is true for $h = k$
   Then the min no. of nodes $= 2 ^ k$ nodes
   If we increase the height by $1$ by adding a node, we must also add nodes to fill the (max level $-1$) level.
   This would mean doubling the nodes
   Thus $2^{k+1}$
   Hence, proved
    
2. In a size-balanced binary tree of height $h \geq 1$, how many nodes are at distance $h-1$ from the root? Write only the answer
   without any explanation
   $2^{h-1}$

Comments

@Abhrajyoti00

Your example is not correct, 

A size-balanced binary tree is a binary tree in which for every node the difference between the number of nodes in the left and right subtree is at most 1. 

 In your example , #nodes in the left-subtree of root is $4$ and

                             #nodes in right-subtree of root is $2$

which gives a difference of $2$ , thus incorrect tree(As per the question).

---

Thanks @Pranavpurkar Overlooked “number of nodes” and started playing with “height”

---

Thanks @Pranavpurkar

Answer 2

(a) recursive equation for nodes at height h,

N(h)= nodes in LST + 1 + nodes in RST

N(h)= N(h-1) + 1 + { N(h-1) - 1 }

N(h)= 2N(h-1) ; when h>=2

       by intution N(0)=1, N(1)=2 

by solving above equation by back substitution (termination condition, h-k=1) we will get 

                                                              N(h)= 2^h

(b)  for h<=1

at h=1,  N(1)=2

at h=0, N(0)= 1 

Answer 3

B.

1 is Ans if h=1

0 is Ans if h=0