Proving Binary Tree Properties: 2^(h-1) Leaf Nodes & 2^(h-1) - 1 Internal Nodes

[craig1928]

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 apparently

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.

thanks.

 

[Mark44]

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

Assume that a tree with k levels has 2^{k - 1} leaf nodes, and then use this to show that a tree with k + 1 levels has 2^k leaf nodes.