Iterative Binary Tree PreOrder Traversal inwards Java - Without Recursion

This is the 2nd article on binary tree pre-order traversal inwards Java. In the first part, I accept shown you lot how to traverse a binary tree amongst pre-order traversal using recursion, together with inwards this article, you lot volition acquire 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 start explored before traversing sibling. In preOrder traversal, first, node or rootage is visited, so left subtree, together with correct subtree, so it is likewise known every bit NLR (Node-Left-Right) algorithm. You powerfulness know that when you lot last recursion, methods calls are stored inwards an internal Stack which unwinds itself when algorithm reaches the base of operations case. When recursion is non allowed, you lot tin last the Stack information structure to exercise the same effect, inwards fact, this is likewise a mutual technique to convert a recursive algorithm into an iterative one.

Pre-order traversal inwards Java without recursion

There is no doubtfulness that recursive algorithm of pre-order traversal was readable, clear, together with concise. You should ever prefer such algorithm over iterative one, exactly if you lot accept been asked to solve this employment without recursion so you lot accept no choice. In social club to convert that recursive algorithm to an iterative one, you lot tin last a Stack.

You start traversal past times pushing the rootage node into Stack together with loop until Stack is empty. In each iteration, you lot popular the concluding chemical component from Stack together with impress its value. That way you lot visited it. Now, force the left together with correct nodes into Stack if they are non null.

The social club on which you lot force the left together with correct node are critical. You must start force correct subtree followed past times left subtree because inwards pre-order nosotros see left subtree afterwards the node. In side past times side iteration when you lot telephone telephone pop() it volition provide left node because Stack is a LIFO information structure, to acquire to a greater extent than close Stack, you lot tin read whatsoever skillful majority on information structures together with algorithms e.g. Introduction to Algorithms past times Thomas S. Cormen.

Anyway, hither are the exact steps of iterative pre-order traversal inwards Java:

Create an empty Stack
Push the rootage into Stack
Loop until Stack is empty
Pop the concluding node together with impress its value
Push correct together with left node if they are non null
Repeat from measurement four to half dozen again.

Here is the business office to implement this algorithm

public void preOrderWithoutRecursion() {     Stack<TreeNode> nodes = new Stack<>();     nodes.push(root);      while (!nodes.isEmpty()) {       TreeNode electrical flow = 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 tin run into that nosotros are pushing correct node before left node so that our programme tin procedure left node before correct node every bit required past times the pre-order algorithm. By the way, if you lot are learning binary tree from interview perspective, you lot tin banking concern fit out The Algorithm Design Manual for to a greater extent than tree based problems.

This is the 2nd article on binary tree pre Iterative Binary Tree PreOrder Traversal inwards Java - Without Recursion

Java Program to traverse binary tree using preOrder traversal

Here is our consummate Java programme to impress binary tree nodes inwards the pre-order traversal. You start traversing from rootage node past times pushing that into Stack. We accept used the same bird which is used inwards before binary tree tutorial.

The BinaryTree bird is your binary tree together with TreeNode is your private nodes inwards the tree. This time, though I accept moved the logic to exercise a sample binary tree within the BinaryTree bird itself. This way, you lot don't demand to exercise a novel tree every fourth dimension inwards main() method.

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

Iterative Pre-Order Traversal of Binary Tree inwards 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 past times see to left together with correct 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 {      // build the binary tree given inwards question     BinaryTree bt = BinaryTree.create();      // traversing binary tree inwards PreOrder without using recursion     System.out         .println("printing nodes of a binary tree inwards 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;     }    }    // rootage of binary tree   TreeNode root;    /**    * Java method to see tree nodes inwards PreOrder traversal without recursion.    */   public void preOrderWithoutRecursion() {     Stack<TreeNode> nodes = new Stack<>();     nodes.push(root);      while (!nodes.isEmpty()) {       TreeNode electrical flow = 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 exercise binary tree amongst exam information    *     * @return a sample binary tree for testing    */   public static BinaryTree create() {     BinaryTree tree = new BinaryTree();     TreeNode rootage = 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 close how to traverse a binary tree using PreOrder traversal inwards Java. The social club inwards which you lot see the node, left together with correct subtree is telephone substitution because that social club determines you lot traversal algorithm. If you lot see the node start way it preOrder, if you lot see the node 2nd way its InOrder together with when you lot see the node concluding so its called postOrder traversal.

Further Reading
Algorithms together with Data Structures - Part 1 together with two
Java Fundamentals, Part 1 together with 2
Cracking the Coding Interview - 189 Questions together with Solutions

Other data construction together with algorithm tutorials you lot may like

How to implement linked listing inwards Java using Generics? (solution)
How to implement binary search tree inwards Java? (solution)
How to opposite a linked listing inwards Java? (solution)
How to notice Nth node from the terminate inwards a singly linked listing inwards Java? (answer)
How to opposite an array inwards house inwards Java? (solution)
How to take duplicate characters from String inwards Java? (solution)
How to notice duplicates from an array inwards Java? (solution)
How to banking concern fit if a linked listing contains bike inwards Java? (solution)