trees figure result of splaying the previous tree at node the analysis of splay trees is difficultbecause it must take into account the everchanging structure of the tree on the other handsplay trees are much simpler to program than most balanced search treessince there are fewer cases to consider and no balance information to maintain some empirical evidence suggests that this translates into faster code in practicealthough the case for this is far from complete finallywe point out that there are several variations of splay trees that can perform even better in practice one variation is completely coded in tree traversals (revisitedbecause of the ordering information in binary search treeit is simple to list all the items in sorted order the recursive function in figure does the real work convince yourself that this function works as we have seen beforethis kind of routine when applied to trees is known as an inorder traversal (which makes sensesince it lists the items in orderthe general strategy of an inorder traversal is to process the left subtree firstthen perform processing at the current nodeand finally process the right subtree the interesting part about this algorithmaside from its simplicityis that the total running time is (nthis is because there is constant work being performed at every node in the tree each node is visited onceand the work performed at each node is testing against nullptrsetting up two function callsand doing an output statement since there is constant work per node and nodesthe running time is (nsometimes we need to process both subtrees first before we can process node for instanceto compute the height of nodewe need to know the height of the subtrees first the code in figure computes this since it is always good idea to check the special cases--and crucial when recursion is involved--notice that the routine will declare the height of leaf to be zerowhich is correct this general order of traversalwhich we have also seen beforeis known as postorder traversal againthe total running time is ( )because constant work is performed at each node