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


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
What is AVL Tree? Describe the method of Deletion of a node from and AVL Tree ?

b) The user will roll two (six-sided) dices and the user will lose the game if (s)he gets a value 1 on either any of the two dices & wins otherwise. Display a message to the user w

two standards ways of traversing a graph in data structure

What is a first-in-first-out data structure ? Write algorithms to perform the following operations on it – create, insertion, deletion, for testing overflow and empty conditions.

Write a program to create a hashed file that stores the records currently in the file " data_2013 ". Records should use the same fixed-length schema given previously, and should ag

B Tree Unlike a binary-tree, every node of a B-tree may have a variable number of keys and children. The keys are stored in non-decreasing order. Every key has an associated ch

H o w can you r ot a t e a B i n a r y Tr e e? E x pl a i n r i g h t a n d l eft r ot a tion s by taking an e x a mpl e.   If after

Normally a potential y satisfies y r = 0 and 0 ³ y w - c vw -y v . Given an integer K³0, define a K-potential to be an array y that satisfies yr = 0 and K ³ y w - c vw -y v

A stack is a last in, first out (LIFO) abstract data type and sequential data structure. A stack may have any abstract data type as a component, but is characterized by two fundame