#94

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Binary Tree Inorder Traversal

Binary Tree Inorder Traversal asks you to visit left subtree, node, then right subtree without losing position while moving through the tree.

stack tree depth first search binary tree

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

Metric	Value
Time	O(n)
Space	O(1)

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.

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.

terminal

Solution

Solution 1: Recursive Traversal

We first recursively traverse the left subtree, then visit the root node, and finally recursively traverse the right subtree.

# 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: Optional[TreeNode]) -> List[int]:
        def dfs(root):
            if root is None:
                return
            dfs(root.left)
            ans.append(root.val)
            dfs(root.right)

        ans = []
        dfs(root)
        return ans

Solution 2: Stack Implementation for Non-recursive Traversal

The non-recursive approach is as follows:

# 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: Optional[TreeNode]) -> List[int]:
        def dfs(root):
            if root is None:
                return
            dfs(root.left)
            ans.append(root.val)
            dfs(root.right)

        ans = []
        dfs(root)
        return ans

Solution 3: Morris Implementation for In-order Traversal

Morris traversal does not require a stack, so the space complexity is $O(1)$. The core idea is:

# 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: Optional[TreeNode]) -> List[int]:
        def dfs(root):
            if root is None:
                return
            dfs(root.left)
            ans.append(root.val)
            dfs(root.right)

        ans = []
        dfs(root)
        return ans

Continue Practicing

#114 flatten binary tree to linked list #144 binary tree preorder traversal #145 binary tree postorder traversal