Path length of Binary Tree


What is the relation between internal path length and external path length in a binary tree?


In an external binary tree, all nodes have either 2 children or 0 children.
The nodes with two children are called internal nodes.
The nodes with zero child are called external nodes( “extended” nodes ).

Internal path length(I) is the summation of the lengths all of the lengths all paths from the root of a binary tree to each of its nodes.
External path length(E) is the summation of the lengths of path lengths to the “extended” nodes of a binary tree, usually the null nodes with zero children .

E = I + 2n (where n is the number of internal nodes)