LeetCode 94: Binary Tree Inorder Traversal

Problem Restatement

We are given the root of a binary tree.

We need to return the inorder traversal of the tree’s node values.

Inorder traversal means:

left subtree
current node
right subtree

The official constraints say the number of nodes is between 0 and 100, and each node value is between -100 and 100. The follow-up asks for an iterative solution.

Input and Output

Function shape:

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        ...

Examples

Example 1:

root = [1, None, 2, 3]

Tree shape:

    1
     \
      2
     /
    3

Inorder traversal:

left of 1 -> none
visit 1
right of 1 -> node 2
left of 2 -> node 3
visit 3
visit 2

Answer:

[1, 3, 2]

Example 2:

root = []

There are no nodes.

Answer:

[]

Example 3:

root = [1]

Only one node exists.

Answer:

[1]

First Thought: Recursive DFS

Inorder traversal is naturally recursive.

For each node:

1. Traverse the left child.
2. Add the current node value.
3. Traverse the right child.

This directly follows the definition.

Algorithm

Create an empty result list:

ans = []

Define a helper:

dfs(node)

Inside the helper:

1. If node is None, return.
2. Traverse node.left.
3. Append node.val.
4. Traverse node.right.

Return ans.

Correctness

For any node, inorder traversal requires that every node in its left subtree appears before the node itself, and every node in its right subtree appears after the node itself.

The recursive helper does exactly this.

It first applies the same rule to the left subtree, then records the current node, then applies the same rule to the right subtree.

The base case handles an empty subtree by adding nothing.

Therefore, every node is visited once in inorder order.

Complexity

Let:

n = number of nodes
h = height of the tree

In the worst case, h = n for a skewed tree.

In a balanced tree, h = log n.

Recursive Implementation

# 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]:
        ans = []

        def dfs(node: Optional[TreeNode]) -> None:
            if node is None:
                return

            dfs(node.left)
            ans.append(node.val)
            dfs(node.right)

        dfs(root)
        return ans

Iterative Stack Implementation

The follow-up asks for an iterative solution.

The recursive call stack can be replaced with an explicit stack.

The idea is:

1. Keep going left and push nodes into the stack.
2. When there is no more left child, pop one node.
3. Visit that node.
4. Move to its right child.

Iterative Algorithm

Start with:

stack = []
cur = root

While cur exists or stack is not empty:

1. While cur exists, push it and move left.
2. Pop the top node.
3. Append its value.
4. Move to its right child.

Iterative Implementation

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        ans = []
        stack = []
        cur = root

        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left

            cur = stack.pop()
            ans.append(cur.val)
            cur = cur.right

        return ans

Code Explanation

The inner loop:

while cur:
    stack.append(cur)
    cur = cur.left

pushes the current node and all left ancestors.

When it stops, there is no more left subtree to process.

Then:

cur = stack.pop()
ans.append(cur.val)

visits the nearest unvisited node.

Finally:

cur = cur.right

moves into the right subtree.

This exactly simulates recursive inorder traversal.

Testing

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    root = TreeNode(1)
    root.right = TreeNode(2)
    root.right.left = TreeNode(3)
    assert s.inorderTraversal(root) == [1, 3, 2]

    assert s.inorderTraversal(None) == []

    root = TreeNode(1)
    assert s.inorderTraversal(root) == [1]

    root = TreeNode(2, TreeNode(1), TreeNode(3))
    assert s.inorderTraversal(root) == [1, 2, 3]

    root = TreeNode(1, TreeNode(2, TreeNode(3)))
    assert s.inorderTraversal(root) == [3, 2, 1]

    print("all tests passed")

run_tests()

Test meaning: