Difficulty: EasyTrees

Binary Tree Inorder Traversal

Problem in Plain English

Given the root of a binary tree, return the values of its nodes in inorder sequence: left subtree, then the node itself, then the right subtree.

Problem Statement

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

Inorder means visiting the left subtree first, then the node itself, then the right subtree, repeating that order at every node.

Constraints

The number of nodes is between 0 and 100, inclusive.
Each node value is between -100 and 100, inclusive; the input need not be a binary search tree.

Examples

Example 1

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

Node 1 has no left child, so append 1 before entering its right subtree. Node 2 has left child 3, which must be appended before 2. Thus the order is [1,3,2], not the level order [1,2,3].

Example 2

Input: root = []
Output: []

An empty root has neither a node to append nor subtrees to traverse. Its inorder sequence is an empty list.

Example 3

Input: root = [1]
Output: [1]

Both subtrees of the lone node are empty, so append its value exactly once and return [1].

Example 4

Input: root = [4,2,5,1,3]
Output: [1,2,3,4,5]

The left subtree contributes [1,2,3], then root 4 is appended, then the right subtree contributes [5]. Morris traversal must restore both temporary links, from 1 to 2 and from 3 to 4.

Example 5

Input: root = [2,2,1]
Output: [2,2,1]

This input is an arbitrary binary tree, not necessarily a search tree. The left leaf 2 precedes root 2 and right leaf 1; duplicate values remain separate entries and the output need not be sorted.

Intuition

Inorder describes where to place each node relative to its two subtrees: everything on its left comes before it, and everything on its right comes after it. In Example 1, node 1 has no left subtree, so it comes first; node 2 must wait for its left child 3, giving [1,3,2]. Recursion remembers that unfinished visit on the call stack. Morris traversal temporarily borrows an unused right-child link to remember the return route, then restores it.

Approaches

Recursive Traversal

Solution Details

Reveal Recursive Traversal: intuition, complexity, and code

Intuition

Recursion mirrors the definition word for word: traverse left, record the node, traverse right, with the call stack remembering where to resume. The cost is one stack frame per level of depth, which a skewed tree stretches to one per node.

Step-by-Step Logic

Enter node 1 of [1, null, 2, 3]: its left child is null, so record nothing and visit 1 itself, giving [1].
Move to the right child 2: go left first and reach node 3.
Node 3 has no left child, so record 3 ([1, 3]); it has no right child either, so return to 2.
Back at 2, record it ([1, 3, 2]); its right child is null, so return [1, 3, 2].

Why It Works

Induct on subtree size. The helper appends nothing for an empty subtree, which is its correct inorder sequence. For a nonempty subtree, the first recursive call appends precisely its left subtree sequence by induction; the next append records the root exactly once; the final call appends precisely its right subtree sequence. Concatenating those three parts is the definition of inorder. Every node belongs to exactly one recursive call, and all child links and values are read without modification.

Dry Run

Recursive Traversal: variable states at each step
Execution event	Active non-null call path	Result after event
enter helper(1)	1	[]
helper(1.left=null) returns	1	[]
append 1; enter helper(2) on the right	1 -> 2	[1]
enter helper(3) on the left of 2	1 -> 2 -> 3	[1]
helper(3.left=null) returns; append 3	1 -> 2 -> 3	[1,3]
helper(3.right=null) returns; return from 3	1 -> 2	[1,3]
append 2	1 -> 2	[1,3,2]
helper(2.right=null) returns; return from 2	1	[1,3,2]
return from 1 and return output	empty	[1,3,2]

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

For n nodes and height h, each node is appended once and each child link is traversed once, giving O(n) time. The call stack uses O(h) auxiliary space, worst-case O(n) on a chain. The returned list separately allocates O(n) values; total extra storage is O(n). No tree nodes or child links change, and result storage is local to each invocation. At the problem maximum of 100 nodes, the verified runtime defaults handle the recursion depth.

Code

Solution.java

1import java.util.ArrayList;2import java.util.List;3
4class TreeNode {5    int val;6    TreeNode left, right;7    TreeNode(int val) { this.val = val; }8}9
10class Solution {11    public List<Integer> inorderTraversal(TreeNode root) {12        List<Integer> result = new ArrayList<>();13        helper(root, result);14        return result;15    }16
17    private void helper(TreeNode node, List<Integer> result) {18        if (node == null) return;19        // The node is emitted only after its entire left subtree has finished.20        helper(node.left, result);21        result.add(node.val);22        helper(node.right, result);23    }24}

Hints

Hint 1

State the order as a mantra: left, node, right, applied at every subtree.

Hint 2

To drop the call stack, walk down the left spine yourself and climb back using saved ancestors.

Hint 3

For constant space, thread each left subtree back to its parent, then cut the thread on the second visit.

Edge Cases

An empty root returns an empty list without visiting anything.
A left-only chain is emitted from deepest leaf upward and creates one thread per nonleaf in Morris traversal.
A right-only chain is emitted root first and needs no Morris threads at all.
Duplicate and negative values do not change order; reference comparisons must distinguish equal-valued nodes.
The nested threads of Example 4 must all be removed. A second traversal should produce the same sequence from exactly the same tree.
Inorder output is sorted only when the input satisfies the binary search tree ordering rule.

Common Mistakes and Interview Tips

Recording the node before the left subtree, which produces preorder instead of inorder.
In Morris traversal, forgetting to remove a thread, which loops forever around the same subtree.
Searching for a null predecessor link without also stopping at a link to curr: the existing thread otherwise leads back into the tree and can cause a loop.
Comparing predecessor values instead of node identity breaks duplicate-valued inputs.
Calling Morris traversal constant total space: the auxiliary pointers are constant, but the returned values still occupy O(n) space.
Stopping Morris traversal early or allowing concurrent readers while threads exist can expose a cyclic temporary structure. Prefer recursion or an explicit stack when the tree must remain read-only throughout traversal.
Keeping result as an uncleared Solution field leaks values between calls; these snippets allocate result inside each entry method.

Key Takeaway

Tree orderings are just visit schedules; recursion schedules with the call stack, and threading schedules with the tree itself.