Share
Explore BrainMass

Internal Path Length (IPL) of a tree

The Internal Path Length (IPL) of a tree is the sum of the length of the paths from the root to all nodes in the tree.

Use structural induction (induction over the height of the tree, h) to show that:

IPL( T ) = IPL( left( T )) + IPL( right( T )) + num_nodes( T ) - 1

Solution Preview

This response is intended as a mere guidance. Please express it in your own words in case you want to use it for any assignment/exam submission.

In this response, I am considering an empty tree (that is, a tree without any nodes) of height 0 and a tree with just one node as of height 1. Height of tree is indicated by "h" in following explanation.

Base case (h=0):

When there are no nodes in a tree, there are no paths and thus the sum of the length of the paths from the root to all nodes in the tree = 0.
That is to say,
h=0 => IPL(T) = 0

Base case (h=1):

When there is just one node in the tree, there will be just one path from the root to all nodes in the tree. Since this node is root ...

Solution Summary

This response considers an empty tree (that is, a tree without any nodes) of height 0, and a tree with just one node as of height 1.

$2.19