Tree Traversal

In-order

What is In-order Traversal?

In-order traversal visits a node's left subtree, then the node itself, then its right subtree — the order is Left, Root, Right. The "in" refers to the root being processed in between its two children, rather than before or after both of them.

How Does It Work?

  1. Start at the root (8), but don't visit it yet — first go left
  2. At 3, go left again first: reach 1 (a leaf) — visit it: 1
  3. Back at 3, its left is done — visit 3: 1, 3
  4. Now go right from 3: reach 6 (a leaf) — visit it: 1, 3, 6
  5. Back at 8, its left subtree is fully done — visit 8: 1, 3, 6, 8
  6. Go right from 8: reach 10 — visit it: 1, 3, 6, 8, 10 (sorted!)
84321163105
Visit orderNode

In-order traversal has one property that makes it stand out from pre-order and post-order: when run on a Binary Search Tree, it visits every value in strictly ascending sorted order. That falls directly out of the BST invariant — every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger, so visiting left-root-right at every level naturally produces sorted output.

This is why in-order traversal is the standard way to read a BST's contents in sorted order without needing a separate sort step, and why it's used to validate whether a tree actually satisfies the BST property — if the in-order sequence isn't strictly increasing, the tree isn't a valid BST.

Algorithm Steps

  1. If the current node is null, return immediately (base case)
  2. Recursively traverse the left subtree
  3. Visit (process) the current node
  4. Recursively traverse the right subtree

Time Complexity

  • Time Complexity: Every node is visited exactly once → O(n).
  • Space Complexity: Bounded by the recursion depth → O(h).

Time Complexity Analysis

Advertisement

Traversal needs O(h) extra space for the recursion call stack, where h is the tree's height — O(log n) for a balanced tree, but O(n) in the worst case of a completely skewed tree.

Daily DSA Challenge by Scale Engineer

Build a tree, then watch in-order visit Left → Root → Right

Tree is empty
No tree yet — insert a value or generate a random tree
Not yet visitedVisitedCurrently visitingRoot

Test Your Knowledge before moving forward!

In-order Traversal Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

In-order Traversal Implementation

// Binary tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// In-order traversal: Left -> Root -> Right
function inOrder(node, result = []) {
  if (node === null) return result;

  inOrder(node.left, result);
  result.push(node.value); // visit root in between
  inOrder(node.right, result);

  return result;
}

// Usage example — for a BST, the output comes out sorted
let root = new TreeNode(8);
root.left = new TreeNode(3);
root.right = new TreeNode(10);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(6);

console.log(inOrder(root)); // [1, 3, 6, 8, 10]

Done With the Learning

Mark In-order Traversal as done and view it on your dashboard

Explore Other Tree Topics

Pre-order Traversal

Post-order Traversal

Level-order Traversal

Morris Traversal

BST Insertion

BST Deletion

BST Searching

AVL Balancing