reshown by
998 views
1 votes
1 votes
Consider a binary tree T that has 50 leaf nodes. Then the number of nodes in T that have exactly

ONE children are ______.
reshown by

3 Answers

2 votes
2 votes
Caption

like this for 50 nodes exactly one children nodes will be from  0 to 50

1 votes
1 votes

 

Let number of nodes with exactly two children be x, and with exactly one children be y.

Total degree = 50 + 3x+ 2y −1 (As all nodes with 2 children have degree 3 except the root)

N = Total No. of nodes=x+y+50      --------eq.1

we know 2*total edges = sum of all degree

2(x+y+50-1) = 50 + 3x + 2y -1

2x + 2y + 100 - 2 = 50 + 3x + 2y -1

x = 49 Putting this in eq.1, we get

N =  49 + y + 50 

so, y = the number of nodes in T that have exactly ONE children = N - 99

0 votes
0 votes
number of leaf nodes is free from no of nodes with one child...........it can be any no. irrespective of no. of leaves

Related questions

0 votes
0 votes
0 answers
1
sandeep singh gaur asked Feb 22, 2019
453 views
somewhere we seen that formula-How many binary tree possible without labeled =c(2n,n)/n+1. anybody explain how we get this formula.
1 votes
1 votes
1 answer
2
Kaluti asked Mar 28, 2018
330 views
Give an algorithm for finding the height or depth of the tree
2 votes
2 votes
2 answers
3
Vegeta asked Jul 16, 2018
1,342 views
How to Construct Full Binary Tree from given preorder and postorder?Thank you.
0 votes
0 votes
0 answers
4
eyeamgj asked Nov 30, 2018
263 views
https://gateoverflow.in/132037/self-doubt-in-binary-search-algoDOUBT : THIS QUESTION 10 ELEMENTS ARE IN ARRAY AND SORTED THEN HOW CAN WE DRAW A BALANCED TREE BECZ IT I...