Interview Cake by Aced

In-Order Traversal of a Binary Search Tree

In short: An in-order traversal visits a binary tree's left subtree, then the node itself, then the right subtree. On a binary search tree that visits the values in sorted order, in O(n) time and O(h) space for the recursion, where h is the tree's height.

Sometimes we have a BST and we want to go through the items in order from smallest to largest. This is called an "in-order traversal."

We can write a recursive algorithm for this:

  • Everything in the left subtree is smaller, so print that first, then,
  • print the current node, then
  • print the right subtree.
public static void inorderPrint(BinaryTreeNode node) { if (node != null) { inorderPrint(node.left); System.out.println(node.value); inorderPrint(node.right); } }

This takes time (we're traversing the whole tree, so we're looking at all n items) and space, where h is the height of the tree (this is the max depth of the call stack during our recursion).

If the tree is balanced its height is lg(n), so we have space. If we can't make any assumptions about the "shape" of the tree, in the worst case it's just one continuous line, giving us a height of n, and a space complexity of for our recursive in-order traversal.

See also:

Frequently Asked Questions

What is an inorder traversal?

A depth-first traversal that visits the left subtree, then the current node, then the right subtree (left, root, right).

Why does an inorder traversal of a BST give sorted output?

Everything in a node's left subtree is smaller and everything in its right subtree is larger, so visiting left, node, right outputs the values from smallest to largest.

What is the time and space complexity of inorder traversal?

O(n) time, since every node is visited once, and O(h) space for the call stack, where h is the height of the tree: O(log n) if it's balanced, O(n) in the worst case.

Last updated: October 21, 2026

. . .