Binary Tree Inorder Traversal - Solution & Explanation

Problem Overview: You are given the root of a binary tree and need to return the inorder traversal of its nodes. Inorder traversal visits nodes in the order left → root → right. The result is typically stored in an array while traversing the tree.

Binary tree traversals are fundamental operations in tree problems. Inorder traversal is especially useful for binary search trees because it naturally produces values in sorted order.

Approach 1: Recursive Inorder Traversal (O(n) time, O(h) space)

The recursive solution directly mirrors the definition of inorder traversal. For each node, recursively traverse the left subtree, add the current node value to the result, then recursively traverse the right subtree. This naturally fits a Depth‑First Search pattern because you explore a path fully before backtracking.

The recursion call stack implicitly handles traversal state. Each function call processes one node and moves deeper into the tree until it reaches a null node. If the tree has n nodes, every node is visited exactly once, giving O(n) time complexity. The space complexity is O(h), where h is the tree height due to recursion stack frames. This approach is the most readable and usually the first implementation developers write when working with Depth‑First Search.

Approach 2: Iterative Inorder Traversal using Stack (O(n) time, O(h) space)

The iterative approach simulates recursion explicitly using a stack. Start from the root and repeatedly push nodes while moving to the left child. This step ensures the leftmost node is processed first. When you reach a null, pop the top node from the stack, add its value to the result, and then move to its right child.

This push-left / process / move-right pattern exactly reproduces inorder traversal without recursion. Every node is pushed and popped from the stack at most once, resulting in O(n) time complexity. The stack stores at most the nodes along the current path from root to leaf, so space usage remains O(h).

The iterative version is preferred when recursion depth could be large or when interviewers want to see your understanding of how traversal works internally. It demonstrates control over stack-based state management instead of relying on the call stack.

Recommended for interviews: Start with the recursive DFS version to show you understand the traversal rule (left → root → right). Then mention the iterative stack solution as the non-recursive alternative. Interviewers usually expect the iterative version for deeper understanding of traversal mechanics, while the recursive approach demonstrates clean problem decomposition.