Movatterモバイル変換


[0]ホーム

URL:


How to Perform Binary Tree InOrder traversal in Java using Recursion? Example Tutorial

TheInOrder traversal is one of the three popular ways to traverse a binary tree data structure, the other two being thepreOrder andpostOrder. During the in-order traversal algorithm, the left subtree is explored first, followed by root, and finally nodes on the right subtree. You start traversal from root then go to the left node, then again go to the left node until you reach a leaf node. At that point in time, you print the value of the node or mark it visited and move to the right subtree. Continuing the same algorithm until all nodes of the binary tree are visited. The InOrder traversal is also known as the left-node-right orleft-root-right traversal orLNR traversal algorithm.

Similar to thepreOrder algorithm, it is also a depth-first algorithm because it explores the depth of a binary tree before exploring siblings. Since it is one of the fundamental binary tree algorithms it's quite popular in programming interviews.

These traversal algorithms are also the basis for learning more advanced binary tree algorithms, hence every programmer should learn, understand, and know how to implement in-order and other traversal algorithms.

The easiest way to implement the inOrder traversal algorithm in Java or any programming language is by usingrecursion

Since the binary tree is a recursive data structure, recursion is the natural choice for solving a tree-based problem. TheinOrder() method in theBinaryTree class implements the logic to traverse a binary tree using recursion.

From the Interview point of view, InOrder traversal is extremely important because it also prints nodes of a binary search tree in the sorted order but only if the given tree is a binary search tree

If you remember, in BST, the value of nodes in the left subtree is lower than the root, and the values of nodes on the right subtree are higher than the root. 

The In order traversal literally means IN order i.e notes are printed in the order or sorted order.

Btw, even though these three algorithms (pre-order, in-order, and post-order) are popular binary tree traversal algorithms but they are not the only ones. You also have other breadth-first ways to traverse a binary tree e.g. level order traversal (See Data Structure and Algorithms: Deep Dive).




The Recursive algorithm to implement InOrder traversal of a Binary tree

The recursive algorithm of inorder traversal is very simple. You just need to call theinOrder() method of BinaryTree class in the order you want to visit the tree. What is most important is to include the base case, which is key to anyrecursive algorithm.

For example, in this problem, the base case is you reach the leaf node and there is no more node to explore, at that point of time recursion starts to wind down. 

Here are the exact steps to traverse the binary tree using InOrder traversal:
  1. visit left node
  2. print value of the root
  3. visit right node

and here is the sample code to implement this algorithm using recursion in Java:

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


Similar to the preOrder() method inthe last example, there is anotherinOrder() method which exposes inorder traversal to the public and calls this private method which actually performs the InOrder traversal.

This is the standard way to write a recursive method that takes input, it makes it easier for a client to call the method.

publicvoid inOrder() {    inOrder(root);}

You can see that we start with root and then recursive call theinOrder() method withnode.left, which means we are going down on the left subtree until we hitnode == null, which means the last node was a leaf node.

At this point in time, theinOrder() method will return and execute the next line, which prints thenode.data. After that it's again recursiveinOrder() call withnode.right, which will initiate the same process again.

You can also check outData Structure and Algorithms Part 1 and 2 courses on Pluralsight to learn more about algorithms and how to design your own algorithms.

inorder traversal in java using recursion




Java Program to implement InOrder traversal of a Binary tree

Here is our complete solution to the inorder traversal algorithm in Java. This program uses a recursive algorithm to print the value of all nodes of a binary tree usingInOrder traversal.

As I have told you before, during the in-order traversal value of the left subtree is printed first, followed by root and right subtree. 

If you are interested in the iterative algorithm, you can further check thistutorialof implementing in order traversal without recursion.

Btw, if you struggle to understand recursion and coming up with recursive algorithms then I also recommend you to check out the Educative platform which has interactive courses to teach you recursion. 

I also highly recommend their Grokking the Coding Interview: Patterns for Coding Questions course which teaches 15+ essential coding patterns like sliding window, fast and slow pointer, merge interval etch which can be used to solve 100+ Leetcode problems. 

import java.util.Stack;/* * Java Program to traverse a binary tree  * using inorder traversal without recursion.  * In InOrder traversal first left node is visited, followed by root * and right node. *  * input: *      40 *     /  \ *    20   50 *   / \    \ *  10  30   60 * /   /  \ * 5  67  78 *  * output: 5 10 20 30 40 50 60 67 78  */publicclassMain {publicstaticvoid main(String[] args) throws Exception {// construct the binary tree given in question    BinaryTree bt= BinaryTree.create();// traversing binary tree using InOrder traversal using recursionSystem.out        .println("printing nodes of binary tree on InOrder using recursion");    bt.inOrder();  }}classBinaryTree {staticclassTreeNode {Stringdata;    TreeNodeleft,right;    TreeNode(Stringvalue) {this.data=value;left=right=null;    }  }// root of binary tree  TreeNode root;/**   * traverse the binary tree on InOrder traversal algorithm   */publicvoid inOrder() {    inOrder(root);  }privatevoid 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 with test data   *    * @return a sample binary tree for testing   */publicstatic 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;  }}Outputprinting nodes of binary treeon InOrder using recursion5 10 20 30 67 78 40 50 60


That's all abouthow to implement inOrder traversal of a binary tree in Java using recursion. You can see the code is pretty much similar to the preOrder traversal with the only difference in the order we recursive call the method. In this case, we callinOrder(node.left) first and then print the value of the node.

It's worth remembering that in order traversal is a depth-first algorithm and prints tree node in sorted order if given binary tree is a binary search tree.

In the next part of this article, I'll share inOrder traversal without recursion, meanwhile, you can try practicing following data structure and binary tree problems.


Otherdata structure and algorithms tutorials for Java Programmers
  • 10 Algorithm books Every Programmer Should Read (list)
  • How to implement the Quicksort algorithm in Java? (solution)
  • 5 Books to learn data structure and algorithms in Java? (books)
  • Top 50 Java Programs from Coding Interviews (see here)
  • How to find the largest and smallest number in an array in Java (read here)
  • How to find two maximum numbers on an integer array in Java (check here)
  • 5 Free Data Structure and Algorithms Courses for Programmers (courses)
  • How to check if a String is a Palindrome in Java? [solution]
  • How to find the missing number in a sorted array in Java? [answer]
  • 10 Algorithms Books Every Programmer Should Read (books)
  • 10 Free Data Structure and Algorithm Courses for Programmers (courses)
  • 100+ Data Structure Coding Problems from Interviews (questions)
  • How to print the Fibonacci series in Java without using Recursion? [solution]
  • How to check if an integer is a power of two without using division or modulo operator?[hint]
  • How to find all permutations of String in Java? [solution]
  • Top 20 String coding interview questions (see here)
  • How to remove an element from the array without using a third-party library (check here)
If you have any suggestions to make this algorithm better, feel free to suggest. The interviewer loves people who come up with their own algorithms or give some touch to popular algorithms.


P. S. - If you don't mind learning from free resources then you can also take a look at my list offree data structure and algorithm courses for Java developers. It contains some free online courses from Udemy, Coursera, edX, and other resources for Java developers. 

And, now one question for you, what is your favorite data structure? array, linked list, binary tree or Hash table?  do let me know in comments. 

9 comments:

  1. to represent the tree mentioned in input tree, you need to change the code like this :
    tree.root.left.right.left = new TreeNode("67");
    tree.root.left.right.right = new TreeNode("78");

    ReplyDelete
    Replies
    1. Thanks @Sar, that was exactly the problem. I have corrected it now.

      Delete
  2. the output is wrong.

    ReplyDelete
    Replies
    1. Hi @Anonymous, thanks for pointing out, I have corrected the code to create the binary tree as per diagram in specification.

      Delete
  3. Replies
    1. Hi Vipin, I have corrected the testing code, now the tree is created as per the diagram shown in the program and also nodes are printed in pre order. If you see any issue, please comment. thanks for heads up.

      Delete
    2. you are saying that its printing the node in preOrder and in the code you have mentioned that as Inorder, it is incorrect the correct inorder traversal for the tree given on top will be : 5 10 20 67 30 78 40 50 60

      Delete
  4. Exception in thread: the method inOrder(BinaryTree.TreeNode) in the type BinaryTree is not applicable for the arguments ()

    ReplyDelete
  5. Hey java67, here are the changes to fix code and example:

    Your tree in ascii should look like this (you can reconfigure of in order):
    /*
    * input:
    * 40
    * / \
    * 20 50
    * / \ \
    * 10 30 67
    * / / \
    * 5 60 78
    *
    * output: 5 10 20 30 40 50 60 67 78
    */

    and your create method, like this:
    ...
    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("67");
    tree.root.right.right.left = new TreeNode("60");
    tree.root.right.right.right = new TreeNode("78");

    return tree;
    }
    ...

    ReplyDelete

Feel free to comment, ask questions if you have any doubt.


[8]ページ先頭

©2009-2025 Movatter.jp