1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Binary trees

  1. Aug 19, 2009 #1
    2 questions that came up in a past paper.

    A binary tree which is both full and complete and has h levels contains a total of 2^(h-1)
    leaf nodes. Prove that this is the case for all h > 0.

    Show that with h levels the number of internal nodes is 2^(h−1) − 1

    proof by induction apparantly

    anyone can help? I don't really need to understand it if it came up in an exam just to know it off by heart.

    Sorry if I've posted in the wrong section.

  2. jcsd
  3. Aug 24, 2009 #2


    Staff: Mentor

    Proof by induction is the way to go. A tree with 2 levels has 2 leaf nodes (= 22 - 1 nodes). A tree with 3 levels has 4 leaf nodes (= 23 - 1).

    Assume that a tree with k levels has 2k - 1 leaf nodes, and then use this to show that a tree with k + 1 levels has 2k leaf nodes.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook