in DS retagged by
13,526 views
44 votes
44 votes

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

in DS retagged by
13.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
1

2 Answers

66 votes
66 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
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
11
edited by

@Arjun Sir

This is right?

5
5
Answer:

Related questions