How to implement Binary Tree PreOrder Traversal in Java without Recursion?

This is my second article on how to implement binary tree pre-order traversal in Java. In the first part, I have shown how to traverse a binary tree with a pre-order traversal algorithm using Recursion, and in this article, you will learn how to implement pre-order traversal without using Recursion. You might be thinking that why do you need to learn the iterative solution if a recursive solution is possible and easy to write? Well, this type of question is mostly asked in Programming Job interviews and Interviewers like to see how comfortable a candidate is with both Recursion as well as using other data structures and iteration.

Apart from that, an Iterative solution is also often preferred in real code because a Recursive solution can always run into StackOverflow error when the number of nodes increases and Recursion gets deeper and deeper.  That’s why an iterative solution is considered safe and if possible you should always use that for your production code.

Just to revise, pre-order is a depth-first algorithm, where the depth of the tree is first explored before traversing siblings. In preOrder traversal, first, node or root is visited, then left subtree, and right subtree, hence it is also known as NLR (Node-Left-Right) algorithm.

You might know that when you use Recursion, methods calls are stored in an internal Stack which unwinds itself when the algorithm reaches the base case.

When recursion is not allowed, you can use the Stack data structure to create the same effect, in fact, this is also a common technique to convert a recursive algorithm into an iterative one.

Btw, if you are not familiar with an essential data structure like Stack, Queue, Array, LinkedList, Binary tree and Hash table then  I suggest you join a good course like Data Structures and Algorithms: Deep Dive Using Java on Udemy, it’s one of the best course to learn and master data structure and Algorithms. Even if you know data structure, this can be used to further strengthen your knowledge.

Pre-order traversal in Java without recursion

There is no doubt that the recursive algorithm of pre-order traversal was readable, clear, and concise. You should always prefer such an algorithm over an iterative one, but if you have been asked to solve this problem without recursion then you have no choice. In order to convert that recursive algorithm to an iterative one, you can use a Stack.

You start traversal by pushing the root node into Stack and loop until Stack is empty. In each iteration, you pop the last element from Stack and print its value. That means you visited it. Now, push the left and right nodes into Stack if they are not null.

The order in which you push the left and right nodes is critical. You must first push the right subtree followed by the left subtree because in pre-order we visit the left subtree after the node.

In the next iteration when you call pop() it will return the left node because Stack is a LIFO data structure, to learn more about Stack, you can join a comprehensive course on data structures and algorithms like Algorithms and Data Structures – Part 1 and 2 on Pluralsight.

Anyway, here are the exact steps of iterative pre-order traversal in Java:

1. Create an empty stack
2. Push the root into Stack
3. Loop until Stack is empty
4. Pop the last node and print its value
5. Push right and left node if they are not null
6. Repeat from steps 4 to 6 again.

And, here is the function to implement this algorithm

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);
      }
    }
  }

You can see that we are pushing the right node before the left node so that our program can process the left node before the right node as required by the pre-order algorithm. By the way, if you are learning a binary tree from an interview perspective, you can check out Data Structures in Java: An Interview Refresher for more tree-based problems.

Java Program to traverse the binary tree using preOrder traversal

Here is our complete Java program to print binary tree nodes in the pre-order traversal. You start traversing from the root node by pushing that into Stack. We have used the same class which is used in the earlier binary tree tutorial.

The BinaryTree class is your binary tree and TreeNode is your individual nodes in the tree. This time, though I have moved the logic to create a sample binary tree inside the BinaryTree class itself. This way, you don’t need to create a new tree every time in the main() method.

If you want to learn more about Stack Data Structure, here is a diagram of the iterative pre-order traversal algorithm which will make the steps clearer:

And, if you don’t mind learning from free resources then you can also check out this list of Free Data Structure and Algorithm courses, which includes data structure courses on all major programming languages like Java, Python, and JavaScript. 

Iterative Pre-Order Traversal of Binary Tree in Java

And here is our complete code example which you can run in your favorite IDE like Eclipse or IntelliJIDEA. If you want you can also run from the command prompt if you have JAVA_HOME setup already and Java is in the path. 

import java.util.Stack;

/*
 * Java Program to traverse a binary tree 
 * using PreOrder traversal without recursion. 
 * In PreOrder the node value is printed first,
 * followed by visit to left and right subtree.
 * 
 * input:
 *     a
 *    / \
 *   b   e
 *  / \   \
 * c   d   f
 * 
 * output: a b c d e f 
 */

public class Main {

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

    // construct the binary tree given in question
    BinaryTree bt = BinaryTree.create();

    // traversing binary tree in PreOrder without using recursion
    System.out.println("printing nodes of a binary tree in preOrder
                         without 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 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);
      }
    }
  }

  /**
   * Java method to create binary tree with test data
   * 
   * @return a sample binary tree for testing
   */
  public static BinaryTree create() {
    BinaryTree tree = new BinaryTree();
    TreeNode root = new TreeNode("a");
    tree.root = root;
    tree.root.left = new TreeNode("b");
    tree.root.left.left = new TreeNode("c");

    tree.root.left.right = new TreeNode("d");
    tree.root.right = new TreeNode("e");
    tree.root.right.right = new TreeNode("f");

    return tree;
  }

}

Output
printing nodes of a binary tree in preOrder using recursion
a b c d e f 

That’s all about how to traverse a binary tree using PreOrder traversal in Java. The order in which you visit the node left and right subtree is key because that order determines your traversal algorithm. If you visit the node first means it preOrder, if you visit the node second means it’s InOrder and when you visit the node last then it’s called postOrder traversal.