LeetCode 94 - Binary Tree Inorder Traversal

This problem asks us to perform an inorder traversal on a binary tree and return the values of the visited nodes in the correct order. A binary tree is a hierarchical data structure where each node can have at most two children, a left child and a right child.

leetcodeeasystacktreedepth-first-searchbinary-tree

LeetCode Problem 94

Difficulty: 🟢 Easy
Topics: Stack, Tree, Depth-First Search, Binary Tree

Solution

Binary Tree Inorder Traversal

Problem Understanding

This problem asks us to perform an inorder traversal on a binary tree and return the values of the visited nodes in the correct order.

A binary tree is a hierarchical data structure where each node can have at most two children, a left child and a right child. The input root represents the root node of that tree. If the tree is empty, root will be None in Python or nil in Go.

An inorder traversal follows a very specific visiting order:

  1. Visit the left subtree
  2. Visit the current node
  3. Visit the right subtree

This ordering is important because it determines the final output sequence.

For example, consider this tree:

    1
     \
      2
     /
    3

The inorder traversal works like this:

  • Start at node 1
  • Visit its left subtree, which is empty
  • Visit node 1
  • Move to node 2
  • Visit node 2's left subtree
  • Visit node 3
  • Return to node 2
  • Visit node 2

Final result:

[1, 3, 2]

The constraints tell us that:

  • The tree can contain between 0 and 100 nodes
  • Node values range from -100 to 100

Since the tree is relatively small, performance is not extremely demanding, but we should still aim for the optimal traversal solution.

Some important edge cases include:

  • An empty tree
  • A tree with only one node
  • A completely left-skewed tree
  • A completely right-skewed tree
  • Trees where some children are missing

A naive implementation can easily fail if it does not properly handle None or nil child pointers.

Approaches

Brute Force Approach

The most straightforward solution is recursive depth-first traversal.

The recursive algorithm directly mirrors the definition of inorder traversal:

  • Recursively traverse the left subtree
  • Record the current node's value
  • Recursively traverse the right subtree

This works because recursion naturally keeps track of where we came from in the tree. Each recursive call pauses execution until its subtree is fully processed.

Although this solution is already efficient enough for the problem constraints, recursion implicitly uses the call stack. The follow up asks whether we can solve the problem iteratively, which means we should explicitly manage traversal state ourselves.

Optimal Approach

The optimal iterative solution uses an explicit stack to simulate recursion.

The key insight is that inorder traversal requires us to fully process all left descendants before visiting a node. A stack is perfect for this because it allows us to remember the path back up the tree while we continue exploring left children.

The algorithm repeatedly:

  • Pushes nodes while moving left
  • Processes the top node once no more left children exist
  • Moves to the right subtree afterward

This guarantees nodes are visited in exact inorder sequence.

Approach Time Complexity Space Complexity Notes
Brute Force Recursive DFS O(n) O(h) Uses recursive call stack
Optimal Iterative Stack O(n) O(h) Uses explicit stack, avoids recursion

Here:

  • n is the number of nodes
  • h is the height of the tree

Algorithm Walkthrough

Iterative Inorder Traversal Using a Stack

  1. Initialize an empty stack and an empty result list.

The stack will help us simulate recursion. The result list stores nodes in inorder sequence. 2. Set a pointer called current to the root node.

This pointer tracks the node we are currently exploring. 3. Continue looping while either:

  • current is not None, or
  • the stack is not empty.

This ensures we keep processing until every node has been visited. 4. Move as far left as possible.

While current is not None:

  • Push current onto the stack
  • Move current to current.left

We do this because inorder traversal must fully process left descendants first. 5. Once no more left children exist:

  • Pop the top node from the stack
  • Add its value to the result list

This node is now ready to be visited because its entire left subtree has already been processed. 6. Move to the popped node's right child.

Set:

current = current.right

This begins traversal of the right subtree. 7. Repeat the process until the stack is empty and current is None. 8. Return the result list.

Why it works

The stack always stores ancestors whose left subtrees are already being explored but whose values have not yet been added to the result. When a node is popped, we know every node in its left subtree has already been processed, so it is safe to visit the node itself before moving to the right subtree. This exactly matches the inorder traversal definition.

Python Solution

# 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]:
        result = []
        stack = []
        current = root

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

            current = stack.pop()
            result.append(current.val)

            current = current.right

        return result

The implementation begins by creating two data structures:

  • result, which stores the traversal order
  • stack, which simulates recursive calls

The variable current starts at the root node.

The outer while loop continues as long as there are nodes left to process, either through the current pointer or nodes stored in the stack.

The inner loop repeatedly moves left while pushing nodes onto the stack. This preserves the path back to parent nodes.

Once no more left children exist, the algorithm pops the most recent node from the stack. Since its left subtree is complete, its value is appended to the result.

Finally, traversal shifts to the node's right subtree.

This process continues until every node has been visited exactly once.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    result := []int{}
    stack := []*TreeNode{}
    current := root

    for current != nil || len(stack) > 0 {
        for current != nil {
            stack = append(stack, current)
            current = current.Left
        }

        current = stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        result = append(result, current.Val)

        current = current.Right
    }

    return result
}

The Go implementation follows the exact same algorithmic structure as the Python version.

Some Go-specific details include:

  • nil is used instead of None
  • Slices are used to implement the stack
  • Popping from the stack requires manual slice resizing
  • The result slice dynamically grows with append

Since node values are small and traversal only reads data, integer overflow is not a concern here.

Worked Examples

Example 1

Input:

root = [1,null,2,3]

Tree:

    1
     \
      2
     /
    3
Step Current Stack Result Action
1 1 [] [] Push 1
2 nil [1] [] No left child
3 1 [] [1] Pop and visit 1
4 2 [] [1] Move right
5 2 [] [1] Push 2
6 3 [2] [1] Move left
7 3 [2] [1] Push 3
8 nil [2,3] [1] No left child
9 3 [2] [1,3] Pop and visit 3
10 nil [2] [1,3] Move right
11 2 [] [1,3,2] Pop and visit 2

Final result:

[1,3,2]

Example 2

Input:

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

Tree:

        1
      /   \
     2     3
    / \     \
   4   5     8
      / \   /
     6   7 9

Traversal order:

4 -> 2 -> 6 -> 5 -> 7 -> 1 -> 3 -> 9 -> 8

Final output:

[4,2,6,5,7,1,3,9,8]

The algorithm repeatedly descends left, processes nodes, and explores right subtrees in proper inorder sequence.

Example 3

Input:

root = []

Initial state:

Current Stack Result
nil [] []

The loop never executes because both conditions are false.

Final result:

[]

Example 4

Input:

root = [1]
Step Current Stack Result Action
1 1 [] [] Push 1
2 nil [1] [] No left child
3 1 [] [1] Pop and visit 1

Final result:

[1]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node is pushed and popped exactly once
Space O(h) Stack stores at most the tree height

The time complexity is linear because each node participates in a constant number of operations.

The space complexity depends on the tree height. In the worst case, a completely skewed tree behaves like a linked list, causing the stack to store all n nodes. In a balanced tree, the height is approximately log n.

Test Cases

# Definition for testing
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):
        result = []
        stack = []
        current = root

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

            current = stack.pop()
            result.append(current.val)

            current = current.right

        return result

solution = Solution()

# Empty tree
assert solution.inorderTraversal(None) == []  # tests empty input

# Single node
root = TreeNode(1)
assert solution.inorderTraversal(root) == [1]  # tests one-node tree

# Right-skewed tree
root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
assert solution.inorderTraversal(root) == [1, 3, 2]  # tests mixed structure

# Balanced tree
root = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(4),
        TreeNode(5, TreeNode(6), TreeNode(7))
    ),
    TreeNode(
        3,
        None,
        TreeNode(8, TreeNode(9))
    )
)
assert solution.inorderTraversal(root) == [4, 2, 6, 5, 7, 1, 3, 9, 8]  # tests complex tree

# Left-skewed tree
root = TreeNode(4,
    TreeNode(3,
        TreeNode(2,
            TreeNode(1)
        )
    )
)
assert solution.inorderTraversal(root) == [1, 2, 3, 4]  # tests deep left traversal

# Tree with negative values
root = TreeNode(0,
    TreeNode(-3),
    TreeNode(5)
)
assert solution.inorderTraversal(root) == [-3, 0, 5]  # tests negative values

# Tree with missing children
root = TreeNode(1,
    TreeNode(2, None, TreeNode(4)),
    TreeNode(3)
)
assert solution.inorderTraversal(root) == [2, 4, 1, 3]  # tests sparse tree
Test Why
Empty tree Verifies algorithm handles no nodes correctly
Single node Confirms simplest non-empty tree
Right-skewed tree Tests traversal when right children dominate
Balanced tree Validates normal multi-level traversal
Left-skewed tree Tests deep stack growth
Negative values Ensures values themselves do not affect traversal
Missing children Confirms sparse trees are handled correctly

Edge Cases

Empty Tree

An empty tree is represented by root = None in Python or nil in Go. This case is easy to mishandle if the algorithm assumes a valid node exists before entering the loop.

The implementation handles this correctly because the outer loop condition:

while current or stack

fails immediately when both are empty, returning an empty list.

Completely Left-Skewed Tree

A tree where every node only has a left child can expose issues with stack handling or recursive depth assumptions.

For example:

    4
   /
  3
 /
2
/
1

The iterative solution correctly pushes all nodes while descending left, then processes them in reverse order as they are popped from the stack.

Nodes With Missing Children

Binary trees are often sparse, meaning some nodes may have only one child.

Example:

    1
   /
  2
   \
    4

Incorrect implementations sometimes assume both children exist or attempt invalid accesses.

This solution safely checks whether current is None before accessing child pointers, ensuring sparse trees work correctly without runtime errors.