Binary Tree PreOrder Traversal in Java - Recursion and Iteration Example

Unlike a linked list and array which are linear data structure and can only be traversed linearly, there are several ways to traverse a binary tree because of its hierarchical nature. The tree traversal algorithms are mainly divided into two types, the depth-first algorithms, and breadth-first algorithms. As their name suggests, in a depth-first algorithm, the tree is traversed downwards (towards the depth) before the next sibling is visited, the Pre Order, InOrder and PostOrder traversal of a binary tree is actually depth-first traversal algorithms. On the breadth-first algorithm, also known as level order traversal, the entire breadth of the tree is traversed before moving to the next level, hence it is also known as level order traversal.

There are other algorithms to traverse a binary tree as well e.g. Monte Carlo tree search, which concentrates on analyzing the most promising moves, but the pre-order, post-order, and in-order traversal are the most popular ways to traverse a binary tree in Java. They are also the most popular data structure and algorithm questions at beginner and intermediate level.

When you traverse a tree in a depth-first way, you got three choices e.g. root, left subtree and right subtree. Depending upon the order you visit these three, different tree traversal algorithm is born.

In PreOrder traversal, the root is visited first, followed by left subtree and the right subtree, hence it is also known as NLR (nod-left-right) algorithm as well.

For those, who don't know what is the meaning of traversing a binary tree? It's a process to visit all nodes of a binary tree. It is also used to search a node in the binary tree.

Coming back to the binary tree traversal algorithm, you can implement the pre-order binary tree traversal algorithm in Java either using recursion or iteration.

As I told you in the article while finding leaf nodes in a binary tree, most of the tree based algorithms can be easily implemented using recursion because a binary tree is a recursive data structure.

Though, I believe a programmer should also know how to solve a binary tree based problem with or without recursion to do well on coding interviews. Almost 9 out of 10 times, Interviewer will ask you to solve the same problem using recursion and iteration as seen earlier with Fibonacci or reverse String problems.

In this article, I'll show you how to write a program to traverse a binary tree using PreOrder traversal using both recursion and iteration in Java.

How to traverse a Binary tree in PreOrder in Java using Recursion

Since binary tree is a recursive data structure (why? because after removing a node, rest of the structure is also a binary tree like left and right binary tree, similar to linked list, which is also a recursive data structure), it's naturally a good candidate for using recursive algorithm to solve tree based problem.

Steps on PreOrder traversal algorithm

1. visit the node
2. visit the left subtree
3. visit the right subtree

You can easily implement this pre-order traversal algorithm using recursion by printing the value of the node and then recursive calling the same preOrder() method with left subtree and right subtree, as shown in the following program:

private void preOrder(TreeNode node) {
    if (node == null) {
      return;
    }
    System.out.printf("%s ", node.data);
    preOrder(node.left);
    preOrder(node.right);
  }

You can see that it's just a couple of line of code. What is most important here is the base case, from where the recursive algorithm starts to unwind. Here node == null is our base case because you have now reached the leaf node and you cannot go deeper now, it's time to backtrack and go to another path.

The recursive algorithm is also very readable because you can see that first, you print the node value then you are visiting the left subtree and finally right subtree.

Binary tree PreOrer traversal in Java without Recursion

One of the easier ways to convert a recursive algorithm to iterative one is by using the Stack data structure. If you remember, recursion implicitly uses a Stack which started to unwind when your algorithm reaches the base case.

You can use external Stack to replace that implicit stack and solve the problem without actually using recursion. This is also safer because now your code will not throw StackOverFlowError even for huge binary search trees but often they are not as concise and readable as their recursive counterpart.

 Anyway, here is the preOrder algorithm without using recursion in Java.

public void preOrderWithoutRecursion() {
    Stack<TreeNode> nodes = new Stack<>();
    nodes.push(root);

    while (!nodes.isEmpty()) {
      TreeNode current = nodes.pop();
      System.out.printf("%s ", current.data);

      if (current.right != null) {
        nodes.push(current.right);
      }
      if (current.left != null) {
        nodes.push(current.left);
      }
    }
  }

To be honest, this is code is also easy to understand but there is tricky part in the middle of the algorithm, where you have to push right sub-tree before the left subtree, which is different from the recursive algorithm. We initially push the root in the Stack to start the traversal and then use a while loop to go over Stack until its empty. In each iteration, we pop element for visiting it.

If you remember, Stack is a LIFO data structure, since we want to visit the tree in order of node-left-right, we push right node first and left node afterward, so that in the next iteration when we pop() from Stack we get the left sub-tree.

This way a binary tree is traversed in the PreOrder traversal. If you change the order of insertion into the stack, the tree will be traversed in the post-order traversal. See  Introduction to Algorithms by Thomas S. Cormen to learn more about Stack data structure and its role in converting recursive algorithm to an iterative one.

Here is a nice diagram which shows pre-order traversal along with in-order and post-order traversal. Follow the blue line to traverse a binary tree in pre-order.

Java Program to traverse a Binary tree in PreOrder Algorithm

Here is our complete program to traverse a given binary tree in PreOrder. In this program, you will find an implementation of both recursive and iterative pre-order traversal algorithm. You can run this program from the command line or Eclipse IDE to test and get a feel of how tree traversal works.

This program has a class called BinaryTree which represents a BinaryTree, remember it's not a binary search tree because TreeNode doesn't implement Comparable or Comparator interface. The TreeNode class represents a node in the binary tree, it contains a data part and two references to left and right children.

I have created a preOrder() method in the BinaryTree class to traverse the tree in pre-order. This is a public method but actual work is done by another private method which is an overloaded version of this method.

The method accepts a TreeNode. Similarly, there is another method called preOrderWithoutRecursion() to implement the iterative pre-order traversal of the binary tree.

import java.util.Stack;

/*
 * Java Program to traverse a binary tree using PreOrder traversal. 
 * In PreOrder the node value is printed first, followed by visit
 * to left and right subtree. 
 * input:
 *     1
 *    / \
 *   2   5
 *  / \   \
 * 3   4   6
 * 
 * output: 1 2 3 4 5 6 
 */
public class PreOrderTraversal {

  public static void main(String[] args) throws Exception {

    // construct the binary tree given in question
    BinaryTree bt = new BinaryTree();
    BinaryTree.TreeNode root = new BinaryTree.TreeNode("1");
    bt.root = root;
    bt.root.left = new BinaryTree.TreeNode("2");
    bt.root.left.left = new BinaryTree.TreeNode("3");

    bt.root.left.right = new BinaryTree.TreeNode("4");
    bt.root.right = new BinaryTree.TreeNode("5");
    bt.root.right.right = new BinaryTree.TreeNode("6");

    // printing nodes in recursive preOrder traversal algorithm
    bt.preOrder();

    System.out.println();

    // traversing binary tree in PreOrder without using recursion
    bt.preOrderWithoutRecursion();

  }

}

class BinaryTree {
  static class TreeNode {
    String data;
    TreeNode left, right;

    TreeNode(String value) {
      this.data = value;
      left = right = null;
    }

    boolean isLeaf() {
      return left == null ? right == null : false;
    }

  }

  // root of binary tree
  TreeNode root;

  /**
   * Java method to print tree nodes in PreOrder traversal
   */
  public void preOrder() {
    preOrder(root);
  }

  /**
   * traverse the binary tree in PreOrder
   * 
   * @param node
   *          - starting node, root
   */
  private void preOrder(TreeNode node) {
    if (node == null) {
      return;
    }
    System.out.printf("%s ", node.data);
    preOrder(node.left);
    preOrder(node.right);
  }

  /**
   * Java method to visit tree nodes in PreOrder traversal without recursion.
   */
  public void preOrderWithoutRecursion() {
    Stack<TreeNode> nodes = new Stack<>();
    nodes.push(root);

    while (!nodes.isEmpty()) {
      TreeNode current = nodes.pop();
      System.out.printf("%s ", current.data);

      if (current.right != null) {
        nodes.push(current.right);
      }
      if (current.left != null) {
        nodes.push(current.left);
      }
    }
  }

}

Output
1 2 3 4 5 6 
1 2 3 4 5 6 

That's all about how to traverse a binary tree in PreOrder in Java. We have seen how to implement a pre-order traversing algorithm using both recursion and iteration e.g. by using a Stack data structure.

As a Computer Engineer or Programmer, you should know the basic tree traversal algorithms e.g. pre-order, in order and postorder traversals. It becomes even more important when you are preparing for coding interviews.

Anyway, just remember that in PreOrder traversal, node value is printed before visiting left and right subtree. It's also a depth-first traversal algorithm and order of traversal is node-left-right, hence it is also known NLR algorithm.

If you want to improve this program and practice your Java skill then try to implement a binary tree using Generic so that you can store String or Integer as data into the binary tree. 

Other Binary Tree Tutorials and Interview Questions

If you like this article and would like to try out a couple of more challenging programming exercise, then take a look at following programming questions from various Interviews :

• How to implement a binary search tree in Java? (solution)
• 5 Books to Learn Data Structure and Algorithms in depth (books) 
• How to print all leaf nodes of a binary tree in Java? (solution)
• 50+ Data Structure and Algorithms Problems from Interviews (list)
• How to implement a recursive preorder algorithm in Java? (solution)
• Post order binary tree traversal without recursion (solution)
• Recursive Post Order traversal Algorithm (solution)
• How to print leaf nodes of a binary tree without recursion? (solution)
• Recursive InOrder traversal Algorithm (solution)
• Iterative PreOrder traversal in a binary tree (solution)
• How to count the number of leaf nodes in a given binary tree in Java? (solution)
• 100+ Data Structure Coding Problems from Interviews (questions)
• 75+ Coding Interview Questions for Programmers (questions)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)