4.3k views

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

in DS
edited | 4.3k views

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 = sigma(for(each node in the tree) (path length)*(weight of the node) ).

= $\sum_{i=1}^{n} Path \ Length_{i} * 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$
by (171 points)
edited
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.
by Boss (19.9k points)
+9

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

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

+1

@Arjun Sir

This is right?