recategorized
3,460 views
0 votes
0 votes

A binary search tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 19 leaves:

  1. cannot have more than 37 nodes
  2. has exactly 37 nodes
  3. has exactly 35 nodes
  4. cannot have more than 35 nodes
recategorized

8 Answers

0 votes
0 votes

Option B.  has exactly 37 nodes

A strictly binary tree with n leaves contains (2n-1) nodes

0 votes
0 votes
strict binary tree is a tree which has either  "0" children OR  "1"children .  AND

A     n-ary tree      is   a   tree   which has  either   "0"  children OR    "n" children , Which means that n-ary tree is also a strict binary tree , so

we know property of n-ary tree that if   'i' is  no. of internal nodes of complete n-ary tree ,

the no. of leaves in it = i( n-1) +1

so According to question   no. of leaves = 19 [given]    ,  

                                           and as BInary tree so   n=2  

19= i(2-1) +1

19= i+1

i=18   ;   internal nodes= 18 ,  no. of leaves = 19

              so     18 + 19 = 37 (total no. of nodes )  option B is anwser
0 votes
0 votes

Option: B

Explanation : 
A strictly binary tree with 'n' leaves must have (2n - 1) nodes. Verify for some small 'n'. This can be proved by the principle of mathematical induction.

2*19-1=37

A strictly binary tree must have child nodes.

 

0 votes
0 votes
option (2)

Total = Leaves +internal nodes

$T = L  +  I$

$T = 19 +  I$

$I = T-19$

Degree = degree of leaves + degree of internal nodes except root +2(degree of root)

$D = 19 + 3*(I-1) + 2$

Degree = 2 edges

edges = Total nodes -1

so

$2(T-1)  = 19 + 3I -3+2$

$2T-2  = 3I +18$

putting value I

$2T-2  = 3(T-19) +18$

$2T-2  = 3T-57 +18$

$T  = 37$

option 2

has exactly 37 nodes

Related questions

1 votes
1 votes
3 answers
1
Pooja Khatri asked Jul 13, 2018
3,344 views
Consider the array A=<4, 1, 3, 2, 16, 9, 10, 14, 8, 7>. After building heap from the array A, the depth of the heap and the right child of max-heap are ______ and _____ r...
0 votes
0 votes
2 answers
2
Pooja Khatri asked Jul 13, 2018
8,890 views
A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the ...
0 votes
0 votes
2 answers
3
Pooja Khatri asked Jul 13, 2018
2,573 views
Which of the following algorithms solves the single-source shortest paths?Prim's algorithmFloys-Warshall algorithmJohnson's algorithmDijkstra's algorithm
2 votes
2 votes
3 answers
4
Pooja Khatri asked Jul 13, 2018
17,107 views
The maximum number of comparisons needed to sort 9 items using radix sort is (assume each item is 5 digit octal number):4572360450