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
solve the following relation by recursive method: T(n)=2T(n^1/2)+log n

infix to revrse polish

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

complete information about collision resolution techniques

how to draw a 5 inch square on the screen using * symbol

Painter's Algorithm As the name suggests, the algorithm follows the standard practice of a painter, who  would paint the background (such as a backdrop) first, then the major d

how to creat atm project by using linked list?

important points on asymptotic notation to remember

Determine the number of character comparisons made by the brute-force algorithm in searching for the pattern GANDHI in the text

What is quick sort?   Answer Quick sort is one of the fastest sorting algorithm used for sorting a list. A pivot point is chosen. Remaining elements are divided or portio