Inorder traversal
Visit the left subtree, then the root, then the right subtree — the order that sorts a BST for free. About 8 minutes.
Left, then root, then right
Inorder of a tree means: do inorder on the left subtree first, then write down the node's own value, then do inorder on the right subtree. The node sits in between its two sides, which is where the name "in order" comes from.
The base case is the same as before: an empty subtree adds nothing.
if not root:
return []
out = inorder_traversal(root.left)
out.append(root.val)
out += inorder_traversal(root.right)
return out- result
- []
At 5, we don't visit yet. Left subtree first.
The special case of a BST
A binary search tree keeps every left subtree smaller than its node and every right subtree larger, like a well-kept filing system. Inorder visits smaller things, then the node, then larger things.
So on a search tree it always produces the values in fully sorted order. You get sorting as a side effect of the walk.
For the BST with root 5, left child 3, and right child 8, what does inorder traversal return?
- A[3, 5, 8]
- B[5, 3, 8]
- C[3, 8, 5]
Show the answer
[3, 5, 8]. Left subtree (3) first, then the root (5), then the right subtree (8) — already sorted.
Inorder traversal
Given the root of a binary tree, return the values of its nodes visited in inorder: every node in its left subtree, then the current node, then every node in its right subtree. If the tree is empty, return an empty list.
root = [5, 3, 8] → [3, 5, 8]
0 ≤ number of nodes ≤ 10,000 · -1,000,000 ≤ node.val ≤ 1,000,000