Binary Tree · Traversal
Visual EditorTree Problems

Inorder Traversal

Visit nodes in Left → Root → Right order. For a BST, this gives you a sorted sequence.

RecursionDFSInterview Essential

Key concepts at a glance — for those who already know the basics.

Problem Statement

Binary Tree Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its node values.
Example 1

Input: root = [1, null, 2, 3]

Output: [1, 3, 2]

Tree: 1 → right child 2, left child of 2 is 3.

Example 2

Input: root = [1, 2, 3, 4, 5, 6, 7]

Output: [4, 2, 5, 1, 6, 3, 7]

Perfect binary tree — left subtree, root, right subtree.

Constraints

  • The number of nodes in the tree is in the range [0, 100].
  • Each node's value is in the range [-100, 100].
01

The Task

Given the root of a binary tree, return a list of all node values in inorder sequence.

Input:binary tree
Output:[4, 2, 5, 1, 6, 3, 7]
02

The Rule

Left → Root → Right

At every node: go as far left as possible, visit the current node, then explore the right subtree.

03

The Intuition

Analogy

Think of a bookshelf — books sorted left to right. You always finish the left shelf before reading the current book, then move right.

Superpower

Inorder of a Binary Search Tree always produces values in ascending sorted order.

04

Mental Model

1

Go Left

Keep going left until you hit None — the recursion dives to the leftmost leaf.

2

Visit Current

Only after the entire left subtree is done, append this node's value.

3

Go Right

The right subtree is a new problem — apply the same Left → Root → Right rule.

05

Dry Run

1root234leaf5leaf6leaf7leaf
Step
Node
What Happens
1
4
No left child. Visit 4. No right child. Done.
2
2
Left (4) already done. Visit 2. Now go right → 5.
3
5
No left child. Visit 5. No right child. Done.
4
1
Entire left subtree (4,2,5) done. Visit root 1. Go right → 3.
5
6
No left child. Visit 6. No right child. Done.
6
3
Left (6) done. Visit 3. Go right → 7.
7
7
No left child. Visit 7. No right child. Done.
06

Code

solution.py
def inorder(node, result):
if node is None: return # base case
inorder(node.left, result) # 1. go left
result.append(node.val) # 2. visit
inorder(node.right, result) # 3. go right
07

Complexity

Time

O(n)

Every node visited exactly once.

Space

O(h)

Recursion stack = tree height. Balanced: log n. Skewed: n.

08

Interview Questions

Kth smallest in BST

Inorder gives sorted order, so the kth element is the answer.

Validate a BST

Check that the inorder sequence is strictly increasing.

Convert BST to sorted array

Directly collect inorder result.

Recover BST

Find the two swapped nodes by spotting where inorder order breaks.

Ready to see it in action?

Step through the visualizer to watch the algorithm state update live.

Open Visualizer