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: Full Binary Tree question

  1. Mar 18, 2005 #1
    I need to prove that for any full binary tree with [tex]N\geq1[/tex] leaves, that it has [tex]2N-1[/tex] nodes. I can see this when looking at a tree, but I can't figure out how to prove this.
     
  2. jcsd
  3. Mar 18, 2005 #2
    I'll take a stab at it.

    I would try proving by induction on N by letting P(N) be the statement that for a full binary tree with [tex]N\geq1[/tex] leaves, it has [tex]2N-1[/tex] nodes.


    starting with the simplest case (a tree consisting of a single node) we'll prove P(1).
    in this case #leaves = #nodes = 1.
    hence P(1) = 2(1) - 1 and P(1) is a true statement.

    now lets assume that P(k) is true for some integer k, where k is greater than or equal to 1.
    If we can show that P(k) implies P(k+1) then were done with the proof.

    What we want to prove: P(k+1) = 2(k+1) - 1 = 2k + 1

    Proof: ( I'll use the notation FBT for "full binary tree" )

    a FBT with k+1 leaves has the same number of nodes of a FBT with k leaves + 2.
    ( notice that you can't add just one node to a FBT for it to remain full )

    therefore
    P(k+1) = P(k) + 2
    P(k+1) = (2k-1) + 2 <---- ( here we used the assumption that P(k) is true )
    P(k+1) = 2k + 1

    QED


    EDIT: I looked up the definitions of both full and complete binary trees online, and realize that they are a little different, however the same argument applies. I went ahead and edited out the word "complete" and changed it to "full".
     
    Last edited: Mar 18, 2005
  4. Mar 18, 2005 #3
    Thank you for the help.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook