the algorithm is interesting (it' also simpler than deletionthe discussion of which we want to defer as long as possible there are three simple ways to traverse tree they're called preorderinorderand postorder the order most commonly used for binary search trees is inorderso let' look at that firstand then return briefly to the other two inorder traversal an inorder traversal of binary search tree will cause all the nodes to be visited in ascending orderbased on their key values if you want to create sorted list of the data in binary treethis is one way to do it the simplest way to carry out traversal is the use of recursion (discussed in "recursion" recursive method to traverse the entire tree is called with node as an argument initiallythis node is the root the method needs to do only three things call itself to traverse the node' left subtree visit the node call itself to traverse the node' right subtree remember that visiting node means doing something to itdisplaying itwriting it to fileor whatever traversals work with any binary treenot just with binary search trees the traversal mechanism doesn' pay any attention to the key values of the nodesit only concerns itself with whether node has children java code for traversing the actual code for inorder traversal is so simple we show it before seeing how traversal looks in the workshop applet the routineinorder()performs the three steps already described the visit to the node consists of displaying the contents of the node like any recursive functionthere must be base casethe condition that causes the routine to return immediatelywithout calling itself in inorder(this happens when the node passed as an argument is null here' the code for the inorder(methodprivate void inorder(node localrootif(localroot !nullinorder(localroot leftchild)localroot displaynode()inorder(localroot rightchild)this method is initially called with the root as an argumentinorder(root)after thatit' on its owncalling itself recursively until there are no more nodes to visit