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

Ask an Expert

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

Write your message here..

Related Questions

Recurrence relation, solve the following relation by recursive method: T(n... solve the following relation by recursive method: T(n)=2T(n^1/2)+log n

Stack, infix to revrse polish infix to revrse polish

Explain avl tree, AVL tree An AVL tree is a binary search tree in which... 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

Collision resolution techniques, complete information about collision resol... complete information about collision resolution techniques

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

State the painter algorithm, Painter's Algorithm As the name suggests, ... 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

Linked list, how to creat atm project by using linked list? how to creat atm project by using linked list?

Asymptotic notation.., important points on asymptotic notation to remember important points on asymptotic notation to remember

Brute force, Determine the number of character comparisons made by the brut... 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, What is quick sort?   Answer Quick sort is on... 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