Hi,
I cant understand the concept of internal path length (IPL). I cant 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?
I am calculating the IPL for the tree which i have attached using the formula:

Summation (i-1) * Li
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.
IPL = 30 & there are only 13 nodes in the tree. Book says that "IPL is the sum of all path lengths of all nodes". If there are only 13 nodes, then it means
IPL does not represent nodes of tree nor it represents the sum of nodes & edges of a tree, so what is the purpose of this value?
Zulfi.

allthat

 

In a very large tree it can tell you if the tree is a binary tree. If it is not a binary tree, then it is a measure of how close it is to being a binary tree. It could be useful in estimating the computational resources required for an exhaustive traversal of the tree.

 

What is the smallest IPL that a tree with N nodes can have?

What is the largest IPL that a tree with N nodes can have?

Consider what information the IPL of a given tree with N nodes gives you relative to the above questions.

 

Smallest is 0 & largest is 30.
<
In a very large tree it can tell you if the tree is a binary tree. >
Its very interesting if i can know how IPL value can tell me whether the tree is binary or not?

Zulfi.

 

Smallest is 0 & largest is 30.
<
In a very large tree it can tell you if the tree is a binary tree. >
Its very interesting if i can know how IPL value can tell me whether the tree is binary or not?

Zulfi.

Please draw a binary tree (I'm assuming we are talking about binary trees?) having 30 nodes that has an IPL of 0.

For that matter, please draw a binary tree (I'm assuming we are talking about binary trees?) having 30 nodes that has an IPL of 30.

 

In a very large tree it can tell you if the tree is a binary tree. If it is not a binary tree, then it is a measure of how close it is to being a binary tree. It could be useful in estimating the computational resources required for an exhaustive traversal of the tree.

Do you mean a binary tree as opposed to a trinary tree? Or do you mean a complete binary tree as opposed to a highly imbalanced binary tree?

 

I was thinking of a binary tree where some pathways were shorter than others, as in the picture in the original post, where each node can have 0, 1, or 2 child nodes. If a tree has 4 levels and each node, except the leaf nodes, has two children then we can derive the value of IPL without doing the explicit calculation.

 

I was thinking of a binary tree where some pathways were shorter than others, as in the picture in the original post, where each node can have 0, 1, or 2 child nodes. If a tree has 4 levels and each node, except the leaf nodes, has two children then we can derive the value of IPL without doing the explicit calculation.

That's what I originally thought you meant, but I didn't look carefully at where you said, "if it is not a binary tree". So now I understand that what you were saying is, "if it is not a complete binary tree." Possibly you meant "full binary tree" (one in which every node except the leaf nodes have exactly two children), but those trees only exist for trees having exactly 2^n - 1 nodes for some nonnegative value of n.

 

Please draw a binary tree (I'm assuming we are talking about binary trees?) having 30 nodes that has an IPL of 0.

Not possible. This means that we have 30 nodes in level 1 which is not possible.

For that matter, please draw a binary tree (I'm assuming we are talking about binary trees?) having 30 nodes that has an IPL of 30.

[/QUOTE]
30 nodes are possible in a complete binary tree of level 5 but its IPL is 105.
So if my answer is wrong please show me what you mean?

Zulfi.

 

You've answered your own question.

You previously stated that a tree with 30 nodes has a minimum IPL of 0 and a maximum IPL of 30. But you've just indicated that it can't have an IPL of 0 since that would require that all 30 nodes be at the root level. You've also indicated that a complete tree with 30 nodes would have an IPL of 105, significantly more than the max of 30 you had previously indicated.

At a quick glance, I'm not seeing how you got 105. I got 94 (but that's just in my head, so I might have done something wrong).

 

Hi,
My question was this (post #1 of this thread):
<
If there are only 13 nodes, then it means
IPL does not represent nodes of tree nor it represents the sum of nodes & edges of a tree, so what is the purpose of this value?
>
and I got its answer from some other forum that IPL represents distance of a node from root in terms of edges.

Zulfi.

 

But your very first post indicated that you knew what IPL is. You calculated the value for the tree you used as an example. You asked what information it conveyed and Papabravo told you -- it is a measure of how close or how far a tree is from being a complete binary tree.

If does not represent the distance of a node from the root because it is a cumulative measure of the distances from the root to all of the nodes. The distance of a node from the root in terms of edges is nothing more than the depth of the node (or the layer in which that node lies, with the root lying at level 0).

 

Yes i calculated the value 30 using the formula but i didn't know what this 30 represents. If you say that its a distance then what's its unit? Normally distance is measured in terms of metres or km but here in this case we are using nodes but there are not 30 nodes in the tree so i was confused what this 30 means. If its a distance then what its unit. So i got the answer that its unit is edges & not nodes. Yes at first i also said to them that do we express IPL in terms of levels & i got the answer "most likely" however afterwards he explained with just left tree & showed me how IPL is related to edges. In the first level we will label all nodes as '1' because they are at a distance of 1 edge from root & at the 2nd level we will label all nodes to '2' because they are at a distance of 2 edges from root and so on. In this way if i sum labels of all nodes on the left, i would get 12 & on the right i would get 18.

If we sum both then we will get 30.
Thanks for your efforts.

Zulfi.

 

Yes, the unit for IPL would be edges.

Think of it as the total number of edges you would traverse if you started at the root an then went to one of the nodes, then were teleported back to the root and went to another node, and continued this until you visited all of the nodes exactly once.