How To Create Inorder Traversal Inwards Binary Tree Without Recursion Inwards Java

This is the instant component subdivision of implementing inorder traversal of a binary tree inwards Java, inwards the first part, I accept shown you lot how to solve this occupation using recursion together with inwards this part, we'll implement inorder traversal algorithm without recursion. Now, to a greater extent than or less of you lot powerfulness argue, why purpose iteration if the recursive solution is therefore tardily to implement? Well, that's true, exactly the iterative solution is oftentimes regarded improve every bit they are non prone to StackOverFlowError. Another ground why nosotros are discussing the iterative solution hither is because of technical interviews. If you lot to expire to a programmer chore interview, you lot volition honour that Interviewer volition oftentimes inquire you lot to solve the same occupation using iteration together with recursions like Fibonacci series or String reversal algorithm. It's every bit good goodness for your learning together with developing algorithm skill, which is really of import for becoming a improve programmer.

The inwards club algorithm is really similar to the preorder traversal algorithm nosotros accept seen earlier, every bit both are the depth-first algorithm. The alone difference betwixt inorder together with preorder traversal is the club on which they see left subtree, root, together with correct subtree.

The inorder traversal commencement explores left subtree until it reaches a foliage node, from in that place it the impress value of the node together with starts exploring correct subtree of the node. The procedure continues until all nodes are visited.

One of the worth knowing affair well-nigh inorder traversal is that it prints all nodes of the tree inwards sorted club if given binary tree is binary search tree. Influenza A virus subtype H5N1 useful item to solve many binary tree-based problems.

Though these are non the alone agency to traverse the tree, you lot tin every bit good purpose breadth-first traversal algorithm similar marking club traversal (see Data Structures together with Algorithms: Deep Dive Using Java), which traverses all nodes of a marking before moving on to novel level. If you lot are preparing for Google or Amazon developer interviews, knowing every bit many algorithms every bit possible volition improve your chances.

Binary Tree InOrder traversal without Recursion

The steps for inorder traversal volition rest the same alongside recursion together with without it. The cardinal is how to purpose a Stack to convert recursive algorithm to an iterative one.

Since nosotros postulate to explore the left tree, nosotros start alongside beginning together with expire along to force nodes until nosotros achieve the foliage node that's 1 status inwards our loop. When the electrical flow becomes null we popular the node, impress its values together with start alongside correct subtree.

Here are the exact steps to implement in-order traversal inwards a binary tree without recursion

1) Start alongside electrical flow = root
2) loop, until Stack is empty or current, becomes null
3) if the electrical flow is non cipher force electrical flow into the stack together with electrical flow = current.left
4) if the electrical flow is cipher together with then popular from stack, impress the node value together with electrical flow = node.right

together with hither is the Java component subdivision to implement the higher upward steps:

public void inOrderWithoutRecursion() {         Stack<TreeNode> nodes = new Stack<>();         TreeNode electrical flow = root;          while (!nodes.isEmpty() || electrical flow != null) {              if (current != null) {                 nodes.push(current);                 electrical flow = current.left;             } else {                 TreeNode node = nodes.pop();                 System.out.printf("%s ", node.data);                 electrical flow = node.right;             }          }     }

You tin run across that the logic is really much similar to an iterative pre-order algorithm alongside the alone affair nosotros are continuing alongside left subtree first. This algorithm is slightly tougher than the recursive one, which is extremely easy.

If you lot honour coding this algorithm hard past times yourself, mayhap it's fourth dimension to refresh your cognition alongside a goodness information construction together with algorithm courses like PreOrder algorithm nosotros accept used the Stack data construction to convert the recursive algorithm to an iterative one, 1 of the of import things every programmer should remember.

We accept used the same classes BinaryTree together with TreeNode, which is used inwards before exercises. The code for inorder traversal is encapsulated inwards the inOrderWithoutRecursion() method.

import java.util.Stack;  /*  * Java Program to traverse a binary tree   * using inorder traversal without recursion.   * In InOrder traversal commencement left node is visited, followed past times beginning  * together with correct node.  *   * input:  * twoscore  * / \  * twenty l  * / \ \  * 10 thirty lx  * / / \  * v 67 78  *   * output: v 10 twenty thirty twoscore l lx 67 78   */ 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 on InOrder traversal without recursion         System.out.println("printing nodes of binary tree on InOrder                               using iteration");         bt.inOrderWithoutRecursion();     }  }  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;         }      }      // beginning of binary tree     TreeNode root;      public void inOrderWithoutRecursion() {         Stack<TreeNode> nodes = new Stack<>();         TreeNode electrical flow = root;          while (!nodes.isEmpty() || electrical flow != null) {              if (current != null) {                 nodes.push(current);                 electrical flow = current.left;             } else {                 TreeNode node = nodes.pop();                 System.out.printf("%s ", node.data);                 electrical flow = node.right;             }          }     }      /**      * Java method to do binary tree alongside examination information      *      * @return a sample binary tree for testing      */     public static BinaryTree create() {         BinaryTree tree = new BinaryTree();         TreeNode beginning = new TreeNode("40");         tree.root = root;         tree.root.left = new TreeNode("20");         tree.root.left.left = new TreeNode("10");         tree.root.left.left.left = new TreeNode("5");          tree.root.left.right = new TreeNode("30");         tree.root.right = new TreeNode("50");         tree.root.right.right = new TreeNode("60");         tree.root.right.right.left = new TreeNode("67");         tree.root.right.right.right = new TreeNode("78");          return tree;     }  }  Output printing nodes of a binary tree on InOrder using iteration v 10 twenty thirty twoscore l 67 lx 78 

That's all well-nigh how to traverse a binary tree using in-order traversal algorithm inwards Java. One of the mutual purpose of in-order traversal is to evaluate infix expressions together with impress nodes inwards sorted club of binary search tree. If you lot come upward across whatever other goodness purpose of in-order algorithm together with then delight allow us know.

Further Learning
Data Structures together with Algorithms: Deep Dive Using Java
solution)

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

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

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

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

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

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

5 Books to prepare information construction together with algorithm for programming/coding interviews (list)

How to implement a binary search tree inwards Java? (program)

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

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

5 Free Data Structure together with Algorithms Courses for Programmers (courses)

10 Algorithms Books Every Programmer Should read (books)

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 together with Algorithms Problems from Interviews (questions)

10 Free Data Structure together with Algorithm Courses for Programmers (courses)

100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article therefore far. If you lot similar this binary tree tutorial together with then delight portion alongside your friends together with colleagues. If you lot accept whatever questions or feedback together with then delight drib a comment.

P. S. - If you lot are looking for to a greater extent than or less Free Algorithms courses to improve your agreement of Data Structure together with Algorithms, together with then you lot should every bit good banking concern jibe the Easy to Advanced Data Structures course of report on Udemy. It's authored past times a Google Software Engineer together with Algorithm proficient together with its completely complimentary of cost.