search trees the "firstposition of binary search tree can be located by starting walk at the root and continuing to the left childas long as left child exists by symmetrythe last position is reached by repeated steps rightward starting at the root the successor of positionafter( )is determined by the following algorithm algorithm after( )if right(pis not none then {successor is leftmost position in ' right subtreewalk right(pwhile left(walkis not none do walk left(walkreturn walk else {successor is nearest ancestor having in its left subtreewalk ancestor parent(walkwhile ancestor is not none and walk =right(ancestordo walk ancestor ancestor parent(walkreturn ancestor code fragment computing the successor of position in binary search tree the rationale for this process is based purely on the workings of an inorder traversalgiven the correspondence of proposition if has right subtreethat right subtree is recursively traversed immediately after is visitedand so the first position to be visited after is the leftmost position within the right subtree if does not have right subtreethen the flow of control of an inorder traversal returns to ' parent if were in the right subtree of that parentthen the parent' subtree traversal is complete and the flow of control progresses to its parent and so on once an ancestor is reached in which the recursion is returning from its left subtreethen that ancestor becomes the next position visited by the inorder traversaland thus is the successor of notice that the only case in which no such ancestor is found is when was the rightmost (lastposition of the full treein which case there is no successor symmetric algorithm can be defined to determine the predecessor of positionbefore(pat this pointwe note that the running time of single call to after(por before(pis bounded by the height of the full treebecause it is found after either single downward walk or single upward walk while the worst-case running time is ( )we note that either of these methods run in ( amortized timein that series of calls to after(pstarting at the first position will execute in total of (ntime we leave formal justification of this fact to exercise - but intuitively the upward and downward paths mimic steps of the inorder traversal ( related argument was made in the justification of proposition