LeetCode Solution 94 - Binary Tree Inorder Traversal

Problem Statement

The problem Binary Tree Inorder Traversal is stated as follows:

Given the root of a binary tree, return its inorder traversal.

Example:

Input:

    1
     \
      2
     /
    3

Output:

[1, 3, 2]

Optimal Approach: Recursive and Iterative Traversal

The inorder traversal follows Left -> Root -> Right order.

Recursive Approach

1. Traverse the left subtree.
2. Visit the root node.
3. Traverse the right subtree.

Iterative Approach (Using Stack)

1. Use a stack to track nodes.
2. Push all left nodes until reaching NULL.
3. Pop from stack, visit node, move to the right subtree.
4. Repeat until all nodes are visited.

LeetCode-Compatible Code Implementation

Recursive Solution (C++)

class Solution {
public:
    void inorder(TreeNode* root, vector<int>& result) {
        if (!root) return;
        inorder(root->left, result);
        result.push_back(root->val);
        inorder(root->right, result);
    }
    
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        inorder(root, result);
        return result;
    }
};

Iterative Solution (C++)

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* curr = root;
        
        while (curr || !st.empty()) {
            while (curr) {
                st.push(curr);
                curr = curr->left;
            }
            curr = st.top();
            st.pop();
            result.push_back(curr->val);
            curr = curr->right;
        }
        return result;
    }
};

Step-by-Step Explanation of Code

• Recursive Approach
  • Base condition: If node is NULL, return.
  • Recur for left subtree → Add node value to result → Recur for right subtree.
• Iterative Approach
  • Use stack to track unvisited nodes.
  • Push left children onto stack until NULL is reached.
  • Pop the last node, add to result, and move to the right child.

Dry Run / Execution Steps

For tree:

    1
     \
      2
     /
    3

Step	Stack Content	Result
1	[1]	[]
2	[1, 2]	[]
3	[1, 2, 3]	[]
4	[1, 2]	[3]
5	[1]	[3, 2]
6	[]	[3, 2, 1]

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Sorting)	O(n log n)	O(n)	Requires extra sorting step
Morris Traversal	O(n)	O(1)	Modifies tree structure temporarily

Best Solution & Why It’s Best

• Iterative Approach (Stack) and Recursive Approach both have O(n) time complexity.
• Recursive approach is simpler but uses O(n) extra space for recursion.
• Iterative approach avoids recursion overhead, making it better for large trees.

Complexity Analysis

Approach	Time Complexity	Space Complexity
Recursive	O(n)	O(n) (call stack)
Iterative	O(n)	O(n) (stack)
Morris	O(n)	O(1)

Conclusion

• Iterative method using stack is widely used.
• Recursive method is simple and intuitive.
• Morris traversal is optimal for space but modifies tree temporarily.

Similar Problems for Practice

• Preorder Traversal
• Postorder Traversal
• Binary Tree Level Order Traversal