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
Midsquare Method :- this operates in 2 steps. In the first step the square of the key value K is taken. In the 2nd step, the hash value is obtained by deleting digits from ends of

How can the third dimension be displayed on the screen The main problem in visualization is the display of three-dimensional objects and scenes on two-dimensional screens. How

Which sorting algorithm is easily adaptable to singly linked lists? Simple Insertion sor t is easily adabtable to singly linked list.

Draw the process flow diagram: Anand   Dairy (AD) sources 150,000 litres of milk daily from large number of local villagers .The milk is collected from 4:00 AM to 6:00 am and

Containers Introduction Simple abstract data types are useful for manipulating simple sets of values, such as integers or real numbers however more complex abstract data t

Preconditions assertion A precondition is an assertion which should be true at the initiation of an operation. For instance, a square root operation can't accept a negative a

Q. Write an algorithm INSERT which takes a pointer to a sorted list and a pointer to a node and inserts the node into its correct position or place in the list.  Ans: /* s

Have you ever thought about the handling of our files in operating system? Why do we contain a hierarchical file system? How do files saved & deleted under hierarchical directories

Q. Implement a stack making use of the linked list. Show the PUSH and POP operations both. A n s . Stack implemantation using linked list # include # include

calculate gpa using an algorithm