In-order traversal

O(n)

In-order traversal recurses into the left child, visits the node, then recurses into the right child. On a binary search tree this produces the values in sorted order, which is why in-order is the go-to traversal for listing a BST. It runs in O(n) and uses O(h) stack space for height h.

Binary search tree
Press ▶ to run
Edit the input and press Play

How it works

  1. Recurse into the left subtree first.
  2. Visit the current node.
  3. Recurse into the right subtree.
  4. On a BST, nodes come out in ascending order.

Pseudocode

1inorder(node):                      # O(n)2  if node = null: return3  inorder(node.left)4  visit(node)                        # sorted order on a BST5  inorder(node.right)