Inorder Traversal of Binary Tree - Recursive

In the previous tutorial, we have seen preorder traversal of a binary tree with the help of recursion. Now, in this tutorial we will see inorder traversal of a binary tree. In this, firstly, left of the tree is visited then root is printed and then right of tree is visited same applies for subtree. Inorder traversal also uses DFS(depth-first-search) approach to traverse the whole tree.
Inorder Traversal: Left Root Right.
Let us take an example.

The Inorder Traversal of above given Binary Tree will be: 6, 5, 7, 2, 20, 10, 30

Explanation:

1. If we encounter any node which is null we will return back (this will be the base condition)
2. Recur to the left subtree using node.left
3. Print the node value
4. Then recur to the right subtree using node.right
The same process gets repeated until whole tree is traversed.

Algorithm:

1. if (node == null) return
2. visit the left subtree.
3. print the node.
4. visit the right subtree.

Recursive code of Inorder Traversal is implemented below:

• Java

public class Inorder {

    public static class Node {

        int val;

        Node left, right;

        // Constructor

        Node(int val) {

            this.val = val;

            left = right = null;

        }

    }

    public static void main(String[] args) {

        /*

         * Creating Binary Tree The created binary tree is same as in the above given

         * figure (refer figure for reference)

         */

        Node root = new Node(2);

        root.left = new Node(5);

        root.right = new Node(10);

        root.left.left = new Node(6);

        root.left.right = new Node(7);

        root.right.left = new Node(20);

        root.right.right = new Node(30);

        // calling inorder method

        System.out.print("Inorder Traversal is: ");

        inorder(root);

    }

    public static void inorder(Node node) {

        if (node == null)

            return;

        // recur to the left subtree

        inorder(node.left);

        // Printing the node

        System.out.print(node.val + " ");

        // recur to the right subtree

        inorder(node.right);

    }

}

Output:

Inorder Traversal is: 6 5 7 2 20 10 30

Complexity Analysis:

Time Complexity: O(n), where n is number of nodes in tree. This is because, we are traversing the each node of tree at once.

Space Complexity: We have not used any extra space for storing the nodes values, so O(1) can be considered as space complexity.

---

Also See:

1. Preorder Traversal using Recursion.
2. Postorder Traversal using Recursion.