In-Order Traversal — Left, Root, Right

In-Order Traversal (LNR)

In-order traversal visits nodes in the order: Left subtree, Node, Right subtree. For a Binary Search Tree, this produces values in ascending sorted order, which is one of the most useful properties of BSTs.

Recursive Implementation

INORDER(node):
  if node is NULL: return
  INORDER(node.left)
  visit(node)          // process current node
  INORDER(node.right)

Example

        4
       / \
      2   6
     / \ / \
    1  3 5  7

In-order result: [1, 2, 3, 4, 5, 6, 7]

Notice the output is sorted — this always holds for a valid BST.

Iterative Implementation Using a Stack

INORDER_ITERATIVE(root):
  stack = []
  current = root
  while current != NULL or stack is not empty:
    while current != NULL:
      stack.push(current)
      current = current.left
    current = stack.pop()
    visit(current)
    current = current.right

The iterative version uses an explicit stack to simulate the recursion. It processes the leftmost nodes first, which mirrors the recursive call order.

Time and Space Complexity

• Time: O(n) — every node is visited exactly once
• Space: O(h) — the recursion depth (or stack size) equals the tree height h; this is O(log n) for balanced trees and O(n) for skewed trees

Applications

• BST validation: If in-order traversal produces a sorted sequence, the tree is a valid BST
• Kth smallest element: Perform in-order traversal and stop at the kth element
• Range queries: Collect all values between two bounds during in-order traversal