The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
3k views

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

asked in DS by Veteran (59.5k points) | 3k views

2 Answers

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

                                        = $\sum_{i=1}^{n} PathLength_{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 = \mathbf{144}$

answered by (171 points)
edited by
+8 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.
answered by Boss (19.7k points)
+8

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

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



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,072 questions
44,645 answers
127,047 comments
43,699 users