Degree of node, Data Structure & Algorithms

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







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
Related Questions
the voltage wave forms are applied at the inputs of an EX-OR gate. determine the output wave form

human resource management project work in c++

what happen''s in my computer when i input any passage

Huffman Encoding is one of the very simple algorithms to compress data. Even though it is very old and simple , it is still widely used (eg : in few stages of JPEG, MPEG etc). In t

Explain the Arrays in Ruby Ruby arrays are dynamic arrays which expand automatically whenever a value is stored in a location beyond current end of the array. To the programmer

How many recursive calls are called by the naïve recursive algorithm for binomial coefficients, C(10, 5) and C(21, 12) C(n,k){c(n-1,k)+c(n-1,k-1) if 1 1 if k = n or k = 0

Assume you are in the insurance business. Find two examples of Type 2 slowly changing dimensions in that business. As an analyst on the project, write the specifications for applyi

In this project you will write a program to produce a discrete time simulation of a queue as shown in Fig. 1. Time is slotted on the input and the output. Each input packet follows

explain implementation of circular queue insert,delete operations

Write an algorithm for binary search. Algorithm for Binary Search 1.  if (low> high) 2.  return (-1) 3.  Mid = (low + high)/2 4.  if ( X = = a[mid]) 5.  return (mid); 6.