Easy

Binary Tree Inorder Traversal

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.

Examples

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

Output:[1,3,2]

Explanation:Node 1 has no left child so it comes first, then the right subtree yields 3 before 2.

Input:root = []

Output:[]

Explanation:An empty tree yields no values.

Input:root = [1]

Output:[1]

Explanation:A lone node is visited by itself.

Constraints

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

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 skewed chain exercises only one side at each step, which both methods handle without extra logic.

Common Mistakes

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.
Finding the wrong predecessor by stopping at any right child instead of the rightmost one lacking a thread.

Pattern Takeaway

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

Related Problems

Validate Binary Search Tree Kth Smallest Element in a BST Binary Tree Level Order 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].

Dry Run

Visit	Action	`result`
1	left is null, record 1	[1]
2	go left to 3	[1]
3	no left, record 3	[1, 3]
3	no right, return to 2	[1, 3]
2	record 2, right is null	[1, 3, 2]

Complexity Analysis

Time Complexity

$O(n)$

Space Complexity

$O(n)$

Every node is visited once, and a skewed tree nests one call frame per node.

Solution.java

1class Solution {2    public List<Integer> inorderTraversal(TreeNode root) {3        List<Integer> result = new ArrayList<>();4        helper(root, result);5        return result;6    }7
8    private void helper(TreeNode node, List<Integer> result) {9        if (node == null) return;10        helper(node.left, result);11        result.add(node.val);12        helper(node.right, result);13    }14}