Logout

Traversing Binary Search Trees

To traverse through a list, should you wish, is very straight-forward: just keep on using getNext() to move through, stating at one end and getting to the other, doing whatever you want with the data that you encounter.

Traversing through a binary search tree is a different matter. How will you approach it, so that you get to each and every node, doing so in an orderly, efficient manner.

As it turns out, there are three generally accepted ways, and the convention is to call them "pre-order traversal", "in-order traversal", and "post-order traversal". The names refer to the order in which the accessing of the data occurs, in combination with two recursive calls, which will be required to do both sides that branch off of each node:

Pre-order traversal: - the accessing of the data comes first, then the two recursive calls.

sout(node.getData()
preOrderTraversal(left)
preOrderTraversal(right)

In-order traversal - the accessing of the data is inbetween the two recursive calls.

preOrderTraversal(left)
sout(node.getData()
preOrderTraversal(right)

Post-order traversal - the accessing of the data is done after the two recursive calls.

preOrderTraversal(left)
preOrderTraversal(right)
sout(node.getData()

The tricky part about tracing through each traversal, is to keep in mind that with recursion, whenever a recursive call interrupts a previous called instance of a recursive method, that former call must go on a stack of unfinished methods - so it remains there until the interrupting call(s) is/are finished. So in the case of both in-order and post-order traversals, there are lots of "souts" waiting to sout while new instances of the traversal keep being "born".

To see and get used to these traversals, here's a great animation.

And then you can go a bit deeper with how the recursive nature of the code is accomplishing things by looking at my pre-order animation.