Binary Tree PreOrder Traversal in Java

Not like a linked record and array that are linear knowledge construction and may solely be traversed linearly, there are a number of methods to traverse a binary tree due to its hierarchical nature. The tree traversal algorithms are primarily divided into two varieties, the depth-first algorithms, and breadth-first algorithms. As their identify suggests, in a depth-first algorithm, the tree is traversed downwards (in direction of the depth) earlier than the subsequent sibling is visited, the Pre Order, InOrder and PostOrder traversal of a binary tree is definitely depth-first traversal algorithms. On the breadth-first algorithm, also referred to as stage order traversal, the complete breadth of the tree is traversed earlier than transferring to the subsequent stage, therefore additionally it is generally known as stage order traversal.

There are different algorithms to traverse a binary tree as properly e.g. Monte Carlo tree search, which concentrates on analyzing essentially the most promising strikes, however the pre-order, post-order, and in-order traversal are the most well-liked methods to traverse a binary tree in Java. They’re additionally the most well-liked knowledge construction and algorithm questions at newbie and intermediate stage.

Once you traverse a tree in a depth-first approach, you bought three decisions e.g. root, left subtree and proper subtree. Relying upon the order you go to these three, completely different tree traversal algorithm is born.

In PreOrder traversal, the foundation is visited first, adopted by left subtree and the best subtree, therefore additionally it is generally known as NLR (nod-left-right) algorithm as properly.

For these, who do not know what’s the that means of traversing a binary tree? It is a course of to go to all nodes of a binary tree. It is usually used to look a node within the binary tree.

Coming again to the binary tree traversal algorithm, you’ll be able to implement the pre-order binary tree traversal algorithm in Java both utilizing recursion or iteration.

As I advised you within the article whereas discovering leaf nodes in a binary tree, a lot of the tree primarily based algorithms might be simply carried out utilizing recursion as a result of a binary tree is a recursive knowledge construction.

Although, I imagine a programmer must also know the best way to clear up a binary tree primarily based downside with or with out recursion to do properly on coding interviews. Nearly 9 out of 10 instances, Interviewer will ask you to resolve the identical downside utilizing recursion and iteration as seen earlier with Fibonacci or reverse String issues.

On this article, I will present you the best way to write a program to traverse a binary tree utilizing PreOrder traversal utilizing each recursion and iteration in Java.

traverse a Binary tree in PreOrder in Java utilizing Recursion

Since binary tree is a recursive knowledge construction (why? as a result of after eradicating a node, remainder of the construction can also be a binary tree like left and proper binary tree, much like linked record, which can also be a recursive knowledge construction), it is naturally a superb candidate for utilizing recursive algorithm to resolve tree primarily based downside.

Steps on PreOrder traversal algorithm

1. go to the node
2. go to the left subtree
3. go to the best subtree

You possibly can simply implement this pre-order traversal algorithm utilizing recursion by printing the worth of the node after which recursive calling the identical preOrder() technique with left subtree and proper subtree, as proven within the following program:

non-public void preOrder(TreeNode node) {
    if (node == null) {
      return;
    }
    System.out.printf("%s ", node.knowledge);
    preOrder(node.left);
    preOrder(node.proper);
  }

You possibly can see that it is simply a few line of code. What’s most vital right here is the bottom case, from the place the recursive algorithm begins to unwind. Right here node == null is our base case as a result of you’ve now reached the leaf node and you can not go deeper now, it is time to backtrack and go to a different path.

The recursive algorithm can also be very readable as a result of you’ll be able to see that first, you print the node worth then you’re visiting the left subtree and at last proper subtree.

Binary tree PreOrer traversal in Java with out Recursion

One of many simpler methods to transform a recursive algorithm to iterative one is through the use of the Stack knowledge construction. For those who bear in mind, recursion implicitly makes use of a Stack which began to unwind when your algorithm reaches the bottom case.

You need to use exterior Stack to exchange that implicit stack and clear up the issue with out really utilizing recursion. That is additionally safer as a result of now your code is not going to throw StackOverFlowError even for big binary search timber however usually they aren’t as concise and readable as their recursive counterpart.

 Anyway, right here is the preOrder algorithm with out utilizing recursion in Java.

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

    whereas (!nodes.isEmpty()) {
      TreeNode present = nodes.pop();
      System.out.printf("%s ", present.knowledge);

      if (present.proper != null) {
        nodes.push(present.proper);
      }
      if (present.left != null) {
        nodes.push(present.left);
      }
    }
  }

To be trustworthy, that is code can also be straightforward to grasp however there’s difficult half in the course of the algorithm, the place you must push proper sub-tree earlier than the left subtree, which is completely different from the recursive algorithm. We initially push the foundation within the Stack to start out the traversal after which use some time loop to go over Stack till its empty. In every iteration, we pop factor for visiting it.

For those who bear in mind, Stack is a LIFO knowledge construction, since we need to go to the tree so as of node-left-right, we push proper node first and left node afterward, in order that within the subsequent iteration after we pop() from Stack we get the left sub-tree.

This manner a binary tree is traversed within the PreOrder traversal. For those who change the order of insertion into the stack, the tree shall be traversed within the post-order traversal. See  Introduction to Algorithms by Thomas S. Cormen to study extra about Stack knowledge construction and its position in changing recursive algorithm to an iterative one.

Here’s a good diagram which reveals pre-order traversal together with in-order and post-order traversal. Observe the blue line to traverse a binary tree in pre-order.

Java Program to traverse a Binary tree in PreOrder Algorithm

Right here is our full program to traverse a given binary tree in PreOrder. On this program, one can find an implementation of each recursive and iterative pre-order traversal algorithm. You possibly can run this program from the command line or Eclipse IDE to check and get a really feel of how tree traversal works.

This program has a category known as BinaryTree which represents a BinaryTree, bear in mind it isn’t a binary search tree as a result of TreeNode does not implement Comparable or Comparator interface. The TreeNode class represents a node within the binary tree, it incorporates a knowledge half and two references to left and proper youngsters.

I’ve created a preOrder() technique within the BinaryTree class to traverse the tree in pre-order. This can be a public technique however precise work is completed by one other non-public technique which is an overloaded model of this technique.

The tactic accepts a TreeNode. Equally, there’s one other technique known as preOrderWithoutRecursion() to implement the iterative pre-order traversal of the binary tree.

import java.util.Stack;

/*
 * Java Program to traverse a binary tree utilizing PreOrder traversal. 
 * In PreOrder the node worth is printed first, adopted by go to
 * to left and proper subtree. 
 * enter:
 *     1
 *    / 
 *   2   5
 *  /    
 * 3   4   6
 * 
 * output: 1 2 3 4 5 6 
 */
public class PreOrderTraversal {

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

    // assemble the binary tree given in query
    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.proper = new BinaryTree.TreeNode("4");
    bt.root.proper = new BinaryTree.TreeNode("5");
    bt.root.proper.proper = new BinaryTree.TreeNode("6");

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

    System.out.println();

    // traversing binary tree in PreOrder with out utilizing recursion
    bt.preOrderWithoutRecursion();

  }

}

class BinaryTree {
  static class TreeNode {
    String knowledge;
    TreeNode left, proper;

    TreeNode(String worth) {
      this.knowledge = worth;
      left = proper = null;
    }

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

  }

  // root of binary tree
  TreeNode root;

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

  /**
   * traverse the binary tree in PreOrder
   * 
   * @param node
   *          - beginning node, root
   */
  non-public void preOrder(TreeNode node) {
    if (node == null) {
      return;
    }
    System.out.printf("%s ", node.knowledge);
    preOrder(node.left);
    preOrder(node.proper);
  }

  /**
   * Java technique to go to tree nodes in PreOrder traversal with out recursion.
   */
  public void preOrderWithoutRecursion() {
    Stack<TreeNode> nodes = new Stack<>();
    nodes.push(root);

    whereas (!nodes.isEmpty()) {
      TreeNode present = nodes.pop();
      System.out.printf("%s ", present.knowledge);

      if (present.proper != null) {
        nodes.push(present.proper);
      }
      if (present.left != null) {
        nodes.push(present.left);
      }
    }
  }

}

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

That is all about the best way to traverse a binary tree in PreOrder in Java. We have now seen the best way to implement a pre-order traversing algorithm utilizing each recursion and iteration e.g. through the use of a Stack knowledge construction.

As a Laptop Engineer or Programmer, it’s best to know the essential tree traversal algorithms e.g. pre-order, so as and postorder traversals. It turns into much more vital when you find yourself making ready for coding interviews.

Anyway, simply keep in mind that in PreOrder traversal, node worth is printed earlier than visiting left and proper subtree. It is also a depth-first traversal algorithm and order of traversal is node-left-right, therefore additionally it is identified NLR algorithm.

If you wish to enhance this program and follow your Java ability then attempt to implement a binary tree utilizing Generic so to retailer String or Integer as knowledge into the binary tree.