Internal Path Length: Solving the Mystery

[zak100]

Homework Statement

I can't understand the concept of internal path length. I can't understand what this value mean in the tree? For instance if a IPL of a tree is 30 then what does it mean for the tree. Tree does not have 30 nodes so what the path length means?

Li is the number of nodes in Level i

Homework Equations

Summation (i-1) * Li

The Attempt at a Solution

IPL = 30: for the attached figure(one node at level 0, two at level 1, four at level 2, four at level 3and 2 at level 4:

1 * 0+2* 1 + 4 * 2+ 4 * 3 + 2 * 4= 30.

Some body please tell me how can we see this value in the tree through nodes??

Zulfi

 

[andrewkirk]

The IPL is the sum, over all nodes in the tree, of the distance from each node to the root.

You can see this in a diagram by erasing the numbers written on the nodes of your tree and replacing them by the distance of the node from the root. So the root has 0, the two on the next level have 1, the four on the next level have 2, and so on. Then just add up all the numbers to get the IPL.

It's straightforward to show that that gives the same number as the formula you have written above under 'relevant equations'.

You can also think of it as follows: label the nodes of the tree as 1 to n. Then label n little robots with the numbers from 1 to n and program each robot to walk along the tree to the node with the same label as it has and stop there. Then the IPL is the total distance walked by all the little robots.

 

[zak100]

Hi,
Thanks for your reply. I am calculating the IPL for the tree which i have attached. IPL = 30 & there are only 13 nodes in the tree. This is discrepancy according to what you are saying
<
You can see this in a diagram by erasing the numbers written on the nodes of your tree and replacing them by the distance of the node from the root. So the root has 0, the two on the next level have 1, the four on the next level have 2, and so on. Then just add up all the numbers to get the IPL.>
If possible please show me what you are saying.

Zulfi.

 

[andrewkirk]

This is discrepancy according to what you are saying

I'm afraid I don't know what you mean by that. To what discrepancy are you referring? I cannot see a discrepancy.

 

[zak100]

Hi,
In my figure which shows a binary tree, it has only 13 nodes, but IPL is 30 (i have shown this in reply #1). According to your words, if i do labeling then root which is at level 1, it should have path length =0 which is correct but level 2, IPL is 2, and then at Level 3 IPL is 10. I mean this is a contradiction with what you are saying. Kindly guide me.

Zulfi.

 

[andrewkirk]

It's not a contradiction. There are five levels. You have only done three. Why would you expect to get the IPL for the whole tree if you only include the first three levels?

Keep going until you have covered all levels and you'll get 30.

 

[zak100]

Hi,
I have already evaluated this 30 value in my reply#1. You say that it represents a distance.
<You can see this in a diagram by erasing the numbers written on the nodes of your tree and replacing them by the distance of the node from the root. >

Tell me what distance 30 is representing? We don't have 30 nodes. We have only 13 nodes. This means that the distance is not in terms of nodes. Also if i add up edges with nodes, i won't get 30. So 30 is not the sum of edges & nodes. So then what does this distance of 30 mean. If i say that IPL is 30 what this value would mean?

Zulfi.

 

[andrewkirk]

If i say that IPL is 30 what this value would mean?

I have already given you two meanings for it: one in the first paragraph of post 2 and the other in the last paragraph of post 2.

If you cannot understand those explanations then I am afraid there is nothing more that I can do to help you.

 

[Tom.G]

OK, let's start over.
We will do just the left side of the tree here.

Node 8 is the Root.
Node 3 is next. Node 3's distance from Root is 1, so node 3 is labelled '1'
Node 1 distance from Root is 2 so node 1 is labelled '2'. (Node 3 is already labelled and it has not moved, so leave it alone. It is already labelled.)
Node 5 distance from Root is 2 so node 5 is also labelled '2'. (Node 3 is already labelled, so leave it alone.)
Node 6 distance from Root is 3 so node 6 is labelled '3'. (Nodes 3 & 5 are already labelled, so leave them alone.)
Node 7 distance from Root is 4 so node 7 is labelled '4'. (Nodes 3, 5, 6 are already labelled, so leave them alone.)

Do you see a pattern?
The left side of the tree has an IPL of 1+2+2+3+4 = 12.

Now try the same approach with the right side of the tree.

 

[zak100]

Hi my friend,
Great! I like it.
<
Node 8 is the Root.
Node 3 is next. Node 3's distance from Root is 1, so node 3 is labelled '1'
>
You are trying to provide solution to what andrewkirk stated. Good.

I would try what you say but i think i did not make my question clear. You people are talking about distance. Here in case of IPL distance is not in terms of metres or km but i think its in the context of levels and not in terms of nodes, is this correct??

Zulfi.

 

[Tom.G]

Yes. (Mostly)

Or put another way, you could consider each edge to be one unit of distance.

 

[zak100]

Hi,
Thanks for your help. The right side of the tree has IPL = 1 + 2 + 2 + 3 + 3+ 3 + 4= 18.
If i sum (IPL of boh sides) them i would get an answer of 30. Can we say that the lowest IPL of tree is 0 & maximum IPL is 30??
Zulfi.

 

[Tom.G]

You could describe the IPL as the total distance (number of edges) traversed if you visited each node in turn, always starting at the root.

For instance if you start in Paris (the root) and travel to Bonn, that's length 1. Then you return to Paris (free, there was a sale on roundtrip tickets). Then the following month you travel to Tokyo from Paris, but you have to change airlines in Bonn. That makes the Tokyo trip length 2. So altogether your travel length was 3; which is the IDL for your vacation.

The only way to have a zero IDL is if the only node in a tree is the root. You can't have a length if there is no place to go. And if there is a place to go, there is a length.

 

[zak100]

Hi,
Thanks for your help.
<You could describe the IPL as the total distance (number of edges) traversed if you visited each node in turn, always starting at the root.>
I feel your above answer is correct.

Zulfi.