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

Two plain first ideas. Reading the array in order is wrong: the array is written level by level, not in left-to-right order ([1,2,3,4,5] read as it is stays [1,2,3,4,5] instead of [4,2,5,1,3]). The correct first idea joins lists: inorder(node) = inorder(left) + [node.val] + inorder(right). It works, but every call builds a new list as long as its whole side, so the same values are copied again and again. The optimal version keeps the same left, record, right order but writes into ONE shared list.

Steps

  1. If the node is null, return an empty list (base case)
  2. Build the left list by recursing into node.left
  3. Build the right list by recursing into node.right
  4. Return left + [node.val] + right (a brand-new list at every call)

Time complexity: O(n) calls, but O(n^2) values copied on a chain · Space complexity: O(n^2) values created in total on a chain (O(n) alive at once, plus the call stack)

Trade-offs

  • Copies values into new lists at every level: on a chain of n nodes it places n(n + 1) / 2 values (500,500 for n = 1000) against n appends with one shared list
  • Reading the array order instead is simply wrong: the array is level by level, not inorder
  • Still uses O(h) call-stack space, and Python stops the recursion near 1,000 levels

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 with ONE shared result list is the clean optimal solution for inorder traversal: n appends instead of the n(n + 1) / 2 copies of the join-lists idea. An iterative approach using an explicit stack avoids the recursion limit, and 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)
  • Common slip: appending the node when you push it (or on first arrival) instead of when it is popped. A node is recorded after its left side is finished.
  • Iterative version: the stack holds the nodes whose left side is being walked; a recorded node leaves it.

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). The iterative version's stack is also at most the height: only 1 node on a right-leaning chain, but all n on a left-leaning chain.

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