descendant of xif is at level ithen is said to be at level + converselynode is said to be the (directancestor of the root of tree is defined to be at level the maximum level of any element of tree is said to be its depth or height fig two distinct trees if an element has no descendantsit is called terminal node or leafand an element that is not terminal is an interior node the number of (directdescendants of an interior node is called its degree the maximum degree over all nodes is the degree of the tree the number of branches or edges that have to be traversed in order to proceed from the root to node is called the path length of the root has path length its direct descendants have path length etc in generala node at level has path length the path length of tree is defined as the sum of the path lengths of all its components it is also called its internal path length the internal path length of the tree shown in fig for instanceis evidentlythe average path length is pint (si < <nn in where is the number of nodes at level in order to define what is called the external path lengthwe extend the tree by special node wherever subtree was missing in the original tree in doing sowe assume that all nodes are to have the same degreenamely the degree of the tree extending the tree in this way therefore amounts to filling up empty brancheswhereby the special nodesof coursehave no further descendants the tree of fig extended with special nodes is shown in fig in which the special nodes are represented by squares the external path length is now defined as the sum of the path lengths over all special nodes if the number of special nodes at level is mi then the average external path length is pext (si < <mi im in the tree shown in fig the external path length is the number of special nodes to be added in tree of degree directly depends on the number of original nodes note that every node has exactly one edge pointing to it thusthere are + edges in the extended tree on the other handd edges are emanating from each original nodenone from the special nodes thereforethere exist * + edgesthe resulting from the edge pointing to the root the two results yield the following equation between the number of special nodes and of original nodesd + +nor ( - the maximum number of nodes in tree of given height is reached if all nodes have subtreesexcept those at level hall of which have none for tree of degree dlevel then contains node (namelythe root)level contains its descendantslevel contains the descendants of the nodes at level etc this yields nd(hsi < hd as the maximum number of nodes for tree with height and degree for we obtain (