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)