In Order Traversal

Introduction

Inorder Traversal is one of the fundamental tree traversal techniques used in binary trees. It follows the Left → Root → Right sequence, meaning it first visits the left subtree, then the current node, and finally the right subtree. When performed on a Binary Search Tree (BST), inorder traversal yields the nodes in ascending sorted order, which makes it especially useful in search applications.

Understanding how inorder traversal works — both recursively and iteratively — is essential for mastering tree data structures and for solving problems related to sorting, serialization, tree reconstruction, and validation of BSTs.

What Is Tree Traversal?

Tree traversal is the process of visiting all the nodes in a tree structure in a specific order. There are three major types of depth-first traversal:

Inorder (Left → Root → Right)
Preorder (Root → Left → Right)
Postorder (Left → Right → Root)

Among these, inorder traversal is especially significant because of its direct relationship to sorted order in BSTs.

Inorder Traversal Algorithm

The basic recursive algorithm can be described as:

Traverse the left subtree
Visit the root node
Traverse the right subtree

Pseudocode (Recursive)

inorder(node):
    if node is not null:
        inorder(node.left)
        visit(node)
        inorder(node.right)

Inorder Traversal Example

Consider the following binary tree:

        10
       /  \
      5    15
     / \     \
    2   7     20

Inorder Traversal Output:

2 → 5 → 7 → 10 → 15 → 20

Explanation:

Traverse left subtree of 10 → (5 → 2 → 7)
Visit 10
Traverse right subtree → (15 → 20)

Inorder Traversal in Python (Recursive)

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def inorder_recursive(root):
    if root:
        inorder_recursive(root.left)
        print(root.key, end=" ")
        inorder_recursive(root.right)

# Sample tree
root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(2)
root.left.right = Node(7)
root.right.right = Node(20)

inorder_recursive(root)
# Output: 2 5 7 10 15 20

Inorder Traversal in Python (Iterative)

Using a stack to simulate recursion:

def inorder_iterative(root):
    stack = []
    current = root
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        print(current.key, end=" ")
        current = current.right

This approach is useful for handling very deep trees without risking recursion stack overflows.

Inorder Traversal in JavaScript

function inorder(root) {
  let stack = [];
  let current = root;

  while (stack.length || current) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    console.log(current.key);
    current = current.right;
  }
}

Morris Inorder Traversal (No Stack, No Recursion)

Morris traversal is a clever technique that uses threaded binary trees to avoid using stack or recursion:

def morris_inorder(root):
    current = root
    while current:
        if current.left is None:
            print(current.key, end=" ")
            current = current.right
        else:
            pre = current.left
            while pre.right and pre.right != current:
                pre = pre.right

            if pre.right is None:
                pre.right = current
                current = current.left
            else:
                pre.right = None
                print(current.key, end=" ")
                current = current.right

Time Complexity: O(n)
Space Complexity: O(1)
Used in memory-constrained systems

Inorder Traversal Applications

1. Sorting in BSTs

Inorder traversal of a Binary Search Tree yields sorted order.

2. Serialization

Used to encode trees into flat sequences for storage or transfer.

3. Validation

To verify if a binary tree is a BST, check if its inorder traversal is strictly increasing.

4. Expression Trees

Inorder traversal reconstructs infix expressions from binary operator trees.

Check If Inorder Traversal Is Sorted

def is_bst_inorder(root):
    prev = [None]

    def helper(node):
        if not node:
            return True
        if not helper(node.left):
            return False
        if prev[0] is not None and node.key <= prev[0]:
            return False
        prev[0] = node.key
        return helper(node.right)

    return helper(root)

Comparison to Other Traversals

Traversal Type	Order	Use Case
Inorder	Left → Root → Right	Get sorted elements from BST
Preorder	Root → Left → Right	Serialize tree, construct from preorder
Postorder	Left → Right → Root	Delete tree nodes, evaluate expressions
Level Order	Level by level	BFS, shortest path problems

Common Interview Questions

Convert BST to sorted array using inorder traversal
Validate BST using inorder traversal
Find kth smallest element in BST
Recover a corrupted BST using swapped nodes
Implement Morris traversal without recursion or stack

Time and Space Complexity

Operation	Complexity
Time (all variants)	O(n)
Space (recursive)	O(h)
Space (iterative)	O(h)
Space (Morris)	O(1)

Where h is the height of the tree (log n for balanced, n for skewed).

Edge Cases

Empty tree → return nothing
Skewed tree → acts like a linked list
Duplicate values → still printed in order, but BST property may not hold

Real-World Analogy

Imagine reading a book index organized as a tree. Inorder traversal is like scanning all left-side entries alphabetically before reading the current header, and then proceeding to the right-side topics. It’s a systematic, natural order — particularly valuable in sorting tasks.

Summary

Inorder Traversal is a fundamental technique for navigating binary trees, particularly Binary Search Trees. Whether done recursively, iteratively, or using space-efficient methods like Morris traversal, it provides a clean, logical way to access tree nodes in sorted order.

Mastering this technique is not only essential for algorithm interviews and coding challenges, but also critical in building real-world systems like compilers, databases, and search engines that rely on structured, hierarchical data.