Inorder Traversal Of Binary Tree Inward Coffee Using Recursion Too Iteration

This is the minute article close tree traversal algorithms using Java. In the first part, nosotros receive got seen the pre-order algorithm for visiting all nodes of the binary tree in addition to today we'll acquire close the InOrder traversal. As I told you lot before, dissimilar array in addition to linked list, binary tree has several ways of traversal. The traversal algorithms are broadly divided into depth origin in addition to breadth origin traversal algorithms depending upon how algorithm truly works. As the mention suggest, depth origin explores binary tree towards depth before visiting sibling, acre breath origin visits all nodes inward the same marking before going to side past times side level, therefore it is equally good known equally marking gild traversal. Both PreOrder in addition to InOrder tree traversal algorithms are depth origin in addition to the alone deviation betwixt pre-order in addition to in-order algorithm is the gild on which root, left node, in addition to correct node of the binary tree is visited.

The In gild traversal algorithm origin visits the left node, followed past times root in addition to finally correct node. This is different than pre-order traversal which visits the root first. One of the of import belongings of inorder traversal is that it prints the nodes inward sorted gild if given binary tree is a binary search tree.

Remember, a binary tree is called a binary search tree if all nodes inward left subtree are lower than root in addition to all nodes inward correct subtree is greater than root. To acquire to a greater extent than close the binary search tree, I advise you lot read a proficient mass on Data construction in addition to algorithms e.g. Introduction to Algorithms past times Thomas H. Cormen.


In our example, I receive got equally good used a binary search tree to demonstrate that InOrder tree traversal prints nodes of a binary tree inward sorted order. Continuing the tradition, I receive got shared both recursive in addition to iterative solution of this problem. This is extremely of import from the interview indicate of view. Even though the recursive solution is easier, takes fewer lines of code, in addition to it's to a greater extent than readable, you lot should know how to traverse a binary tree without recursion inward Java to exercise good on programming interviews.

Binary tree InOrder traversal inward Java - Recursion

If you lot receive got solved a span of binary tree problems e.g. finding all leafage nodes, in addition to then you lot know that recursion is the best agency to solve the tree based problems. Since the binary tree is a recursive information structure, recursion fits them naturally. Here are the steps to see a binary tree on InOrder:

1) see left node
2) see root
3) see correct node

To implement this algorithm, you lot tin write a method to traverse all nodes of binary tree using InOrder traversal past times next steps:

1. Write a method inOrder(TreeNode node)
2. Check if node == null, if yep in addition to then return, this is our base of operations case. 
3. Call the inOrder(node.left) to recursively see left subtree
4. Print value of the node
5. Call the inOrder(node.right) to recursively traverse the correct subtree. 

This volition impress all nodes of a binary tree equally per the In gild traversal. If a binary tree is a binary search tree, in addition to then all nodes of the tree volition live printed inward sorted order. Here is a method to implement inward gild algorithm inward Java:

private void inOrder(TreeNode node) {     if (node == null) {       return;     }      inOrder(node.left);     System.out.printf("%s ", node.data);     inOrder(node.right);   }

The method is made private because it is exposed via some other populace method inOrder() which doesn't await a parameter from the client. This is an instance of facade pattern makes method simpler for client. The recursive algorithm is unproblematic to understand, you lot move past times away deep on left subtree until you lot uncovering the leafage node. Once you lot uncovering that, the recursive stack starts to unwind in addition to it prints node information in addition to starts to explore the correct subtree. See Head First blueprint patterns to acquire to a greater extent than close facade pattern inward Java.

Here is some other instance of Inorder traversal of binary tree:

InOrder traversal of Binary tree inward Java - Iterative 

As nosotros did amongst the iterative pre-order algorithm, you lot tin purpose a Stack to convert the recursive inward gild algorithm to an iterative one. Of course, the solution without recursion is non that tardily to read simply non real hard to understand. We start amongst the root in addition to procedure until electrical current node is non or Stack is non empty. We start pushing nodes from left subtree until nosotros attain to a leafage node. At that point, nosotros pop() the lastly element, prints its value in addition to starts exploring correct subtree past times assigning current = current.right. This continues until our stack becomes empty, at that point, the tree traversal is finished in addition to all elements of the binary tree is visited.

Let's see the next binary tree using InOrder traversal using our iterative Java algorithm:

    four    / \   2   v  / \   \ 1   three   six   
public void inOrderWithoutRecursion() {     Stack 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;       }      }   }
 Output 1 2 three four v six 

Since are printing elements on inorder traversal in addition to our binary tree is a binary search tree, you lot tin come across they are printed inward sorted order. See Algorithms blueprint manual past times Steve S, Skiena to acquire to a greater extent than close different types of tree traversal algorithm e.g. marking gild traversal.

Java Program to traverse binary tree using InOrder Algorithm

Here is our consummate plan to implement inorder traversal of a binary tree inward Java. This is similar to the preOrder instance nosotros receive got seen earlier, amongst the alone deviation that root is visited minute instead of first. The recursive algorithm is straightforward simply iterative i is a petty fleck hard to understand. You must squall back that Stack is a LIFO information structure in addition to node you lot force origin volition live popped later. Since you lot involve to see node inward left-node-right order, you lot receive got to force nodes of left tree until you lot attain the leafage node. Thereafter you lot impress the value in addition to start exploring correct subtree.

We receive got used same BinaryTree in addition to TreeNode class, which is used to stand upwards for a binary tree inward before tree based problems e.g. counting leafage nodes. The BinaryTree is your regular binary tree in addition to TreeNode represents a node inward the binary tree.

import java.util.Stack;  /*  * Java Program to traverse a binary tree   * using inorder traversal without recursion.   * In InOrder traversal origin left node is visited, followed past times root  * in addition to correct node.  *   * input:  *     four  *    / \  *   2   v  *  / \   \  * 1   three   six  *   * output: 1 2 three four v six   */  public class InOrderTraversal {    public static void main(String[] args) throws Exception {      // build the binary tree given inward question     BinaryTree bt = BinaryTree.create();      // traversing binary tree using InOrder traversal using recursion     System.out         .println("printing nodes of a binary tree on InOrder using recursion");      bt.inOrder();      System.out.println(); // insert novel line      // 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;     }    }    // root of binary tree   TreeNode root;    /**    * traverse the binary tree on InOrder traversal algorithm    */   public void inOrder() {     inOrder(root);   }    private void inOrder(TreeNode node) {     if (node == null) {       return;     }      inOrder(node.left);     System.out.printf("%s ", node.data);     inOrder(node.right);   }    public void inOrderWithoutRecursion() {     Stack 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 create binary tree amongst examine information    *     * @return a sample binary tree for testing    */   public static BinaryTree create() {     BinaryTree tree = new BinaryTree();     TreeNode root = new TreeNode("4");     tree.root = root;     tree.root.left = new TreeNode("2");     tree.root.left.left = new TreeNode("1");      tree.root.left.right = new TreeNode("3");     tree.root.right = new TreeNode("5");     tree.root.right.right = new TreeNode("6");      return tree;   }  }  Output printing nodes of a binary tree on InOrder using recursion 1 2 three four v six  printing nodes of a binary tree on InOrder using iteration 1 2 three four v six 

That's all about how to see all nodes of a binary tree using InOrder traversal algorithm. As I said before, InOrder is a depth-first traversal algorithm in addition to left subtree is explored origin before visiting root in addition to correct subtree is explored last, therefore it is equally good known equally LNR (left-node-right) algorithm. There is i to a greater extent than unique belongings of inorder traversal, it prints nodes inward sorted gild if given binary tree is a binary search tree. So, you lot tin purpose this algorithm if you lot receive got to impress all nodes inward sorted gild of a BST.

Further Learning
Data Structures in addition to Algorithms: Deep Dive Using Java
algorithm)

How to uncovering GCD in addition to LCM of 2 numbers inward Java? (solution)

How to uncovering if a linked listing contains bike inward Java? (solution)

How to uncovering the third node from lastly inward a linked listing inward Java? (solution)

How to uncovering duplicate elements inward given array? (solution)

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

How to uncovering the length of linked listing inward i pass? (solution)

5 books to acquire Data construction in addition to Algorithms? (list)

References
Binary Tree information structure
Tree Traversal algorithms

Share this post