Binary Tree Inorder Traversal Inwards Coffee Using Recursion

The InOrder traversal is 1 of the iii pop ways to traverse a binary tree information structure, other 2 beingness the preOrder as well as postOrder. During the inwards enterprise traversal algorithm, left subtree is explored first, followed past times root, as well as finally nodes on correct subtree. You start traversal from root as well as then goes to left node, as well as then 1 time to a greater extent than goes to left node until yous attain a leafage node. At that indicate inwards time, yous impress the value of the node or grade it visited as well as moves to correct subtree. Continuing the same algorithm until all nodes of the binary tree are visited. The InOrder traversal is likewise known every bit left-node-right or left-root-right traversal or LNR traversal algorithm.

Similar to the preOrder algorithm, it is likewise a depth-first algorithm because it explores the depth of a binary tree earlier exploring siblings. Since it is 1 of the key binary tree algorithms it's quite pop inwards programming interviews.

These traversal algorithms are likewise the footing to larn to a greater extent than advanced binary tree algorithms, so every programmer should learn, empathize as well as know how to implement in-order as well as other traversal algorithms.

The easiest way to implement the inOrder traversal algorithm inwards Java or whatever programming linguistic communication is past times using recursion. Since the binary tree is a recursive information structure, recursion is the natural alternative for solving a tree-based problem. The inOrder() method inwards the BinaryTree cast implements the logic to traverse binary tree using recursion.

From Interview indicate of view, InOrder traversal is extremely of import because it likewise prints nodes of a binary search tree inwards the sorted order but exclusively if given tree is binary search tree. If yous remember, inwards BST, the value of nodes inwards left subtree is lower than root as well as values of nodes on correct subtree is higher than root. The In enterprise traversal literally agency IN enterprise i.e notes are printed inwards the enterprise or sorted order.

Btw, fifty-fifty though these iii algorithms (pre-order, in-order, as well as post-order) are pop binary tree traversal algorithms but they are non the exclusively ones. You likewise receive got other breadth-first ways to traverse a binary tree e.g. grade enterprise traversal (See Data Structure as well as Algorithms: Deep Dive).

The recursive algorithm to implement InOrder traversal of a Binary tree

The recursive algorithm of inorder traversal is rattling simple. You only demand to telephone weep upward the inOrder() method of BinaryTree cast inwards the enterprise yous desire to see the tree. What is most of import is to include base of operations case, which is key to whatever recursive algorithm.

For example, inwards this problem, the base of operations illustration is yous attain to the leafage node as well as in that place is no to a greater extent than node to explore, at that indicate of fourth dimension recursion starts to current of air down. Here are the exact steps to traverse binary tree using InOrder traversal:

1. visit left node
2. print value of the root
3. visit correct node

as well as hither is the sample code to implement this algorithm using recursion inwards Java:

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

Similar to preOrder() method inwards the lastly example, in that place is about other inOrder() method which exposes inorder traversal to the populace as well as calls this person method which genuinely performs the InOrder traversal.

This is the touchstone way to write a recursive method which takes input, it makes it easier for a customer to telephone weep upward the method.

public void inOrder() {     inOrder(root); }

You tin come across that nosotros start amongst root as well as and then recursive telephone weep upward the inOrder() method amongst node.left, which agency nosotros are going downwards on left subtree until nosotros hitting node == null, which agency the lastly node was a leafage node.

At this indicate inwards time, the inOrder() method volition furnish as well as execute the side past times side line, which prints the node.data. After that its 1 time to a greater extent than recursive inOrder() telephone weep upward amongst node.right, which volition initiate the same procedure again.

You tin likewise banking concern lucifer out tutorial of implementing inwards enterprise traversal without recursion.

import java.util.Stack;  /*  * Java Program to traverse a binary tree   * using inorder traversal without recursion.   * In InOrder traversal root left node is visited, followed past times root  * as well as correct node.  *   * input:  *      twoscore  *     /  \  *    twenty   50  *   / \    \  *  10  xxx   sixty  * /   /  \  * v  67  78  *   * output: v 10 twenty xxx twoscore 50 sixty 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 using InOrder traversal using recursion     System.out         .println("printing nodes of binary tree on InOrder using recursion");      bt.inOrder();   }  }  class BinaryTree {   static class TreeNode {     String data;     TreeNode left, right;      TreeNode(String value) {       this.data = value;       left = right = null;     }    }    // 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);   }    /**    * Java method to create binary tree amongst assay out information    *     * @return a sample binary tree for testing    */   public static BinaryTree create() {     BinaryTree tree = new BinaryTree();     TreeNode root = 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.left.right.left = new TreeNode("67");     tree.root.left.right.right = new TreeNode("78");      return tree;   }  }  Output printing nodes of binary tree on InOrder using recursion v 10 twenty xxx 67 78 twoscore 50 60

That's all nearly how to implement inOrder traversal of a binary tree inwards Java using recursion. You tin come across the code is pretty much similar to the preOrder traversal amongst the exclusively departure inwards the enterprise nosotros recursive telephone weep upward the method. In this case, nosotros telephone weep upward inOrder(node.left) root as well as and then impress the value of the node.

It's worth remembering that inwards enterprise traversal is a depth-first algorithm as well as prints tree node inwards sorted enterprise if given binary tree is a binary search tree.

In the side past times side business office of this article, I'll portion inOrder traversal without recursion, meanwhile, yous tin elbow grease practicing next information construction as well as binary tree problems.

Further Learning
Data Structures as well as Algorithms: Deep Dive Using Java
100+ Data Structure as well as Algorithms Questions for Programmers
75+ Programming as well as Coding Interview Questions

Other data construction as well as algorithms tutorials for Java Programmers

• 10 Algorithm books Every Programmer Should Read (list)
• How to implement Quicksort algorithm inwards Java? (solution)
• 5 Books to larn information construction as well as algorithms inwards Java? (books)
• How to implement a binary search algorithm inwards Java? (solution)
• How to abide by all pairs on integer array whose total is equal to given a number? (solution)
• How to contrary an array inwards house inwards Java? (solution)
• How to contrary a linked listing inwards Java without recursion? (solution)
• How to implement Insertion variety inwards Java? (solution)
• How to abide by the missing lay out inwards an array of 1 to 100? (solution)
• How to abide by the length of a singly linked listing inwards Java? (solution)
• 15 oftentimes asked information construction as well as algorithm Interview Questions (list)

If yous receive got whatever proposition to brand this algorithm better, experience gratis to suggest. Interviewer loves people who come upward up amongst their ain algorithm or rate about touching on to pop algorithms.

P.S. - If yous don't heed learning from gratis resources as well as then yous tin likewise receive got a await at my listing of free information construction as well as algorithm courses for Java developers.