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
Program segment for the deletion of any element from the queue delmq(i)  /* Delete any element from queue i */ { int i,x; if ( front[i] == rear[i]) printf("Queue is

what are the applications of multikey file organization?

Write a function that performs integer division. The function should take the large number in memory location 1 and divide it by the large number in memory location 2 disregarding

Q. Write down the recursive function to count the number of the nodes in the binary tree.    A n s . R ecursive Function to count no. of Nodes in Binary Tree is writt

As we talked in class, a program with two integer variables is universal. Now, we consider a special form of four variableprograms. Let G = (V; E) be a directed graph, where V is a

Step 1: Declare array 'k' of size 'n' i.e. k(n) is an array which stores all the keys of a file containing 'n' records Step 2: i←0 Step 3: low←0, high←n-1 Step 4: while (l

Define Dynamic Programming  Dynamic  programming  is  a  method  for  solving  problems  with  overlapping  problems.  Typically, these sub problems arise from a recurrence rel

While BFS is applied, the vertices of the graph are divided into two categories. The vertices, that are visited as part of the search & those vertices that are not visited as part

Unlike a binary-tree, each node of a B-tree may have a number of keys and children. The keys are stored or saved in non-decreasing order. Each key has an related child that is the

What will be depth do , of complete binary tree of n nodes, where nodes are labelled from 1 to n with root as node and last leaf node as node n