in DS retagged by
8,534 views
30 votes

The weighted external path length of the binary tree in figure is ______

in DS retagged by
8.5k views

1 comment

In the subject wise test, for this question, only option were given as A B C D, no numerical values were given, please check.
1

2 Answers

52 votes
 
Best answer
This is straightforward. The nodes of the given tree are given in square boxes. The weights associated with the nodes are the numbers example $15,9,10$ etc.

Weighted path length $=\sum$ (for(each node in the tree) (path length)$*$(weight of the node) ).

                                        $= \displaystyle{}\sum_{i=1}^{n} \text{Path  Length}_{i} \ast  \text{Weight  of  Node}_{i} $

So answer (written in path_length * weight form) $ = 4*2 + 4*4 + 4*5 + 4*7 + 3*9 + 3*10 + 1*15 = 144.$
edited by
10 votes
I am not so sure, But will it be like this?

4+2 = 6

7+5 = 12

12+6 = 18

9+10 = 19

18+19 = 37

37+15 = 52.

So total 52.

Or will it be

=> 4(4+2) + 4(5+7) + 3(9+10) + 1(15)

=> 24 + 48 + 57 + 15

=> 144.

2 Comments

It'll be the second way. We need to multiply the path length with the corresponding weight.

http://mathworld.wolfram.com/ExternalPathLength.html

11
edited by

@Arjun Sir

This is right?

1
Answer:

Related questions