Binary Tree Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its nodes' values — visit the left subtree, then the node, then the right subtree.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Inorder means left subtree, then the node, then right subtree.

Recursively that's three lines; iteratively use an explicit stack.

For the iterative version, walk left pushing nodes, then pop to visit and go right.

Common doubts

On a binary search tree, inorder yields the node values in sorted order, which is why many BST problems start with an inorder walk.

Inorder visits the leftmost node first, so you must descend all the way left (stacking nodes) before recording anything.

O(height) for the recursion/stack — O(log n) for a balanced tree, O(n) for a degenerate (list-like) one.

Interview follow-ups

· What an interviewer asks next.

Morris traversal threads temporary links from each subtree's rightmost node back to its successor, achieving O(1) space at the cost of temporarily mutating the tree.

Only in when the node is recorded: preorder records before recursing, postorder records after both children.

Fun facts

Inorder traversal of a BST is the basis of the 'kth smallest element' and 'validate BST' solutions.
Morris traversal's threading trick briefly turns the tree into a temporary linked structure to avoid a stack entirely.

Asked at

AmazonMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: root = [1, null, 2, 3]
Output: [1, 3, 2]
Inorder visits the left subtree (empty), then 1, then its right subtree yielding 3 then 2.

Example 2

Input: root = []
Output: []
An empty tree has no nodes.

Constraints

- The number of nodes is in the range [0, 100] - -100 <= Node.val <= 100

Inorder means left, node, right. The recursive version is almost a transcription of that phrase; the iterative version makes the hidden stack explicit — dive left pushing nodes, then pop-visit-and-go-right.

Prerequisites

Before you start

· Concepts used directly in the solution.

Binary tree. Nodes with a value and up to two children (left, right).

Recursion / explicit stack. The two ways to remember where to resume after visiting a subtree.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The order

“What is inorder exactly?”

Left subtree, then the current node, then the right subtree.

“Anything special about a BST?”

On a binary search tree, inorder yields the values in sorted order.

The ideal opening — say it like this

Inorder is left, node, right, so I recurse into the left child, record the node, then recurse into the right child.

The iterative version makes the call stack explicit: go left pushing nodes, pop one to visit it, then move to its right child.

Understand the problem

Worked example — tree [1, null, 2, 3] (1 with right child 2, whose left child is 3)

        1
         \
          2
         /
        3
inorder: left of 1 (none) -> 1 -> right subtree of 1
         in that subtree: left is 3 -> 2
result: [1, 3, 2]

Key observations

1Aha

Inorder is left, node, right

The traversal is a direct realization of that ordering; the only question is whether you use the call stack (recursion) or an explicit one.

2Aha

The iterative stack mirrors the recursion

Pushing while walking left and popping to visit reproduces exactly what recursion does implicitly.

3Aha

Linear time and height space

Every node is visited once (O(n)); the stack holds at most the current root-to-leaf path (O(height)).

Brute force vs optimal

	Iterative (explicit stack)	Recursive
Idea	Walk left pushing nodes; pop, visit, go right	dfs(left); visit; dfs(right)
Time	O(n)	O(n)
Space	O(height)	O(height)

Both are O(n); the recursive form is the clearest, the iterative form avoids the call stack. Full code is in the Approaches selector below.

Summary

Key takeaway

Inorder = left, node, right. Recurse into the left child, record the node, recurse into the right child — or make the stack explicit by walking left and popping to visit. O(n) time, O(height) space.

inorder(node):
    if node is null: return
    inorder(node.left)
    visit(node)
    inorder(node.right)