Mathematical Induction in binary trees

In summary, the proof shows that every 2-tree with n internal nodes has n+1 external nodes. The base case of n=1 has 1 internal node and 2 external nodes. In the inductive step, it is shown that for k internal nodes, there are k+1 external nodes. By adding an internal node, 1 external node is eliminated, resulting in a net change of +2 external nodes and +1 internal node. This demonstrates that for every additional internal node, there is an increase of 2 external nodes.
  • #1
TheMathNoob
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.
 
Physics news on Phys.org
  • #2
TheMathNoob said:
so k+1 internal nodes will have (k+1)+1 external nodes.
What is your reason for thinking that that follows?
 
  • #3
andrewkirk said:
What is your reason for thinking that that follows?
k internal nodes= k+1 external nodes. But I have been thinking and this doesn't 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 don't know how to show that.
 
  • #4
What happens to the internal and external node counts when you take an external node and give it two child nodes?
 
  • #5
andrewkirk said:
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
Yes there are two new external nodes, but what is the net change in the number of external nodes?.
 
  • #7
andrewkirk said:
Yes there are two new external nodes, but what is the net change in the number of external nodes?.
1?
 

1. What is mathematical induction in binary trees?

Mathematical induction in binary trees is a proof technique used to prove statements about binary trees. It involves breaking down a complex problem into smaller subproblems, and then proving the statement for the smallest subproblem. Next, the proof is extended to the next level of the tree, and this process is repeated until the entire tree is covered.

2. How is mathematical induction used in binary trees?

Mathematical induction is used in binary trees to prove statements about their properties or behavior. It allows us to prove these statements for a specific tree, and then generalize it to all trees of that structure. This is especially useful for proving properties of recursive algorithms on binary trees.

3. What are the steps involved in mathematical induction in binary trees?

The steps involved in mathematical induction in binary trees are as follows:

  • Step 1: Prove the statement for the smallest binary tree (usually a single node).
  • Step 2: Assume the statement is true for a binary tree with n nodes.
  • Step 3: Prove that if the statement is true for a tree with n nodes, it is also true for a tree with n+1 nodes.
  • Step 4: Conclude that the statement is true for all binary trees of that structure.

4. Can mathematical induction be used for any property of binary trees?

No, mathematical induction can only be used for properties that can be proved using a recursive approach. This means that the property must be true for a single node, and if it is true for a tree with n nodes, it must also be true for a tree with n+1 nodes.

5. What are some common mistakes to avoid when using mathematical induction in binary trees?

Some common mistakes to avoid when using mathematical induction in binary trees include:

  • Not proving the statement for the smallest binary tree.
  • Assuming the statement is true for a tree with n+1 nodes, without first proving it for a tree with n nodes.
  • Not considering all possible cases when extending the proof to a tree with n+1 nodes.
  • Using the wrong base case or making incorrect assumptions about the base case.

Similar threads

Proving the Number of Leaves is One More Than Internal Nodes in Binary Trees
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Comp Sci Number of trees in a Fibonacci Heap without CASCADING-CUT
    • Engineering and Comp Sci Homework Help
Replies
11
Views
1K
I How do leaf nodes behave in regression decision trees?
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
852
Comp Sci Validating Braces Placement for Expression Evaluation
    • Engineering and Comp Sci Homework Help
Replies
10
Views
1K
Finding a Local Minimum in a Complete Binary Tree with Log(N) Probes
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Comp Sci Working with classes and vectors in C++
    • Engineering and Comp Sci Homework Help
Replies
15
Views
1K
How can the countability of binary trees be proven?
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Calculate the time of an all-to-all broadcast for a balanced binary tree (BBT)
    • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
Deleting Nodes w/ 2 Children from a BST
    • Engineering and Comp Sci Homework Help
Replies
6
Views
1K
Can You Solve This Recurrence Using the Recursion Tree Method?
    • Engineering and Comp Sci Homework Help
Replies
8
Views
1K

Hot Threads

Recent Insights

Back
Top