• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Binary trees

  • Thread starter craig1928
  • Start date
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? 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.
 
32,467
4,200
Proof by induction is the way to go. A tree with 2 levels has 2 leaf nodes (= 22 - 1 nodes). A tree with 3 levels has 4 leaf nodes (= 23 - 1).

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

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top