Inorder Tree Traversal Tutorial | Learn Data Structures

What Is Inorder Traversal?

Inorder traversal is a depth-first tree traversal technique that visits the left subtree, then the current node, and finally the right subtree.

Left → Root → Right

Inorder traversal is especially important for Binary Search Trees because visiting the nodes in inorder produces their values in ascending order, provided the tree follows the BST ordering property.

Example Binary Tree

Consider the following binary tree:

          50
         /  \
       30    70
      /  \  /  \
    20   40 60   80

Inorder traversal starts at the root and explores the left subtree completely before processing the root and then moving through the right subtree.

Inorder:

20 → 30 → 40 → 50 → 60 → 70 → 80

How Inorder Traversal Works

For every node, inorder traversal follows the same three steps:

Traverse the left subtree.
Process the current node.
Traverse the right subtree.

These steps are applied recursively to every subtree until all nodes have been visited.

Tracing Inorder Traversal

Consider the left side of the example tree:

      30
     /  \
   20    40

The traversal first visits 20 because it is the leftmost node. It then processes 30 and finally visits 40.

20 → 30 → 40

The same process is then applied to the right subtree of 50:

      70
     /  \
   60    80

60 → 70 → 80

Finally, 50 is processed between the left and right subtree results.

Recursive Inorder Traversal

Recursion is one of the simplest ways to implement inorder traversal because every subtree is itself a tree.

function inorder(root, result = []) {
  if (root === null) {
    return result;
  }

  inorder(root.left, result);
  result.push(root.value);
  inorder(root.right, result);

  return result;
}

The base case stops the traversal when an empty subtree is reached. The current node is added to the result only after its left subtree has been completely processed.

Complete Recursive Example

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function inorder(root, result = []) {
  if (root === null) {
    return result;
  }

  inorder(root.left, result);
  result.push(root.value);
  inorder(root.right, result);

  return result;
}

const root = new Node(50);

root.left = new Node(30);
root.right = new Node(70);

root.left.left = new Node(20);
root.left.right = new Node(40);

root.right.left = new Node(60);
root.right.right = new Node(80);

console.log(inorder(root));

Inorder Traversal in a Binary Search Tree

Inorder traversal has a special property when used with a Binary Search Tree. Because smaller values are stored on the left and greater values are stored on the right, inorder traversal visits values in sorted order.

BST:

        50
       /  \
     30    70
    /  \  /  \
  20   40 60   80

Inorder:

20, 30, 40, 50, 60, 70, 80

This makes inorder traversal useful for extracting sorted data from a BST without first copying the values into a separate sorting algorithm.

Inorder Traversal Does Not Always Produce Sorted Data

Inorder traversal itself does not sort a tree. It only follows the Left-Root-Right order. Sorted output occurs when the tree being traversed satisfies the Binary Search Tree ordering property.

Binary Tree:

      10
     /  \
   30    20

Inorder:

30, 10, 20

The result is not sorted because this is not a valid Binary Search Tree.

Iterative Inorder Traversal

Inorder traversal can be implemented without recursion by using a stack. The stack simulates the function call stack used by the recursive solution.

function inorderIterative(root) {
  const stack = [];
  const result = [];
  let current = root;

  while (current !== null || stack.length > 0) {
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    current = stack.pop();
    result.push(current.value);

    current = current.right;
  }

  return result;
}

How the Iterative Version Works

The iterative algorithm repeatedly moves as far left as possible while storing each node on a stack. When there is no more left child, the most recently stored node is processed. The algorithm then moves to its right subtree.

For the following tree:

The stack first follows the path:

50 → 30 → 20

Node 20 has no left child, so it is processed. The algorithm then returns to 30, processes it, and moves into its right subtree.

Inorder Traversal Using a Generator

In JavaScript, a generator can produce inorder values one at a time instead of storing the entire traversal result in an array.

function* inorderGenerator(root) {
  if (root === null) {
    return;
  }

  yield* inorderGenerator(root.left);
  yield root.value;
  yield* inorderGenerator(root.right);
}

for (const value of inorderGenerator(root)) {
  console.log(value);
}

This approach can be useful when values should be consumed incrementally rather than collected into a complete result array.

Finding the Kth Smallest Value

Because inorder traversal of a BST produces values in ascending order, it can be used to find the kth smallest value without explicitly sorting all the values.

function kthSmallest(root, k) {
  const stack = [];
  let current = root;

  while (current !== null || stack.length > 0) {
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    current = stack.pop();

    k--;

    if (k === 0) {
      return current.value;
    }

    current = current.right;
  }

  return null;
}

The traversal stops as soon as the kth node in sorted order is reached, so it does not necessarily need to visit every node.

Inorder Traversal for BST Validation

Another useful application is checking whether a binary tree satisfies the ordering property of a Binary Search Tree. During inorder traversal, the values of a valid BST should appear in strictly increasing order when duplicates are not allowed.

function isValidBST(root) {
  const stack = [];
  let current = root;
  let previous = null;

  while (current !== null || stack.length > 0) {
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    current = stack.pop();

    if (previous !== null && current.value <= previous) {
      return false;
    }

    previous = current.value;
    current = current.right;
  }

  return true;
}

Inorder Traversal Complexity

A complete inorder traversal visits every node exactly once, so its time complexity is O(n), where n is the number of nodes.

Implementation	Time	Auxiliary Space
Recursive	O(n)	O(h)
Iterative	O(n)	O(h)
Generator	O(n) for full traversal	O(h) traversal state

Here, h represents the height of the tree. For a balanced tree, h is typically O(log n). For a highly skewed tree, h can approach O(n).

Inorder Traversal Applications

Inorder traversal is useful whenever a binary tree's left-to-right structure has meaning. Common applications include:

Producing sorted values from a Binary Search Tree
Finding the kth smallest element in a BST
Validating Binary Search Tree ordering
Processing expression trees in specific representations
Generating ordered output from hierarchical structures
Solving binary tree and BST interview problems

Common Inorder Traversal Mistakes

Processing the root before the left subtree, which changes the traversal to preorder.
Processing the root after both subtrees, which changes it to postorder.
Forgetting the base case for null nodes.
Assuming inorder traversal automatically sorts any binary tree.
Forgetting to move to the right subtree after processing a node.
Using an incorrect stack order in the iterative implementation.
Assuming recursive and iterative traversal produce different results.

Inorder Traversal vs Other DFS Traversals

The three depth-first traversals use the same basic recursive structure. Their difference is simply when the current node is processed.

Traversal	Node Processing Position
Preorder	Before left and right subtrees
Inorder	Between left and right subtrees
Postorder	After left and right subtrees

Key Takeaways

Inorder traversal follows Left → Root → Right.
It is a depth-first traversal technique.
Recursive implementation naturally follows the traversal definition.
An iterative implementation uses a stack to simulate recursion.
Inorder traversal of a valid BST produces values in ascending order.
It can be used to find the kth smallest value in a BST.
It can help validate whether a binary tree satisfies BST ordering.
A complete inorder traversal takes O(n) time.
Auxiliary traversal space is O(h), where h is the tree height.

Topics

Inorder Tree Traversal