In-order Traversal — Binary Tree Guide

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

Watch pointers traverse left children, visit parent keys, and visit right subtrees in real-time:

Key Takeaway

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.