Problem Statement

Binary Tree Inorder Traversal

You are given a binary tree. A binary tree is a set of connected boxes called nodes, where each node holds a value and can have a left child and a right child below it. The top node is called the root. Your job is to read every value and put them in a list in a special order called inorder. Inorder means: first read everything in the left side, then read the node itself, then read everything in the right side. So the order is left, then root, then right.

easyTreeTreesTime: O(n) · Space: O(n)

Signals to notice

visit all nodesleft-right-root or root-left-right ordertree traversal

Brute force first

No brute force alternative — traversal is the task itself. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

Recursive DFS: traverse left subtree, visit node, traverse right subtree. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `root=[1,null,2,3] (root 1; right child 2; 2's left child 3)`

result=[]; call inorder(1)
inorder(1): inorder(left=null) -> base case, returns immediately
inorder(1): append 1 -> result=[1]; now call inorder(right=2)
inorder(2): call inorder(left=3)
inorder(3): inorder(null) returns; append 3 -> result=[1,3]; inorder(null) returns
back in inorder(2): append 2 -> result=[1,3,2]; inorder(right=null) returns
all calls unwind; return result=[1,3,2]

What must stay true

Inorder traversal of a BST visits nodes in sorted order. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

function inorder(node):
    if node is null: return
    inorder(node.left)
    result.append(node.val)
    inorder(node.right)
return result

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Forgetting the base case (null node) — always check if the node exists before recursing. The fix is usually to return to the meaning of each move, not just the steps themselves.

Trees Pattern