Traversing and Searching Trees: Pre-order, In-order, and Post-order

The code above only creates a binary tree but does not do anything. To iterate through a binary tree we will have to traverse it. Typically, depth-first searching is used to traverse binary (and other) trees. There are three popular ways to do this, pre-order, in-order, and post-order.

Pre-order Tree Traversal

Pre-order tree traversal, the easiest of the depth-first tree traversal methods. It is shown recursively below.
public void preorder(Node root) { if(root != null) { //Will print the value of the current node System.out.print(root.key); preorder(root.left); preorder(root.right); } }

This code prints values in the same line. Consider how you might modify it to give it more of a tree shape.

Here is a video that further explains pre-order tree traversal:

In-Order Tree Traversal

Post-Order Tree Traversal

Level Order Tree Traversal (Breadth First Search)

Less often used (or asked about in programming interviews) is how to traverse a tree using breadth-first searching:

Post-Order Traversal with Two Stacks (No Recursion)