Traversal

In-Order (Left, Root, Right)

Traverse left subtree first, then visit root, then right subtree. On a BST, this visits nodes in SORTED order — incredibly useful. Any time you need sorted output from a BST, think in-order.

O(n)

O(h)

How It Works

In-order traversal recurses into the left subtree, visits the node itself, then recurses right. On a binary search tree this left-root-right order produces the node values in ascending sorted order, because everything smaller than a node lives in its left subtree and everything larger in its right. That single property powers a whole family of BST problems: kth smallest, validation via a strictly increasing previous-value check, converting a BST to a sorted list, and finding successors.

The iterative form walks left pushing nodes onto a stack, pops one to visit, then moves to its right child and repeats. Every node is pushed and popped once, so time is O(n) and space is O(h) for the stack. Compared to extracting all values and sorting them at O(n log n), the traversal gets sorted output for free from the tree's structure.

Step-by-Step Visualization

In-order on BST: Left, Root, Right → sorted!

Go left4→2→1 (leftmost)

Output[1]

1/3

Code

Java

static List<Integer> inorder(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();
  TreeNode curr = root;

  while (curr != null || !stack.isEmpty()) {
    while (curr != null) { stack.push(curr); curr = curr.left; }
    curr = stack.pop();
    result.add(curr.val);
    curr = curr.right;
  }
  return result;
}

// BST: [4,2,6,1,3,5,7] → In-order: [1,2,3,4,5,6,7]

Tips & Gotchas

1Visit left subtree, then root, then right subtree

2For BSTs, in-order gives sorted output

3Iterative: go left as far as possible, then process and go right

Practice Problems

1Binary Tree Inorder Traversal
2Kth Smallest Element in a BST
3Validate Binary Search Tree
4Convert Binary Search Tree to Sorted Doubly Linked List
5Binary Search Tree Iterator

About the Traversal Pattern

There are four ways to visit every node in a tree. Three use DFS (going deep before going wide) with different orderings, and one uses BFS (going wide before going deep). Each ordering is useful for different problems.

Key insight

Tree problems are almost always DFS (recursion) or BFS (level-order). The pattern: solve for children, combine results, return up. BST's sorted property lets you prune half the tree.

Common Trees Interview Problems

Maximum Depth of Binary Tree
Validate BST
Binary Tree Level Order Traversal
Lowest Common Ancestor
Serialize and Deserialize Binary Tree
Diameter of Binary Tree

Frequently Asked Questions

Does in-order traversal give sorted output on any binary tree?

No, only on a binary search tree. The sorted property follows directly from the BST invariant that left descendants are smaller and right descendants are larger. On an arbitrary binary tree, in-order is just one of several valid visiting orders with no ordering guarantee.

How do I stop an in-order traversal early, say after the kth node?

With recursion, return a flag or throw once a counter hits k; with the explicit-stack version, simply break out of the loop after the kth pop. Early exit makes kth-smallest queries cost O(h + k) rather than a full O(n) sweep.