Binary Tree PreOrder Traversal in Java - Recursion and Iteration Example

Datetime:2016-08-23 01:19:27          Topic: Java           Share

Unlike linked list and array which can only be traversed linearly, there are several ways to traverse a binary tree. The tree traversal algorithms are mainly divided into two parts, depth first and breadth first . As their name suggests, in depth first, the tree is traversed downwards (towards the depth) before the next sibling is visited, the PreOrder , InOrder and PostOrder traversal of a binary tree are actually depth-first traversals. On the breadth first, the entire breadth of the tree is traversed before moving to 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 then right subtree, hence it is also known as NLR (nod-left-right) algorithm as well.

For those, who doesn't know what is 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. I also suggest you read a good book on Data structure and algorithm e.g. Introduction to Algorithms to learn more about a binary tree and various tree algorithms. They are extremely important from the programming interview point of view.

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 the 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 withFibonacci orreverse 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 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 e.g. left and right binary tree, similar tolinked 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 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 ourbase 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. I also suggest to read, Algorithms 4th Edition by Robert Sedgewick to learn more bout recursion algorithms in Java.

Binary tree PreOrer traversal in Java without Recursion

One of the easier ways to convert a recursive algorithm to iterative one is by using 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 hugebinary 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 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 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 thecommand line orEclipse 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 implementComparable orComparator interface. The TreNode class represent 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 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 post order traversals. It becomes even more important when you are preparing forcoding 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.

P.S. - 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 data structure and algorithm tutorials for Java Programmers

  • How to implement linked list using generics in Java? ( solution )
  • What is the difference between an array and linked list data structure? (answer)
  • How to find if a linked list contains cycle in Java? (solution)
  • How to find duplicate elements in given array? (solution)
  • How to reverse an array in place in Java? ( solution )
  • How to find the length of linked list in one pass? (solution)
  • 5 books to learn Data structure and Algorithms? (list)




About List