height the height of position in tree is also defined recursivelyif is leafthen the height of is otherwisethe height of is one more than the maximum of the heights of ' children the height of nonempty tree is the height of the root of for examplethe tree of figure has height in additionheight can also be viewed as follows proposition the height of nonempty tree is equal to the maximum of the depths of its leaf positions we leave the justification of this fact to an exercise ( - we present an algorithmheight implemented in code fragment as nonpublic method height of the tree class it computes the height of nonempty tree based on proposition and the algorithm depth from code fragment worksbut ( ^ worst-case time def height (self)"""return the height of the tree ""return max(self depth(pfor in self positionsif self is leaf( )code fragment method height of the tree class note that this method calls the depth method unfortunatelyalgorithm height is not very efficient we have not yet defined the positionsmethodwe will see that it can be implemented to run in (ntimewhere is the number of positions of because height calls algorithm depth(pon each leaf of its running time is ( pl ( ))where is the set of leaf positions of in the worst casethe sum pl ( is proportional to (see exercise - thusalgorithm height runs in ( worst-case time we can compute the height of tree more efficientlyin (nworst-case timeby relying instead on the original recursive definition to do thiswe will parameterize function based on position within the treeand calculate the height of the subtree rooted at that position algorithm height shown as nonpublic method height in code fragment computes the height of tree in this way time is linear in size of subtree def height (selfp)"""return the height of the subtree rooted at position ""if self is leaf( )return elsereturn max(self height (cfor in self children( )code fragment method height for computing the height of subtree rooted at position of tree