Printing out the information of a binary tree in ascending order is no simple task. Using the example diagram below, the first node value printed should be 9, and getting there is fairly simple. The next value is 14, then 21, then comes a big problem - how do we get back to the root node whose value is 26? This is a backtracking problem that is best solved with recursion.

As a review, assume the following class definition applies in this student outline.
public class TreeNode
{
private Object value;
private TreeNode left;
private TreeNode right;
public TreeNode(Object initValue, TreeNode initLeft,
TreeNode initRight)
{ value = initValue; left = initLeft; right = initRight;}
public Object getValue() { return value; }
public TreeNode getLeft() { return left;}
public TreeNode getRight() {return right;}
public void setValue(Object theNewValue) { value = theNewValue; }
public void setLeft(TreeNode theNewLeft) { left = theNewLeft; }
public void setRight(TreeNode theNewRight) { right = theNewRight; }
}
A tree traversal is an algorithm that visits every node in the tree. To visit a node means to process something regarding the data stored in the node. For now, visiting the node will involve printing the value object field.
An inorder tree traversal visits every node in a certain order. Each node is processed in the following sequence:
Solve left subtree inorder
Visit node
Solve right subtree inorder
Notice that visiting the node is placed between the two recursive calls.
Here is the code for the inorder
method:
void inorder (TreeNode temp)
{
if (temp != null)
{
inorder (temp.getLeft());
System.out.println(temp.getValue());
inorder (temp.getRight());
}
}
The first call of inorder
is asked to process the root node. The first step of the method is a recursive call of inorder
to process the left pointer of the root node. This recursive call to solve the left pointer will take place before the System.out.println
statement.
Solving for the node with value 14 results in another recursive call to solve the left pointer to the node having value 9. The inorder
call to process the node with value 9 in turn calls inorder
, which hits a null
. This recursive call results in nothing executed.
The recursion backtracks to the inorder processing of the node with value 9. Our first output occurs and the value 9 is printed. We recursively visit the node to the right and since nothing is there, we return to the node with value 9.
For the node with value 9, we have now done all three steps. We checked left, printed the 9, and checked right. This method call is done and we backtrack to where we left off, which is processing the node with value 14.
From here, the recursion will continue working its way through the tree. Inorder calls which are postponed are placed on the stack. When a call of inorder
is completed, the program will go to the stack (if necessary) to backtrack through the tree.