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

This is the minute component of implementing inorder traversal of a binary tree inward Java, inward the first part, I convey shown yous how to solve this work using recursion together with inward this part, we'll implement inorder traversal algorithm without recursion. Now, or therefore of yous mightiness argue, why role iteration if the recursive solution is therefore slowly to implement? Well, that's true, only 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 yous to give-up the ghost to a programmer chore interview, yous volition detect that Interviewer volition oftentimes enquire yous to solve the same work using iteration together with recursions like Fibonacci series or String reversal algorithm. It's too goodness for your learning together with developing algorithm skill, which is real of import for becoming a improve programmer.

The inward guild algorithm is real similar to the preorder traversal algorithm nosotros convey seen earlier, every bit both are the depth-first algorithm. The solely difference betwixt inorder together with preorder traversal is the guild on which they see left subtree, root, together with correct subtree.

The inorder traversal starting fourth dimension explores left subtree until it reaches a leafage 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 almost inorder traversal is that it prints all nodes of the tree inward sorted guild if given binary tree is binary search tree. Influenza A virus subtype H5N1 useful special to solve many binary tree-based problems.

Though these are non the solely means to traverse the tree, yous tin too role breadth-first traversal algorithm similar degree guild traversal (see Data Structures together with Algorithms: Deep Dive Using Java), which traverses all nodes of a degree before moving on to novel level. If yous 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 amongst recursion together with without it. The cardinal is how to role a Stack to convert recursive algorithm to an iterative one.

Since nosotros postulate to explore the left tree, nosotros start amongst beginning together with give-up the ghost on to force nodes until nosotros accomplish the leafage node that's 1 status inward our loop. When the electrical current becomes null we popular the node, impress its values together with start amongst correct subtree.

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

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

together with hither is the Java business office to implement the inward a higher house 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 encounter that the logic is real much similar to an iterative pre-order algorithm amongst the solely affair nosotros are continuing amongst left subtree first. This algorithm is slightly tougher than the recursive one, which is extremely easy.

If yous detect coding this algorithm hard past times yourself, perhaps it's fourth dimension to refresh your cognition amongst a goodness information construction together with algorithm courses like PreOrder algorithm nosotros convey 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 convey used the 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 starting fourth dimension left node is visited, followed past times beginning  * together with correct node.  *   * input:  * xl  * / \  * xx fifty  * / \ \  * 10 xxx lx  * / / \  * five 67 78  *   * output: five 10 xx xxx xl fifty lx 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;         }      }      // beginning 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 exam 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 five 10 xx xxx xl fifty 67 lx 78 

That's all almost 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 guild of binary search tree. If yous come upwardly across whatsoever other goodness role of in-order algorithm together with therefore delight allow us know.

Further Learning
Data Structures together with Algorithms: Deep Dive Using 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 a linked listing using generics inward Java? (solution)

How to detect the core chemical factor of linked listing using a unmarried pass? (solution)

How to detect the tertiary chemical factor from the cease of a linked listing inward Java? (solution)

How to opposite a singly linked listing inward Java? (solution)

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

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

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

How to implement in-order traversal inward 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 inward Java? (solution)

How to opposite an array inward house inward Java? (solution)

How to opposite a singly linked listing inward 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 yous similar this binary tree tutorial together with therefore delight part amongst your friends together with colleagues. If yous convey whatsoever questions or feedback together with therefore delight drib a comment.

P. S. - If yous are looking for or therefore Free Algorithms courses to improve your agreement of Data Structure together with Algorithms, together with therefore yous should too banking firm jibe the Easy to Advanced Data Structures class on Udemy. It's authored past times a Google Software Engineer together with Algorithm proficient together with its completely complimentary of cost.

Share this post