How To Implement Binary Tree Preorder Traversal Inward Coffee Without Recursion - Iterative Example

This is my mo article on how to implement binary tree pre-order traversal inwards Java. In the first part, I accept shown how to traverse a binary tree alongside a pre-order traversal algorithm using Recursion, too inwards this article, y'all volition larn how to implement pre-order traversal without using Recursion. You mightiness endure thinking that why exercise y'all demand to larn the iterative solution if a recursive solution is possible too slow to write? Well, this type of inquiry is generally asked on Programming Job interviews too Interviewers similar to consider how comfortable a candidate is alongside both Recursion equally good equally using other data structures too iteration.

Apart from that, Iterative solution is likewise oftentimes preferred inwards existent code because Recursive solution tin ever come across StackOverflow fault when a disclose of nodes increase too Recursion gets deeper too deeper.  That's why an iterative solution is considered prophylactic too if possible y'all should ever purpose that for your production code.

Just to revise, pre-order is a depth-first algorithm, where the depth of the tree is commencement explored earlier traversing sibling. In preOrder traversal, first, node or origin is visited, too so left subtree, too correct subtree, therefore it is likewise known equally NLR (Node-Left-Right) algorithm.

You mightiness know that when y'all purpose Recursion, methods calls are stored inwards an internal Stack which unwinds itself when the algorithm reaches the base of operations case.

When recursion is non allowed, y'all tin purpose the Stack information construction to exercise the same effect, inwards fact, this is likewise a mutual technique to convert a recursive algorithm into an iterative one.

Btw, if y'all are non familiar alongside essential information construction similar Stack, Queue, Array, LinkedList, Binary tree too Hash tabular array then  I propose y'all bring together a goodness class like Data Structures too Algorithms: Deep Dive Using Java on Udemy, it's 1 of the best class to larn too original information construction too Algorithms. Even if y'all know information structure, this tin endure used to farther strengthen your knowledge.

Pre-order traversal inwards Java without recursion

There is no dubiety that the recursive algorithm of pre-order traversal was readable, clear, too concise. You should ever prefer such algorithm over iterative one, precisely if y'all accept been asked to solve this employment without recursion too so y'all accept no choice. In lodge to convert that recursive algorithm to an iterative one, y'all tin purpose a Stack.

You start traversal past times pushing the origin node into Stack too loop until Stack is empty. In each iteration, y'all popular the terminal chemical component from Stack too impress its value. That way y'all visited it. Now, force the left too correct nodes into Stack if they are non null.

The lodge on which y'all force the left too correct node is critical. You must commencement 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 y'all telephone telephone pop() it volition provide left node because Stack is a LIFO information structure, to larn to a greater extent than near Stack, y'all tin bring together a comprehensive class on information structures too algorithms like binary tree tutorial.

The BinaryTree shape is your binary tree too 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 shape itself. This way, y'all don't demand to exercise a novel tree every fourth dimension inwards the main() method.

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

Java, Python, too JavaScript. 

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 too 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;     }    }    // origin 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 alongside exam information    *     * @return a sample binary tree for testing    */   public static BinaryTree create() {     BinaryTree tree = new BinaryTree();     TreeNode origin = 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 near how to traverse a binary tree using PreOrder traversal inwards Java. The lodge inwards which y'all see the node left too correct subtree is telephone commutation because that lodge determines your traversal algorithm. If y'all see the node commencement way it preOrder, if y'all see the node mo way its InOrder too when y'all see the node terminal too so its called postOrder traversal.

Further Learning
Data Structures too Algorithms: Deep Dive Using Java
program)

How to implement in-order traversal inwards Java? (solution)

How to implement in-order traversal inwards Java without recursion? (solution)

How to implement pre-order traversal inwards Java?  (solution)

5 Free Data Structure too Algorithms Courses for Programmers (courses)

10 Algorithms Books Every Programmer Should read (books)

How to implement a linked listing using generics inwards Java? (solution)

How to traverse a binary tree inwards pre-order without using recursion? (solution)

5 information construction too algorithm books for coding interviews (list)

How to impress duplicate elements of an array inwards Java? (solution)

How to contrary an array inwards house inwards Java? (solution)

How to contrary a singly linked listing inwards Java? (solution)

50+ Data Structure too Algorithms Problems from Interviews (questions)

How to honour the middle chemical component of the linked listing using a unmarried pass? (solution)

How to honour the third chemical component from the cease of a linked listing inwards Java? (solution)

10 Free Data Structure too Algorithm Courses for Programmers (courses)

100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article so far. If y'all similar this Java Array tutorial too so delight part alongside your friends too colleagues. If y'all accept whatsoever questions or feedback too so delight driblet a comment.

P. S. - If y'all are looking for around Free Algorithms courses to better your agreement of Data Structure too Algorithms, too so y'all should likewise banking concern tally the Easy to Advanced Data Structures class on Udemy. It's authored past times a Google Software Engineer too Algorithm proficient too its completely complimentary of cost.