Recursive Inorder Traversal of a Binary Tree

1. Introduction

Inorder traversal is a type of depth-first traversal used in binary trees. It follows the order:

Left Subtree → Root → Right Subtree

Why Use Inorder Traversal?

In a Binary Search Tree (BST), inorder traversal retrieves nodes in sorted ascending order.
It’s a standard method to explore or evaluate binary trees recursively.

2. Example

Inorder Traversal Output for This Tree

Order: 4 2 5 1 3

3. Pseudocode

function inorder(node):
    if node is NULL:
        return
    inorder(node.left)
    visit(node)
    inorder(node.right)

4. Java Implementation

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.val = value;
        this.left = null;
        this.right = null;
    }
}

public class InorderTraversal {

    public void inorder(TreeNode node) {
        if (node == null) {
            return;
        }

        // Step 1: Recur on left child
        inorder(node.left);

        // Step 2: Visit node
        System.out.print(node.val + " ");

        // Step 3: Recur on right child
        inorder(node.right);
    }

    public static void main(String[] args) {
        // Build the tree: 
        //         1
        //        / \
        //       2   3
        //      / \
        //     4   5

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        InorderTraversal tree = new InorderTraversal();
        System.out.println("Inorder Traversal:");
        tree.inorder(root);
    }
}

5. Time and Space Complexity

Time Complexity:

Each node is visited once → O(n), where n is the number of nodes.

Space Complexity:

O(h) where h is the height of the tree (because of recursion stack).
Worst-case for skewed tree: O(n)
Best case for balanced tree: O(log n)

8. When to Use Recursive Inorder Traversal

When you need an elegant and simple solution.
When tree depth is not too large (to avoid stack overflow).
For inorder printing or evaluation of trees.
To get sorted elements from a Binary Search Tree.