Leetcode 94: Binary Tree Inorder Traversal

 

1. Problem Summary

You’re given the root of a binary tree and must return the inorder traversal of its node values.

• Inorder traversal definition:
  For each node, visit:

1. Left subtree

2. The node itself

3. Right subtree

• Input: root (binary tree root, may be null)

• Output: List/array of integers representing the inorder traversal.

Constraints:

• 0 <= number of nodes <= 100

• -100 <= Node.val <= 100

• Follow-up: implement iteratively, not just recursively.

2. Examples Explanation

Example 1:

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

The tree:

• 1

• right → 2

• left → 3

Inorder (Left, Node, Right):

• Left of 1 is null

• Visit 1

• Inorder of right subtree (2):

• Left of 2 is 3 → visit 3

• Visit 2

Result: [1, 3, 2].

Example 2:

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

Inorder traversal results in:
[4, 2, 6, 5, 7, 1, 3, 9, 8]
This comes from visiting each subtree in Left → Node → Right order.

Example 3:

Input: root = []
Empty tree ⇒ no nodes to visit ⇒ [].

Example 4:

Input: root = [1]
Single node; inorder is just [1].

3. Approach

Pattern:

This is a classic tree traversal problem. The standard recursive solution is straightforward. The follow-up asks for an iterative solution, typically done with a stack.

Simple (Recursive) Idea:

inorder(node):

    if node is null: return

    inorder(node.left)

    visit(node.val)

    inorder(node.right)

But recursion uses the call stack implicitly; they ask to do it iteratively.

4. Optimal Iterative Approach: Stack-based Inorder Traversal

High-Level Idea:

Use an explicit stack to simulate recursion:

1. Maintain a pointer current starting at root.

2. While current is not null, push it onto the stack and move to current.left (go as far left as possible).

3. When you reach null:

• Pop from the stack → this is the next node in inorder.

• Add its value to the result.

• Move to its right child.

4. Repeat until both the stack is empty and current is null.

This exactly mimics the recursive inorder traversal.

Key Observations:

• Inorder = “go left as deep as you can, then process nodes, then go right”.

• Stack stores the path back up the tree.

• Handles all trees within constraints; complexity is optimal.

No tricky edge cases beyond standard null checks and empty trees.

Pseudo-code:

Complexity Analysis:

Let n be the number of nodes.

• Time Complexity: O(n)
  Each node is pushed and popped at most once.

• Space Complexity:

• Stacks can hold at most the height of the tree nodes.

• Worst-case (skewed tree): O(n); best-case balanced: O(logn).

5. Java code

6. C code

7. C++ code

8. Python code

9. JavaScript code