Iterative Binary Tree PreOrder Traversal in Java - Without Recursion

This is the second article on binary tree pre-order traversal in Java. In the first part, I have shown you how to traverse a binary tree with pre-order traversal using recursion, and in this article, you will learn how to implement pre-order traversal without using recursion. Just to revise, pre-order is a depth-first algorithm, where the depth of the tree is first explored before traversing sibling. 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 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.



Pre-order traversal in Java without recursion

There is no doubt that recursive algorithm of pre-order traversal was readable, clear, and concise. You should always prefer such algorithm over 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 on which you push the left and right node are critical. You must first push right subtree followed by left subtree because in pre-order we visit left subtree after the node. In next iteration when you call pop() it will return left node because Stack is a LIFO data structure, to learn more about Stack, you can read any good book on data structures and algorithms e.g. Introduction to Algorithms by Thomas S. Cormen.

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 step 4 to 6 again.

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 right node before left node so that our program can process left node before right node as required by the pre-order algorithm. By the way, if you are learning binary tree from interview perspective, you can check out The Algorithm Design Manual for more tree based problems.

Iterative Binary Tree PreOrder Traversal in Java




Java Program to traverse 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 root node by pushing that into Stack. We have used the same class which is used in 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 main() method.

Here is a diagram of iterative pre-order traversal algorithm which will make the steps clearer:

pre order traversal without recursion in Java


Iterative Pre-Order Traversal of Binary Tree in Java
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 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 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 you traversal algorithm. If you visit the node first means it preOrder, if you visit the node second means its InOrder and when you visit the node last then its called postOrder traversal.

Other data structure and algorithm tutorials you may like
  • How to implement linked list in Java using Generics? (solution)
  • How to implement binary search tree in Java? (solution)
  • How to reverse a linked list in Java? (solution)
  • How to find Nth node from the end in a singly linked list in Java? (answer)
  • How to reverse an array in place in Java? (solution)
  • How to remove duplicate characters from String in Java? (solution)
  • How to find duplicates from an array in Java? (solution)
  • How to check if a linked list contains cycle in Java? (solution)


1 comment:

  1. can you show inorder and postorder as well?

    ReplyDelete