Proving the Number of Nodes in a Full Binary Tree

[NuPowerbook]

I need to prove that for any full binary tree with N\geq1 leaves, that it has 2N-1 nodes. I can see this when looking at a tree, but I can't figure out how to prove this.

 

[MathStudent]

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 N\geq1 leaves, it has 2N-1 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 let's 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".

 

[NuPowerbook]

Thank you for the help.