1k 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.

in DS
edited | 1k views
0
Please clear my doubt I think instead of atleast it should be at most ?
0
When we have h=3 then we have 7 nodes in AVL Tree. then how do we have at least 2^h nodes?

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}$
by Boss (17.3k points)
edited by
0
But for b part it is h <= 1,

(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

by Active (1.3k points)
edited
B.

1 is Ans if h=1

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

+1 vote
1
2