94. Binary Tree Inorder Traversal

Problem¶

Return the inorder traversal of a binary tree: visit left subtree, then node, then right subtree.

Input: root
Output: list of node values in inorder

Example

root = [1, null, 2, null, null, 3] -> [1, 3, 2]

Key trick¶

Use an explicit stack to simulate recursion:

go left as far as possible
pop the last node
record its value
move to its right child

This avoids recursion depth issues and is the standard iterative inorder pattern.

Trap¶

Common mistakes are:

visiting nodes in preorder instead of inorder
forgetting to traverse the right subtree after popping
using a stack incorrectly and mixing node processing order
overcomplicating it by creating new TreeNode objects

Why is it interesting?¶

It tests whether you understand tree traversal order and can convert recursion into an iterative stack-based solution, which is a common interview skill.

Python solution¶

from typing import Optional
from utils import TreeNode

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        # Iterative inorder traversal:
        # 1. Walk left while pushing nodes.
        # 2. Pop, visit, then go right.
        res = []
        stack = []
        node = root

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

            node = stack.pop()
            res.append(node.val)
            node = node.right

        return res

Comment on my solution¶

Your recursive solution is correct and clean, but it is not iterative.

Your second solution works, but it is unusual and less idiomatic because it creates new TreeNode objects to mark when to visit a node; the standard stack + pointer approach is simpler and easier to explain in interviews.

## Solution
# WORKS - recursive
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        if root is None:
            return []
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)


# WORKS - iterative
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        if root is None:
            return []
        res = []
        stack = [root]

        while stack:
            node = stack.pop()
            if node.left is None and node.right is None:
                res.append(node.val)
                continue
            if node.right:
                stack.append(node.right)
            stack.append(TreeNode(node.val))
            if node.left:
                stack.append(node.left)
        return res