How to implement Binary Tree PreOrder Traversal in Java without Recursion - Iterative Example

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 on 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, Iterative solution is also often preferred in real code because Recursive solution can always run into StackOverflow error when a number of nodes increase 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 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 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 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 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 is 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 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 step 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 binary tree from interview perspective, you can check out Data Structures in Java: An Interview Refresher 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 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.

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

pre order traversal without recursion in Java

If you want to learn more about Stack Data Structure, I once again suggest you join Data Structures and Algorithms: Deep Dive Using Java, one of the best course to learn essential Data Structure in Java.  Btw, it's not free but you can get it very cheap like sometimes under $10 during several Udemy flash sales which happens almost every month. 

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 language like Java, Python, and JavaScript



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 your 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.

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Data Structures in Java: An Interview Refresher
Cracking the Coding Interview - 189 Questions and Solutions

 Other binary tree and data structure tutorials you may like to explore
  • How to implement a binary search tree in Java? (program)
  • How to implement in-order traversal in Java? (solution)
  • How to implement in-order traversal in Java without recursion? (solution)
  • How to implement pre-order traversal in Java?  (solution)
  • 5 Free Data Structure and Algorithms Courses for Programmers (courses)
  • 10 Algorithms Books Every Programmer Should read (books)
  • How to implement a linked list using generics in Java? (solution)
  • How to traverse a binary tree in pre-order without using recursion? (solution)
  • 5 data structure and algorithm books for coding interviews (list)
  • How to print duplicate elements of an array in Java? (solution)
  • How to reverse an array in place in Java? (solution)
  • How to reverse a singly linked list in Java? (solution)
  • 50+ Data Structure and Algorithms Problems from Interviews (questions)
  • How to find the middle element of the linked list using a single pass? (solution)
  • How to find the 3rd element from the end of a linked list in Java? (solution)
  • 10 Free Data Structure and Algorithm Courses for Programmers (courses)
  • 100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article so far. If you like this Java Array tutorial then please share with your friends and colleagues. If you have any questions or feedback then please drop a comment.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the Easy to Advanced Data Structures course on Udemy. It's authored by a Google Software Engineer and Algorithm expert and its completely free of cost.

1 comment: