1. Not finding help here? Sign up for a free 30min 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!

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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?