The Concept#

In-order traversal is a depth-first search (DFS) algorithm for trees. For any given node, the traversal follows these steps recursively:

  1. Traverse the left subtree.
  2. Visit the current node (the root).
  3. Traverse the right subtree.

For a Binary Search Tree (BST), performing an in-order traversal yields the elements in sorted ascending order.

Code Implementation#

Below is the recursive implementation of In-order Traversal:

  • Time Complexity: $O(N)$ since we visit each of the $N$ nodes exactly once.
  • Space Complexity: $O(H)$ auxiliary space for the recursion call stack, where $H$ is the height of the tree.

Interactive Lab: In-order Traversal#

Let's take the example of this visualization: a five-node tree with 0 at the root, 1 and 2 as its children, 3 hanging under 1 on the left, and 4 under 2 on the right. Press Play and the pointer dives left as far as it can go (all the way down to 3) before a single value is recorded.

Watch the OUTPUT rail fill in 3, 1, 0, 2, 4, and watch where the root lands: dead centre. Everything in 0's left subtree is emitted before it, everything in its right subtree after it. That's left → node → right playing out one node at a time.

What to Remember#

In-order traversal is the fundamental method for retrieving sorted values out of a BST. Since BST node ordering properties guarantee left subtrees contain only smaller values and right subtrees contain larger values, visiting left-node-right inherently results in sorted sequences.