ENDEAR
Start free
algorithmpro

Depth-first tree traversal

Visit a binary search tree in order: left subtree, then the node, then the right subtree.

time
O(n)
space
O(h)

// step through it

step 1 / 14
1function inorder(node, out) {2  if (node === null) return;3  inorder(node.left, out);4  out.push(node.val);5  inorder(node.right, out);6}
out
= []
4261357
  • 4
  • 2
  • 6
  • 1
  • 3
  • 5
  • 7

At 4: go into the left subtree first.

// pro lesson

Unlock the full walkthrough

This lesson is part of Pro. Pro unlocks every step of every lesson, plus pattern drills and mastery insights.

See pricing

How it works

Depth-first search goes as deep as it can before backing up. In-order traversal does it in a fixed order: the whole left subtree, then the node itself, then the right subtree. Recursion handles the backing up for free, because each call returns to its parent. On a binary search tree this order outputs the values sorted. Every node is visited once: O(n) time, and O(h) space for the call stack, where h is the height of the tree.

Practice spotting this pattern →