Degree of node, Data Structure & Algorithms

Assignment Help:

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.

 


Related Discussions:- Degree of node

Hashing, what is hashing? what are diffrent method of hashing?

what is hashing? what are diffrent method of hashing?

Algorithm and flow chart, algorithm and flow chart to find weather the give...

algorithm and flow chart to find weather the given numbers are positive or negative or neutral

Operating system, discuss the operating system under the following: MONOLIT...

discuss the operating system under the following: MONOLITHIC SYSTEM,LAYER SYSTEM AND VIRTUAL MACHINES

Data Warehousing, Assume you are in the insurance business. Find two exampl...

Assume you are in the insurance business. Find two examples of Type 2 slowly changing dimensions in that business. As an analyst on the project, write the specifications for applyi

Explain binary search tree, Binary search tree. A binary search tree is...

Binary search tree. A binary search tree is a binary tree that is either empty or in which every node having a key that satisfies the following conditions: - All keys (if an

Algorithm of binary search, Step 1: Declare array 'k' of size 'n' i.e. k(n)...

Step 1: Declare array 'k' of size 'n' i.e. k(n) is an array which stores all the keys of a file containing 'n' records Step 2: i←0 Step 3: low←0, high←n-1 Step 4: while (l

State about the pre- and post conditions, State about the pre- and post con...

State about the pre- and post conditions Programmers can easily document other pre- and post conditions and class invariants, though, and insert code to check most value preco

If-then-else statements, In this example, suppose the statements are simple...

In this example, suppose the statements are simple unless illustrious otherwise. if-then-else statements if (cond) { sequence of statements 1 } else { sequence of st

Functions for inserting and deleting at either end of deque, Q. Devise a re...

Q. Devise a representation for a given list where insertions and deletions can be made at both the ends. Such a structure is called Deque (which means Double ended queue). Write fu

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd