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© BrainMass Inc. brainmass.com October 25, 2018, 5:43 am ad1c9bdddf
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 ...
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.