How to Solve Binary Tree Inorder Traversal

Binary Tree Inorder Traversal is mostly about preserving inorder state while moving left, recording a node, then switching to its right subtree. The easiest answers use recursion or an explicit stack, but if the expected follow-up pushes for constant extra space, Morris traversal rewires predecessor pointers temporarily to simulate the call stack without allocating one.

Problem Statement

You are given the root of a binary tree and need to return the node values in inorder order. In this traversal, every node is processed after its entire left subtree and before its right subtree, so the result depends on correctly delaying when each value is added to the answer list.

For root = [1,null,2,3], the traversal must output [1,3,2] because node 2 cannot be recorded before its left child 3. The tree may also be empty, in which case the answer is an empty list. With up to 100 nodes, the main interview challenge is not scale but correctly tracking traversal state and avoiding skipped or duplicated visits.

Examples

Example 1

Input: root = [1,null,2,3]

Output: [1,3,2]

Example 2

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [4,2,6,5,7,1,3,9,8]

Example 3

Input: root = []

Output: []

Example details omitted.

Constraints

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Solution Approach

Recursive inorder DFS

The direct solution is a depth-first search that visits left, then current node, then right. Each recursive call naturally stores where to return after finishing a subtree, which makes inorder state tracking simple and readable. For Binary Tree Inorder Traversal, this is often the fastest way to produce a correct answer in an interview, especially on an Easy problem. The main trade-off is that the call stack is implicit, so you do not control space tightly, and very deep trees would grow stack depth even though this problem’s constraints are small.

Iterative traversal with an explicit stack

The stack version makes the same left-node-right order explicit. Start from the root, keep pushing nodes while moving left, then pop the most recent node, record its value, and move to its right child. This pattern is the safest non-recursive answer because it mirrors exactly what recursion was doing behind the scenes. The common failure mode in this problem is recording the node too early, before exhausting the left chain, or forgetting to move to the popped node’s right subtree, which silently drops values like 3 in [1,null,2,3].

Morris inorder traversal for constant extra space

If the follow-up asks for O(1) extra space, use Morris traversal. For each node with a left child, find its inorder predecessor in the left subtree. If that predecessor’s right pointer is null, temporarily point it back to the current node and move left. If it already points back, restore it, record the current value, and move right. This works because the temporary thread replaces the stack frame you would otherwise need. The important trade-off is implementation risk: a missed restoration or wrong predecessor loop causes duplicates, cycles, or a mutated tree.

Complexity Analysis

Using the provided target complexity, the intended optimized answer is Morris traversal with time complexity O(n) and space complexity O(1). Every node is visited a constant number of times while predecessor links are created and restored. Recursive and explicit-stack solutions are also O(n) time, but they use O(h) extra space instead of the provided O(1), where h is the tree height.

What Interviewers Usually Probe

• Do you know why inorder on [1,null,2,3] must delay visiting 2 until after processing 3?
• Can you explain how your traversal keeps track of where to return after finishing a left subtree?
• Will you switch from recursion or a stack to Morris traversal if constant extra space is requested?

Common Pitfalls or Variants

Common pitfalls

• Appending a node value before fully traversing its left subtree, which turns the result into preorder-like output instead of inorder.
• After popping a node from the stack, forgetting to move to its right child, which causes entire right-side segments to be skipped.
• Implementing Morris traversal without restoring predecessor.right to null, leaving threads behind and producing duplicate visits or a modified tree.

Follow-up variants

• Return the preorder traversal of the same binary tree using recursive, iterative, or Morris-style traversal changes.
• Return the postorder traversal, where the state-tracking becomes harder because the node is recorded after both subtrees.
• Implement inorder traversal iteratively without recursion, then explain how the answer changes if the interviewer requires O(1) extra space.

How GhostInterview Helps

• GhostInterview can screenshot or capture the tree input and keep the exact node layout visible while you trace left-node-right order.
• It gives an answer path and complexity explanation that distinguishes stack-based inorder from Morris traversal when O(1) space matters.
• It supports screen-share workflows or captured layers so the tree, stack state, and current pointer can stay visible together during the solve.

Topic Pages

• Stack
• Tree
• Depth-First Search
• Binary Tree

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the core pattern in Binary Tree Inorder Traversal?

The pattern is binary-tree traversal with state tracking: go as far left as possible, record the node only after returning, then move right. The challenge is preserving that delayed visit order without losing where to come back.

Why does the example root = [1,null,2,3] return [1,3,2]?

Node 1 has no left child, so it is recorded first. Then you move to 2, but inorder requires finishing 2’s left subtree before visiting 2 itself, so 3 must be added before 2.

Is recursion acceptable for this problem?

Yes. For this Easy problem, recursion is usually the cleanest first answer because inorder maps directly to left, node, right. Just be ready to mention that recursion uses call-stack space, so it does not satisfy the strict O(1) follow-up.

When should I use Morris traversal here?

Use Morris traversal when the interviewer explicitly asks for constant extra space or points to the provided O(1) space complexity. It avoids both recursion and an explicit stack by temporarily threading each node’s inorder predecessor back to the current node.

How do I know my iterative stack solution is correct?

Your stack solution is correct if every node is pushed while walking left, popped exactly once, appended immediately after pop, and followed by a move into its right subtree. Any other order usually skips nodes or records them too early.