Binary Tree Inorder Traversal

Difficulty: Easy

Problem

Starting from the root of a binary tree, produce the list of node values in inorder sequence: everything in the left subtree, then the node itself, then everything in the right subtree.

Example

Input: root = [5,3,null,1,4]
Output: [1,3,4,5]
Explanation: Node 5 has only a left child 3. Visit 3's left (1), then 3, then 3's right (4), and only then the root 5, giving [1,3,4,5].

Brute-force approach

Use recursion to traverse the tree: go left, visit node, go right. This is the natural recursive approach and is actually the standard solution for this problem.

Steps

  1. If the current node is null, return (base case)
  2. Recursively traverse the left subtree
  3. Add the current node's value to the result
  4. Recursively traverse the right subtree

Time complexity: O(n) · Space complexity: O(n): O(h) for call stack + O(n) for result array

Trade-offs

  • Uses O(h) stack space due to recursion (O(n) worst case for skewed trees)
  • Risk of stack overflow for very deep trees
  • Cannot pause/resume traversal easily

Optimal approach

Key insight: Inorder traversal follows a simple pattern: fully explore the left subtree first, then visit the current node, then fully explore the right subtree. The recursion naturally handles the ordering.

The recursive approach IS the clean optimal solution for inorder traversal. An alternative iterative approach using an explicit stack avoids recursion overhead and stack overflow risk, but both are O(n) time and O(h) space.

Steps

  1. Base case: If node is null, return immediately
  2. Recurse into the left child (explore entire left subtree)
  3. Visit current node: append its value to the result list
  4. Recurse into the right child (explore entire right subtree)

Time complexity: O(n) · Space complexity: O(h) where h = height of tree

Pseudocode

function inorderTraversal(root):
    result = ____
    
    function inorder(node):
        if node is ____:
            return
        inorder(____)
        result.append(____)
        inorder(____)
    
    inorder(root)
    return result

Hints

  • Base case: What do we do when node is null? (Stop recursing!)
  • Step 1: First recurse into node.left (go LEFT)
  • Step 2: Then add node.val to result (VISIT current node)
  • Step 3: Then recurse into node.right (go RIGHT)

Complexity questions

What is the time complexity of inorder traversal?

O(n). Every node in the tree is visited exactly once. With n nodes, the time complexity is O(n).

What is the space complexity of the recursive approach (excluding the output array)?

O(log n) for balanced, O(n) for skewed. The space is determined by the recursion stack depth, which equals the tree height. For a balanced tree: O(log n). For a completely skewed tree (like a linked list): O(n).

Why is the recursion call stack important to consider for tree traversals?

For very deep/skewed trees, deep recursion can cause stack overflow. Each recursive call adds a frame to the call stack. For a skewed tree with n nodes, this means n frames on the stack. Systems have a limited stack size, so very deep trees can cause stack overflow. Which is why an iterative solution can be safer.

If you run inorder traversal on a valid BST with values [5, 3, 7, 1, 4], what will the output order be?

[1, 3, 4, 5, 7]. Inorder on a BST always produces sorted (ascending) order. The BST property (left < root < right) combined with Left-Root-Right traversal guarantees this. The tree is: 5 → left 3 (left 1, right 4), right 7. Inorder: 1, 3, 4, 5, 7.

Check your understanding of Binary Tree Inorder Traversal

What order does inorder traversal visit nodes?

Left, Root, Right. Inorder traversal follows Left -> Root -> Right. First we fully explore the left subtree, then visit the current node, then fully explore the right subtree.

Given the tree [1,null,2,3] (tree: 1 -> right 2 -> left 3), what is the inorder traversal?

[1, 3, 2]. Starting at root 1: go left (null, nothing). Visit 1. Go right to 2: go left to 3 (leaf, visit 3). Visit 2. Go right (null). Result: [1, 3, 2].

What does inorder traversal produce when run on a Binary Search Tree (BST)?

Sorted (ascending) order. In a BST, all left descendants < root < all right descendants. Inorder (Left, Root, Right) visits smaller values first, then root, then larger values, producing sorted output!

What is the base case for recursive inorder traversal?

When the node is null (empty). The base case is when we reach a null node (empty position). A leaf node is NOT the base case: we still recurse into its null children. Null means 'nothing here, stop and return'.

For a tree with only a root node (no children), what is the inorder traversal result?

[root.val]. Go left: null (nothing). Visit root: add root.val. Go right: null (nothing). Result: just [root.val].

Related problems

Keep practising