Q. The degree of a node is defined as the number of children it has. Shear show that in any binary tree, the total number of leaves is one more than the number of nodes of degree 2

Ans:

Let n be the total number of nodes of degree 2 in a binary tree T. We have to  show that the number of leaves in T is n+1. Let us prove it by induction technique.

For n=1, the result is certain that the leaves are two i.e. 1+1.

Let the formulae be true for n=k, i.e. if there are n nodes of degree 2 in T then T has k+1 leaves of it.

If we add the two children to one of the leaf node then, the number nodes with degree two will be k+1 and number of leaf node will be (k+1)-1+2 = (k+1)+1. Hence we can conclude by induction method that if a binary tree t has n nodes of degree 2 It then it has n+1 leaves.

 

Posted Date: 7/10/2012 4:09:15 AM | Location : United States

Ask an Expert

Related Discussions:- Degree of node, Assignment Help, Ask Question on Degree of node, Get Answer, Expert's Help, Degree of node Discussions

Write discussion on Degree of node
Your posts are moderated

Write your message here..

Related Questions

Data type, Q. Define the terms data type and abstract data type. Comment up... Q. Define the terms data type and abstract data type. Comment upon the significance of both these.   Ans: We determine the total amount of memory to reserve by determining

Infix expression to postfix form using the stack function, Q. Convert the f... Q. Convert the following given Infix expression to Postfix form using the stack function: x + y * z + ( p * q + r ) * s , Follow general precedence rule and suppose tha

Explain merge sort, Merge sort: Merge sort is a sorting algorithm that ... Merge sort: Merge sort is a sorting algorithm that uses the idea of split and conquers. This algorithm splits the array into two halves, sorts them separately and then merges t

Spanning trees, Spanning Trees: A spanning tree of a graph, G, refer to a ... Spanning Trees: A spanning tree of a graph, G, refer to a set of |V|-1 edges which connect all vertices of the graph. There are different representations of a graph. They are f

What is assertions and abstract data types, Assertions and Abstract Data Ty... Assertions and Abstract Data Types Even though we have defined assertions in terms of programs, notion can be extended to abstract data types (which are mathematical entities).

What are the specific needs for realism, Normal 0 false false... Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

Direct file organisation, It offers an effective way to organize data while... It offers an effective way to organize data while there is a requirement to access individual records directly. To access a record directly (or random access) a relationship is

Collision resolution techniques, complete information about collision resol... complete information about collision resolution techniques

Array implementation of a circular queue, A circular queue can be implement... A circular queue can be implemented through arrays or linked lists. Program 6 gives the array implementation of any circular queue. Program 6: Array implementation of any Circu

Determine the components of illumination, Determine the Components of Illum... Determine the Components of Illumination The light reaching the eye when looking at a surface has clearly come from a source (or sources) of illumination and bounced off the su