edited by
4,908 views
22 votes
22 votes

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.

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

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

edited by

3 Answers

Best answer
24 votes
24 votes
  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}$
edited by
9 votes
9 votes

(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)= 2h

(b)  for h<=1

at h=1,  N(1)=2

at h=0, N(0)= 1 

edited by

Related questions