Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def inorderTraversal(self, root):
        result = []
        stack = []
        current = root
        while current or stack:
            while current:
                stack.append(current)
                current = current.left
            current = stack.pop()
            result.append(current.val)
            current = current.right
        return result
      

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> stk;
        TreeNode* current = root;
        while (current || !stk.empty()) {
            while (current) {
                stk.push(current);
                current = current->left;
            }
            current = stk.top();
            stk.pop();
            result.push_back(current->val);
            current = current->right;
        }
        return result;
    }
};
      

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
import java.util.*;

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.val);
            current = current.right;
        }
        return result;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    const result = [];
    const stack = [];
    let current = root;
    while (current || stack.length) {
        while (current) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.push(current.val);
        current = current.right;
    }
    return result;
};
      

Problem Description

Given the root of a binary tree, return the inorder traversal of its nodes' values as a list. In an inorder traversal, you visit the left subtree first, then the root node, and finally the right subtree. The binary tree can have any structure (not necessarily a binary search tree).

• There is only one valid inorder traversal for a given tree structure.
• The tree nodes should not be reused or altered.
• Return a list/array of node values in the order they are visited.

Thought Process

To solve this problem, we first need to understand what an inorder traversal is. In a binary tree, inorder traversal means visiting the left subtree, then the current node, and finally the right subtree. The simplest way to do this is using recursion, but for interview settings, it's also important to know how to do it iteratively (without recursion), which uses a stack.

A brute-force approach would be to use recursion, which is straightforward but relies on the call stack. However, to avoid potential stack overflow with deep trees or to demonstrate iterative control, we can use an explicit stack. This transition from recursion to iteration is a key optimization and a common interview expectation.

The main challenge is managing the traversal order and making sure we visit each node exactly once, in the correct sequence.

Solution Approach

We will use an iterative approach with an explicit stack to simulate the recursive call stack. Here’s how the algorithm works, step by step:

1. Initialize an empty stack and a pointer current starting at the root node.
2. While current is not null or the stack is not empty:
   • Keep traversing to the left child, pushing each node onto the stack as you go. This mimics the recursive call to the left subtree.
   • When you reach a null left child, pop the last node from the stack. This node is the next in the inorder sequence.
   • Add the popped node’s value to the result list.
   • Move current to the right child of the popped node and repeat the process.
3. Continue until both the stack is empty and current is null.
4. Return the result list with all node values in inorder.

This approach ensures that each node is processed in the correct order without recursion, and every node is visited exactly once.

Example Walkthrough

Consider the following binary tree:

        1
         \
          2
         /
        3
  

The inorder traversal should return [1, 3, 2]. Here’s how the algorithm works step by step:

1. Start at root (1). Left child is null, so push 1 onto the stack and move to null.
2. Pop 1 from the stack, add 1 to result. Move to right child (2).
3. At 2, move to its left child (3), push 2 onto stack, then push 3 onto stack and move to left child (null).
4. Pop 3 from stack, add 3 to result. Move to right child (null).
5. Pop 2 from stack, add 2 to result. Move to right child (null).
6. Both stack and current are null, so traversal ends. Result is [1, 3, 2].

Time and Space Complexity

• Brute-force (Recursive) Approach:
  Time Complexity: O(n), where n is the number of nodes in the tree, since each node is visited once.
  Space Complexity: O(h), where h is the height of the tree, due to the call stack.
• Iterative Approach (with stack):
  Time Complexity: O(n), for the same reason—each node is visited exactly once.
  Space Complexity: O(h), since the stack holds at most h nodes at any time (the path from root to the current node).

Both approaches are optimal for this problem. The iterative approach avoids potential stack overflow with deep trees.

Summary

Inorder traversal is a fundamental tree operation. The iterative solution uses a stack to simulate recursion, ensuring each node is visited in the correct order. This approach is efficient, avoids recursion limits, and is easy to implement. The key insight is to process nodes by always traversing left first, then visiting the node, then traversing right—using a stack to remember where we are in the tree.