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
Describe an algorithm to play the Game of Nim using all of the three tools (pseudocode, flowchart, hierarchy chart)

Explain in detail the algorithmic implementation of multiple stacks.

Define order of growth The  efficiency  analysis  framework  concentrates   on  the  order  of  growth  of  an  algorithm's   basic operation count as the principal indicator o

Complexity : How do the resource needs of a program or algorithm scale (the growth of resource requirements as a function of input). In other words, what happens with the performan

The structures of files vary from operating system to operating system. In this unit, we will discuss the fundamentals of file structures with the generic file organisations. A

AVL tree An AVL tree is a binary search tree in which the height of the left and right subtree of the root vary by at most 1 and in which the left and right subtrees are again

The smallest element of an array's index is called its Lower bound.

As part of an experiment, a school measured heights (in metres) of all its 500 students. Write an algorithm, using a flowchart that inputs the heights of all 500 students and ou

Decision Tree A decision tree is a diagram that shows conditions and actions sequentially and therefore shows which condition is to be considered first, second and so on. It is

(a) Suppose that t is a binary tree of integers (that is, an object of type BinTree of Int.) in the state shown in Figure 3.   Give the vectors returned by each of the f