L6. Inorder Traversal of Binary Tree | C++ | Java | Code Explanation

An in-depth exploration of Binary Tree Inorder Traversal, focusing on the recursive mental model, step-by-step tree navigation, and implementation in both C++ and Java.

1. Why Do We Need Tree Traversals?

Unlike linear data structures such as arrays, linked lists, stacks, and queues—which have a single logical path from start to finish—trees are hierarchical data structures.

• The Problem: To process, search, or print every element in a binary tree, we cannot simply use a single loop. We need a systematic strategy to visit every node exactly once.
• The Solution: Tree traversals define the exact order in which nodes are visited. Inorder Traversal is one of the fundamental Depth-First Search (DFS) strategies used extensively in database indexing, expression tree evaluation, and Binary Search Trees (BSTs) where inorder traversal yields sorted data.

2. Core Mental Model: Left, Root, Right

The fundamental rule of Inorder Traversal is defined by the acronym L-R-R (Left, Root, Right).

      [Root]
      /    \
  [Left]  [Right]

For any given node during the traversal, the execution follows this strict sequence:

1. Recursively traverse its left subtree.
2. Visit (process/print) the current node (Root).
3. Recursively traverse its right subtree.

3. The Recursive Approach and Base Case

Because tree structures naturally branch out and mirror smaller versions of themselves (subtrees), recursion is the cleanest and most natural tool for implementing traversals.

The Mental Hook: "Go Deep, Print, and Come Back"

Think of a recursive function as an explorer who hugs the left wall of a cave system.

• The explorer dives as deep as possible down the left paths until hitting a dead end (a null reference).
• Upon hitting a dead end, the explorer steps back (returns), processes the node they were standing on, and then investigates the right path.

Base Case

When the traversal function encounters a node that is null (meaning we have fallen off a leaf node's child pointer), it must immediately stop and return.

// Conceptual Base Case
if (node == NULL) {
    return;
}

4. Step-by-Step Tree Walkthrough

Let's trace how the recursive stack processes a sample binary tree using Inorder Traversal.

Sample Tree Structure

          1
        /   \
       2     3
      / \   / \
     4   5 7   8
        /       \
       6         9
                  \
                   10

Execution Trace (Left -> Root -> Right)

Final Printed Output Sequence

Combining all printed node values in order of execution:

5. Implementation in C++

Here is the clean, production-ready recursive implementation of Inorder Traversal in C++.

#include <iostream>
#include <vector>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    void inorderHelper(TreeNode* root, vector<int>& result) {
        // Base case: if node is null, return
        if (root == nullptr) {
            return;
        }
        
        // 1. Traverse Left Subtree
        inorderHelper(root->left, result);
        
        // 2. Process Current Root
        result.push_back(root->val);
        
        // 3. Traverse Right Subtree
        inorderHelper(root->right, result);
    }

public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        inorderHelper(root, result);
        return result;
    }
};

6. Implementation in Java

Here is the equivalent object-oriented recursive implementation in Java.

import java.util.ArrayList;
import java.util.List;

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderHelper(root, result);
        return result;
    }
    
    private void inorderHelper(TreeNode node, List<Integer> result) {
        // Base case
        if (node == null) {
            return;
        }
        
        // 1. Traverse Left
        inorderHelper(node.left, result);
        
        // 2. Process Root
        result.add(node.val);
        
        // 3. Traverse Right
        inorderHelper(node.right, result);
    }
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Definition: Inorder Traversal follows the Left -> Root -> Right (L-R-R) pattern.
• Natural Fit for Recursion: Trees naturally exhibit recursive sub-structures, making functions call themselves effortlessly to navigate down and bubble back up.
• Base Case Importance: Always check if the node pointer is null to terminate recursion safely when hitting leaf node boundaries.
• Keep It Simple: Avoid overcomplicating tree traversal logic; map the three steps (left call, print/process, right call) directly into your recursive code structure.
• Stack Memory: Understand that recursion relies heavily on the call stack memory frames to remember where to return after finishing a subtree.
• Cross-Language Parity: The algorithm logic remains identical across languages like C++ and Java; only syntax and standard library container names (vector vs ArrayList) differ.