Back To The Basics: The Binary Tree Traversing

In my previous post Back To The Basics: The Binary Tree Insert and Find Operations I described The Binary Tree insert and find operations. In this post I'd like to go over several common algorithms for traversing a Binary Tree. Just like the insert and find operations all of our traversal operations will use recursion.

The first three algorithms deal with returning the tree values in different orders.  For this example we'll simply be printing those values out to System.out. The first algorithm allows us to print the Binary Tree's values in pre-order. Notice that in pre-order our recursive function prints the current node before recursing down it's child nodes. Pre-order has us following the tree top down from the left side of the tree to the right.
public void traversePreOrder(Tree<T> parent) {
if(parent == null)
  return;
System.out.print(parent.data + " ");
  this.traversePreOrder(parent.left);
this.traversePreOrder(parent.right);
}

The second algorithm allows us to print the Binary Tree's values in post-order. Notice that in post-order our recursive function prints the current node after recursing down it's child nodes. Post-order has us following the tree bottom up from the left side of the tree to the right. In post-order the leaf nodes are printing before their parent nodes.
public void traversePostOrder(Tree<T> parent) { if(parent == null)     return;
this.traversePostOrder(parent.left);   this.traversePostOrder(parent.right);
System.out.print(parent.data + " "); } The third algorithm allows us to print the Binary Tree's values in-order. In-order, like it's name suggests, prints the tree from the smallest value to largest value. Notice that for in-order traversal we traverse down the left child nodes, then print the current node value, and finally traverse the right child nodes. We print the current node value after traversing the left child nodes and before traversing the right child nodes because the values on the left side of the tree are always smaller than values on the right side. This is what allows us to print the tree in-order. public void traverseInOrder(Tree<T> parent) { if(parent == null)   return;
this.traverseInOrder(parent.left); System.out.print(parent.data + " ");   this.traverseInOrder(parent.right);
} The fourth algorithm allows us to return the size of the tree. The size is determined by number of items in the tree. This is the simplest of all the traversal algorithms. We simply start with a value of 1 to account for the current node and sum the values of the left and right child nodes. The resulting value will be the number of nodes in the tree. Notice that we must check the left and the right nodes for null.
public int getSize() {
int size = 1;   if(this.left != null)
      size += this.left.getSize();
if(this.right != null)     size += this.right.getSize();
return size; } The fifth algorithm allows us to return the max depth of the tree. The max depth of the tree is really just the height of the tree. The way the max depth is determined is by getting the depth of the left side of the tree and the right side and comparing them. For this algorithm, like the getSize one, we start with a value of 1 to account for the depth of the current level of the tree. public int maxDepth() { int depth = 1;   int leftDepth = (this.left == null) ? 0 : this.left.maxDepth();
int rightDepth = (this.right == null) ? 0 : this.right.maxDepth();   int childDepth = (leftDepth > rightDepth) ? leftDepth : rightDepth;
return depth + childDepth; } The sixth algorithm allows us to return the minimum value in the tree. Unlike the previous 5 algorithms we do not traverse through every node in the tree to find this value. The minimum value in the tree is contained in the left most leaf node. So to find this value we simply need to travel down the left side of the tree until we no longer have any child nodes.
public T minValue() { if(this.left != null)     return this.left.minValue();
return this.data; } Finally, the seventh algorithm allows us to return the maximum value in the tree. This algorithm is just like finding the minimum value except this time we use the right side of the tree. To find the maximum value we simply need to travel down the right side of the tree until we no longer have any child nodes.
public T maxValue() { if(this.right != null)     return this.right.maxValue();
return this.data; }