Mathematical Induction in binary trees

  • #1
189
4

Homework Statement


Show that every 2-tree(Definition 3.2) with n internal nodes has n+1 external nodes

Homework Equations


A 2 tree is a tree which nodes have 2 children or no children.
Internal nodes are nodes which have two children
external nodes are leafs.

The Attempt at a Solution


Proof
base case
n=1
Internal nodes=1
external nodes=2

Inductive step

Inductive hypothesis: Let k internal nodes have k+1 external nodes
so k+1 internal nodes will have (k+1)+1 external nodes.
 

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,836
1,418
so k+1 internal nodes will have (k+1)+1 external nodes.
What is your reason for thinking that that follows?
 
  • #3
189
4
What is your reason for thinking that that follows?
k internal nodes= k+1 external nodes. But I have been thinking and this doesnt make any sense.
1 internal node= 2 external nodes
so k+1 internal nodes= k+3 external nodes.

I know that when you add an internal node, you should eliminate one external node, but I dont know how to show that.
 
  • #4
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,836
1,418
What happens to the internal and external node counts when you take an external node and give it two child nodes?
 
  • #5
189
4
What happens to the internal and external node counts when you take an external node and give it two child nodes?
+2 external nodes +1 internal nodes
 
  • #6
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,836
1,418
Yes there are two new external nodes, but what is the net change in the number of external nodes?.
 
  • #7
189
4
Yes there are two new external nodes, but what is the net change in the number of external nodes?.
1?
 

Related Threads on Mathematical Induction in binary trees

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
1
Views
831
  • Last Post
Replies
0
Views
972
Replies
3
Views
4K
  • Last Post
Replies
2
Views
1K
Replies
1
Views
4K
  • Last Post
Replies
0
Views
2K
Replies
0
Views
2K
  • Last Post
Replies
2
Views
4K
Top