Inorder Traversal

Overview

Inorder Traversal is a specific type of Tree DFS. The order of operations is strictly: Left Child, Current Node, Right Child. The most critical property of Inorder Traversal is that when applied to a Binary Search Tree (BST), it always returns the elements in completely sorted (ascending) order.

Syntax

By visiting the smaller elements (left) before the current element, and then the larger elements (right), a BST is flattened into a sorted list.

Left, Root, Right

java

public void inorder(TreeNode root) {
    if (root == null) return;
    
    inorder(root.left);         // 1. Left
    System.out.print(root.val); // 2. Root (Process)
    inorder(root.right);        // 3. Right
}

Common Pitfalls

Mixing up the order. Inorder means the 'Root' is processed IN the middle of its children.

Interview Tips

Inorder Traversal on a BST = Sorted Array. This is a very common trick in interview questions.

Real-World Example

Converting a BST back into a sorted array or finding the Kth smallest element.

example

java

// Kth smallest element in a BST can be found by keeping a counter during Inorder traversal.

Take Java Quiz