‘Every binary tree has an odd number of vertices’ explain
Answers
Answered by
2
Apart from the root, every vertex in a binary tree is of odd degree. We know that there are even number of such odd vertices. Therefore when the root (which is of even degree) is added to this number, the total number of vertices is odd.
Answered by
14
Prove a complete binary tree has an odd number of vertices.
My attempt at the solution:
Basis step: A binary tree with a height of 0 is a single vertex. This would result in the tree having an odd number of vertices (1). Correct.
Inductive hypothesis: A complete binary tree with a height greater than 0 and less than k has an odd number of vertices.
Prove: A binary tree with a height of k+1 would have an odd number of vertices.
A complete binary tree with a height of k+1 will be made up of two complete binary trees k1 and k2. K1 and K2 are both complete binary trees meaning they have an odd number of vertices. They can be represented by (2m+1) and (2n+1). A tree with the hieght of k+1 can be represented by (2m+1) + (2n+1) plus 1 connecting vertice. Since (2m+1)+(2n+1) = (2m+2n+2) = 2(m+n+1) we can see that the number of vertices in k1+k2 is even. By adding the connecting vertex we get 2(m+n+1)+1. An odd number. Therefor a tree with the height of k+1 has an odd number of vertices.
Does this work, or have I made a mistake?
My attempt at the solution:
Basis step: A binary tree with a height of 0 is a single vertex. This would result in the tree having an odd number of vertices (1). Correct.
Inductive hypothesis: A complete binary tree with a height greater than 0 and less than k has an odd number of vertices.
Prove: A binary tree with a height of k+1 would have an odd number of vertices.
A complete binary tree with a height of k+1 will be made up of two complete binary trees k1 and k2. K1 and K2 are both complete binary trees meaning they have an odd number of vertices. They can be represented by (2m+1) and (2n+1). A tree with the hieght of k+1 can be represented by (2m+1) + (2n+1) plus 1 connecting vertice. Since (2m+1)+(2n+1) = (2m+2n+2) = 2(m+n+1) we can see that the number of vertices in k1+k2 is even. By adding the connecting vertex we get 2(m+n+1)+1. An odd number. Therefor a tree with the height of k+1 has an odd number of vertices.
Does this work, or have I made a mistake?
Similar questions