Binary tree problem

[Erza]

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?

[Blubbartron]

I'm not sure what level of familiarity you have with proofs by induction, so I'll give a simple guide for now instead of doing the whole thing. First step is to prove the base case (h = 1). This is trivial by the definition of full and complete. If h = 1, there's only 1 node. 2^(1 -1) = 1. Therefore base case works. Then you assume the inductive hypothesis (that what you're trying to prove is true for some k > 0) and use it to prove that k + 1 is true. It should only take some small algebraic manipulation and a bit of definition use to get there.

[Erza]

thanks,

Figuring out aside if the question was to come up it'd come up exactly like them, so it'd merely be a case of learning it off.

[SDSD]

thanks,

Figuring out aside if the question was to come up it'd come up exactly like them, so it'd merely be a case of learning it off.

http://www.math.ucsd.edu/~jverstra/154-part1.pdf

Use the proof on page 10 for the number of edges in a binary tree to construct your proof. It follows the same logic.

[Erza]

I don't really get it to be honest.

[SDSD]

Proof that a full binary tree of height h has 2^h external nodes.

Consider a full binary tree of height 0. It is clearly just the root node, which is an external node. 2^0 = 1, so for h = 0, the number of external nodes, 1, is 2^h. So we have established our base case.

Now assume that h = n-1 for some value of n > 1. Our inductive hypothesis is that the number of external nodes in a full binary tree of height n-1 is 2^(n-1). Consider a full binary tree of height n. We can obtain this tree from a full binary tree of height n-1 by adding 2 children to each of the smaller tree's nodes. But then the number of external nodes would be 2*2^(n-1), by the inductive hypothesis, since there were 2^(n-1) nodes at level n-1, and each of those nodes has 2 children. But 2*2^(n-1) = 2^n, and so for any full binary tree of arbitrary height n, the tree has 2^n external nodes.

Edit: http://www.docstoc.com/docs/3423323/...f-by-Induction
Page 5 for the proof to your second question.

[Erza]

thanks for your help there mate, the question didnt come up lol.

[Jodwahh]

I was totally set to make an ascii tree out of ones and zero's but I can't be bothered so you're all going to just have to imagine and then say well played sir.

[Zanmato]

Even though you've said the question didn't come up, I'll still solve it for those who would like to see the solution.

Proof by induction:

Let the total number of leaf nodes be f(h) = 2^(h-1).

Amount of tree nodes f(h) cant be < 1, therefore h has to be > 0.

Consider base cases:

h = 1; f(1) = 2^(1-1) = 1
h = 2; f(2) = 2^(2-1) = 2
h = 3; f(3) = 2^(3-1) = 4
h = 4; f(4) = 2^(4-1) = 8
h = 5; f(5) = 2^(5-1) = 16
etc.

(Now, you know the above is true because you can draw trees for these above values and count the leaf nodes to check if the formula holds. But you can't draw trees for h = over 9000 so that's where the proof from Math comes in.)

Base case holds. Note that it isn't necessary to show so many base cases, but what I am trying to show you is that the terms are always twice as much as the previous term. This is exactly what you want to prove but for all h > 0.

i.e. f(h) = 2*f(h-1) is what you want to prove. This is the actual problem. If you are able to prove that the next term is always twice as the previous term, this will mean that it will be true for all. In this case h > 0.

Consider h = k;
f(k) = 2^(k-1) by just plugging it into the f(h) = 2^(h-1) formula.

Now we need to show that the next term in the sequence (k+1) is twice as much as the above. We're not going to plug it in the formula this time, but we're going to check if it is actually twice as much.

So f(k+1)
= 2*f(k)
= 2*2^(k-1) [2^(k-1) being the previous term]
= (2^1)*2^(k-1) [Wrote it this way to show that they're the same bases so we can add the powers]
= 2^(k-1+1) [I know this equals 2^k but let us leave it this way]
= 2^(k+1-1) [rearranged a little]

Therefore:
f(k+1) = 2^([k+1]-1)

k+1 is the next term of the sequence and this looks like the original formula f(h) = 2^(h-1) where h = k+1.

In conclusion, a binary tree which is both full and complete and has h levels contains a total of 2^(h-1) leaf nodes for all h > 0.

Basically, we showed that it is true for one term. Then we showed it is true for the term after it. Therefore every term after the previous term is always true. Therefore the sequence is always true. This is the logic for basically all "Proof By Induction" problems and its just ... fucking genius.