current current rightchildif(current =null/if end of the line /insert on right parent rightchild newnodereturn/end else go right /end while /end else not root /end insert(/we use new variableparent (the parent of current)to remember the last non-null node we encountered ( in figure this is necessary because current is set to null in the process of discovering that its previous value did not have an appropriate child if we didn' save parentwe would lose track of where we were to insert the new nodechange the appropriate child pointer in parent (the last nonnull node you encounteredto point to the new node if you were looking unsuccessfully for parent' left childyou attach the new node as parent' left childif you were looking for its right childyou attach the new node as its right child in figure is attached as the left child of traversing the tree traversing tree means visiting each node in specified order this process is not as commonly used as findinginsertingand deleting nodes one reason for this is that traversal is not particularly fast but traversing tree is useful in some circumstancesand it' theoretically 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 first and 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