prove by induction that
(i) The number of leaves in a binary tree
of height 'h' are less than or equal to
2h.
(ii) The number of nodes in a full binary
tree of height 'h' are equal to
(2h+1 _ 1).
Answers
Answered by
10
1) Binary tree the number n of leaves at height h <= 2h.
In a binary tree of height h = 1, there is only one node.
Number of nodes n = 1. Hence n <= 2h is true.
Let us say at height H the number N of nodes is <= 2H.
Then at height H+1 the number M of nodes will be <= 2 * N.
Because each of N nodes can have at most two children nodes.
So at height H+1 , number of nodes <= 2 * N <= 2 * (2 H)
or <= 2 (H +1) + 2 (H-1)
Since H-1 >=0, the number of nodes at height H+1 <= 2 (H+1).
Hence the given hypothesis is proved by Mathematical Induction.
================
2. Total Number N of nodes in a full binary tree of height n are: N = 2ⁿ - 1.
For a binary tree of height n = 1, there is one node, ie, N = 1.
So N = 2¹ - 1 = 1. So it is true.
In a full binary tree the number N of nodes at a height n will be = 2ⁿ⁻¹. This is clearly known as N follows the geometric series : 1, 2 , 4, 8 , 16 ....
Let us say for a height n the total number of nodes is = N = 2ⁿ - 1.
The number of nodes in the next level (height n+1) will be = 2⁽ⁿ⁺¹⁾ ⁻ ¹ = 2ⁿ.
Total number of nodes in a tree of height n+1 will be then:
= N + 2ⁿ = 2ⁿ -1 + 2ⁿ = 2ⁿ⁺¹ - 1.
Hence the given hypothesis is proved by Math Induction.
In a binary tree of height h = 1, there is only one node.
Number of nodes n = 1. Hence n <= 2h is true.
Let us say at height H the number N of nodes is <= 2H.
Then at height H+1 the number M of nodes will be <= 2 * N.
Because each of N nodes can have at most two children nodes.
So at height H+1 , number of nodes <= 2 * N <= 2 * (2 H)
or <= 2 (H +1) + 2 (H-1)
Since H-1 >=0, the number of nodes at height H+1 <= 2 (H+1).
Hence the given hypothesis is proved by Mathematical Induction.
================
2. Total Number N of nodes in a full binary tree of height n are: N = 2ⁿ - 1.
For a binary tree of height n = 1, there is one node, ie, N = 1.
So N = 2¹ - 1 = 1. So it is true.
In a full binary tree the number N of nodes at a height n will be = 2ⁿ⁻¹. This is clearly known as N follows the geometric series : 1, 2 , 4, 8 , 16 ....
Let us say for a height n the total number of nodes is = N = 2ⁿ - 1.
The number of nodes in the next level (height n+1) will be = 2⁽ⁿ⁺¹⁾ ⁻ ¹ = 2ⁿ.
Total number of nodes in a tree of height n+1 will be then:
= N + 2ⁿ = 2ⁿ -1 + 2ⁿ = 2ⁿ⁺¹ - 1.
Hence the given hypothesis is proved by Math Induction.
kvnmurty:
:-)
Similar questions