Inorder Traversal
Overview
Inorder Traversal is a specific, highly useful variation of Tree DFS. The name dictates the exact order in which a node is processed relative to its children: Left Child -> Root (Self) -> Right Child.
The algorithm dives deep down the left side until it hits null, then processes the current node, then dives down the right side.
This traversal is incredibly special because when applied to a Binary Search Tree (BST), Inorder Traversal processes the values in perfectly sorted, ascending order. If you ever need to flatten a BST into a sorted array, or validate that a tree actually is a valid BST, Inorder Traversal does the job natively in strict O(N) time with practically zero algorithmic overhead.
Syntax
public class Inorder {
static class TreeNode {
int val; TreeNode left, right;
}
public void inorder(TreeNode root) {
if (root == null) return;
// 1. Go completely down the Left side
inorder(root.left);
// 2. Process the Root (Self)
System.out.print(root.val + " ");
// 3. Go completely down the Right side
inorder(root.right);
}
}Common Pitfalls
- Not accounting for null nodes before recursion. If you don't include
if (root == null) return;, you will trigger a NullPointerException immediately on empty trees. - Mixing up the order of operations. Placing the print statement before the left recursive call accidentally turns this into a Preorder traversal, destroying the sorting properties on a BST.
- Failing to capture state. If you are validating a BST using Inorder, you must keep track of the previously visited node to ensure
previous.val < current.val. Just printing them doesn't help the algorithm validate it.
Interview Questions
Because the mathematical rules of a BST (left is smaller, right is larger) align perfectly with the Left-Root-Right processing order of Inorder traversal. This guarantees that elements are visited in strictly ascending, sorted order.
Perform an Inorder Traversal. Maintain a global or passed-by-reference counter. Every time you process a node (the 'Root' step), increment the counter. When the counter equals K, you have found the Kth smallest element.
Real-World Example
Database Indexing. Databases often use B-Trees or variations of BSTs for indexing columns. When a user runs a SQL query like SELECT * FROM users ORDER BY age ASC, the database engine traverses the age index tree using an Inorder Traversal to instantly stream the rows back to the user in perfectly sorted ascending order.
import java.util.*;
class DBNode { int age; String recordId; DBNode left, right; }
public class DatabaseIndex {
// Fetches all records in ascending order based on the indexed age
public void fetchSortedRecords(DBNode root, List<String> sortedResults) {
if (root == null) return;
fetchSortedRecords(root.left, sortedResults);
// Process self (Ascending order guaranteed by BST property)
sortedResults.add(root.recordId);
fetchSortedRecords(root.right, sortedResults);
}
}Check Your Knowledge
Test your understanding of Inorder Traversal with these quick questions.