1. ## Solved : Question regarding algortihm

Prove the following lemmas :

a) There are at most 2^d nodes at depth d of a binary tree.
b) A binary tree with height h has at most 2^(h+1)-1 nodes
c) A binary tree with n nodes has height at least ceiling(lg(n+1))-1

Can someone get me started with this questions.

2. I would say the easiest way is to do it by induction on the depth of a tree.
You can prove a) and use this to derive b) easily.
I dont want to spoil you the whole work, but if that does not help you, let us know...

3. I am able to do a and b via induction. how about c. Any guidance on that ? Anyone ?

4. Originally Posted by tester85
I am able to do a and b via induction. how about c. Any guidance on that ? Anyone ?
You dont need induction for b): Let T be a binary tree with height h, then the total number of nodes equals the sum of nodes at depth i, i=0,...h and now you just have to use a) on each summand. For c) you can adapt the inequality derived in b)

5. Hmmm this assignment i did it last week but i remember that i was not able to do part c. But able to do a and b. I will check again and update this thread.

6. Originally Posted by tester85
Prove the following lemmas :

a) There are at most 2^d nodes at depth d of a binary tree.
b) A binary tree with height h has at most 2^(h+1)-1 nodes
c) A binary tree with n nodes has height at least ceiling(lg(n+1))-1

Can someone get me started with this questions.
Hi tester85,

If you have done a) and b), here is a hint on c. By b), we know

$\displaystyle n \leq 2^{h+1} -1$.

See if you can "solve" this inequality for h.

7. I did it man . Haha. Thanks.