The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+11 votes
684 views

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.

asked in DS by Veteran (59.5k points)
edited by | 684 views

3 Answers

+9 votes
Best answer
  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}$
answered by Boss (16.2k points)
edited by
0
But for b part it is h <= 1,
+4 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 

answered by Active (1.1k points)
edited by
+2 votes
B.

1 is Ans if h=1

0 is Ans if h=0
answered by Boss (22.8k points)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,751 questions
46,766 answers
140,658 comments
58,522 users