InOrder traversal inward binary tree without recursion inward Java

This is the instant constituent of implementing inorder traversal of a binary tree inward Java, inward the first part, I bring shown you lot how to solve this employment using recursion together with inward this part, we'll implement inorder traversal algorithm without recursion. Now, only about of you lot mightiness argue, why role iteration if the recursive solution is hence slow to implement? Well, that's true, but the iterative solution is oft regarded improve equally they are non prone to StackOverFlowError. Another ground why nosotros are discussing iterative solution hither is because of technical interviews. If you lot to transcend away to a programmer chore interview, you lot volition notice that Interviewer volition oft inquire you lot to solve the same employment using iteration together with recursion e.g. Fibonacci series or String reversal algorithm. It's equally good practiced for your learning together with developing algorithm skill, which is really of import for becoming a improve programmer.

The inward gild algorithm is really similar to the preorder traversal algorithm nosotros bring seen earlier, equally both are the depth-first algorithm. The solely difference betwixt inorder together with preorder traversal is the gild on which they see left subtree, root, together with correct subtree. The inorder traversal start explores left subtree until it reaches a foliage node, from their it 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 matter nearly inorder traversal is that it prints all nodes of the tree inward sorted gild if given binary tree is binary search tree. Influenza A virus subtype H5N1 useful exceptional to solve many tree based problems.

Though these are non the solely means to traverse the tree, you lot tin equally good role breadth-first traversal algorithm e.g. degree gild traversal (see Introduction to Algorithms), which traverses all nodes of a degree before moving on to novel level. If you lot are preparing for Google or Amazon developer interviews, knowing equally many algorithms equally possible volition improve your chances.

Binary Tree InOrder traversal without Recursion

The steps for inorder traversal volition stay same amongst recursion together with without it. The fundamental is how to role a Stack to convert recursive algorithm to an iterative one. Since nosotros take away to explore left tree, nosotros start amongst source together with proceed to force nodes until nosotros attain the foliage node that's i status inward our loop. When electrical current becomes null we popular the node, impress its values together with start amongst correct subtree. Here are the exact steps

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

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

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

You tin run into that the logic is really much similar to an iterative pre-order algorithm amongst the solely matter nosotros are continuing amongst left subtree first. This algorithm is slightly tougher than recursive one, which is extremely easy. If you lot notice coding this algorithm hard yesteryear yourself, perchance it's fourth dimension to refresh your noesis amongst a practiced information construction together with algorithm mass similar Algorithm Design manual.

This is the instant constituent of implementing inorder traversal of a binary tree inward Java InOrder traversal inward binary tree without recursion inward Java

Java Program to traverse binary tree using InOrder algorithm

Here is our consummate Java plan to implement iterative inorder traversal inward Java. Similar to the iterative PreOrder algorithm nosotros bring used Stack to convert recursive algorithm to an iterative one. We bring used same classes BinaryTree together with TreeNode, which is used inward before exercises. The code for inorder traversal is encapsulated inward the inOrderWithoutRecursion() method.

import java.util.Stack;  /*  * Java Program to traverse a binary tree   * using inorder traversal without recursion.   * In InOrder traversal start left node is visited, followed yesteryear source  * together with correct node.  *   * input:  * xl  * / \  * twenty l  * / \ \  * x thirty sixty  * / / \  * five 67 78  *   * output: five x twenty thirty xl l sixty 67 78   */ public class Main {      public static void main(String[] args) throws Exception {          // build the binary tree given inward 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;         }      }      // source of binary tree     TreeNode root;      public void inOrderWithoutRecursion() {         Stack<TreeNode> nodes = new Stack<>();         TreeNode electrical current = root;          while (!nodes.isEmpty() || electrical current != null) {              if (current != null) {                 nodes.push(current);                 electrical current = current.left;             } else {                 TreeNode node = nodes.pop();                 System.out.printf("%s ", node.data);                 electrical current = node.right;             }          }     }      /**      * Java method to do binary tree amongst bear witness information      *      * @return a sample binary tree for testing      */     public static BinaryTree create() {         BinaryTree tree = new BinaryTree();         TreeNode source = 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 five x twenty thirty xl l 67 sixty 78

That's all nearly how to traverse a binary tree using in-order traversal algorithm inward Java. One of the mutual role of in-order traversal is to evaluate infix expressions together with impress nodes inward sorted gild of binary search tree. If you lot come upward across whatever other practiced role of in-order algorithm together with hence delight allow us know.

Other Binary tree tutorials inward Java for Programmers

How to implement pre-order traversal inward Java? (solution)
How to traverse a binary tree inward pre-order without using recursion? (solution)
How to implement in-order traversal inward Java without recursion? (solution)
How to implement linked listing using generic inward Java? (solution)
How to notice the middle chemical component of linked listing using unmarried pass? (solution)
How to notice the tertiary chemical component from the terminate of linked listing inward Java? (solution)
How to contrary a singly linked listing inward Java? (solution)
5 Books to prepare information construction together with algorithm for programming/coding interviews (list)