it is important to understand why algorithm height is more efficient than height the algorithm is recursiveand it progresses in top-down fashion if the method is initially called on the root of it will eventually be called once for each position of this is because the root eventually invokes the recursion on each of its childrenwhich in turn invokes the recursion on each of their childrenand so on we can determine the running time of the height algorithm by summingover all the positionsthe amount of time spent on the nonrecursive part of each call (review section for analyses of recursive processes in our implementationthere is constant amount of work per positionplus the overhead of computing the maximum over the iteration of children although we do not yet have concrete implementation of children( )we assume that such an iteration is generated in ( timewhere denotes the number of children of algorithm height spends ( time at each position to compute the maximumand its overall running time is op ( ) ( in order to complete the analysiswe make use of the following property proposition let be tree with positionsand let denote the number of children of position of thensumming over the positions of justificationeach position of with the exception of the rootis child of another positionand thus contributes one unit to the above sum by proposition the running time of algorithm height when called on the root of is ( )where is the number of positions of revisiting the public interface for our tree classthe ability to compute heights of subtrees is beneficialbut user might expect to be able to compute the height of the entire tree without explicitly designating the tree root we can wrap the nonpublic height in our implementation with public height method that provides default interpretation when invoked on tree with syntax heightsuch an implementation is given in code fragment def height(selfp=none)"""return the height of the subtree rooted at position if is nonereturn the height of the entire tree ""if is nonep self rootstart height recursion return self height (pcode fragment public method tree height that computes the height of the entire tree by defaultor subtree rooted at given positionif specified