# Internal Path Length: Solving the Mystery

• zak100
In summary: But what is the total distance for the whole tree in terms of levels. Can we say that the total distance is 24. If not then kindly guide me.Zulfi.In summary, the internal path length (IPL) of a tree is the total distance, in terms of levels, from each node to the root. This can be calculated by labeling each node with its distance from the root and then adding up all the numbers. In the example given, the total distance for the whole tree would be 24.
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

#### Attachments

• IPL3.jpg
12.6 KB · Views: 383
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.

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.

zak100 said:
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.

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.

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.

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.

zak100 said:
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.

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.

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.

Yes. (Mostly)

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

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.

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.

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.

## 1. What is the internal path length?

The internal path length is a measure used to analyze the efficiency of a binary tree data structure. It is the sum of the lengths of all paths from the root node to each leaf node in the tree.

## 2. Why is the internal path length important?

The internal path length can give insight into the efficiency of a binary tree in terms of storage and retrieval of data. It can also help identify areas where the tree can be improved for better performance.

## 3. How is the internal path length calculated?

The internal path length is calculated by adding the depth of each node in the tree. The depth is the number of edges from the node to the root. This calculation is performed for each leaf node, and the results are summed to get the total internal path length.

## 4. What is the relationship between internal path length and tree height?

The internal path length is directly related to the height of a tree. As the height of a tree increases, the internal path length also increases. This is because the height of a tree determines the number of levels or edges in the tree, which directly affects the depth of each node and, subsequently, the internal path length.

## 5. How can the internal path length be optimized?

The internal path length can be optimized by balancing the tree. This means rearranging the nodes in a way that minimizes the depth of each node and, consequently, reduces the internal path length. There are various balancing algorithms that can be used to achieve this optimization.

• Engineering and Comp Sci Homework Help
Replies
4
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
10
Views
1K
• Engineering and Comp Sci Homework Help
Replies
4
Views
1K
• Engineering and Comp Sci Homework Help
Replies
16
Views
3K
• Engineering and Comp Sci Homework Help
Replies
12
Views
1K
• Engineering and Comp Sci Homework Help
Replies
15
Views
2K
• Engineering and Comp Sci Homework Help
Replies
14
Views
4K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K