Results 1 to 7 of 7

Math Help - Question regarding algortihm

  1. #1
    Member
    Joined
    Oct 2008
    From
    Singapore
    Posts
    160

    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.
    Last edited by tester85; January 17th 2009 at 08:14 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jan 2009
    Posts
    3
    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...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2008
    From
    Singapore
    Posts
    160
    I am able to do a and b via induction. how about c. Any guidance on that ? Anyone ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2009
    Posts
    3
    Quote Originally Posted by tester85 View Post
    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)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2008
    From
    Singapore
    Posts
    160
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by tester85 View Post
    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

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

    See if you can "solve" this inequality for h.
    Last edited by awkward; January 17th 2009 at 06:08 AM. Reason: Can't type
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2008
    From
    Singapore
    Posts
    160
    I did it man . Haha. Thanks.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: January 2nd 2012, 07:58 PM

Search Tags


/mathhelpforum @mathhelpforum