Loading learning content...
Imagine reading a book in a language that goes from left to right. You naturally process things in order: what's on the left, then the middle, then the right. Inorder traversal captures this same intuition for trees: explore everything to the left, then process the current node, then explore everything to the right.
But here's where inorder becomes truly special: when applied to a Binary Search Tree (BST), inorder traversal visits nodes in ascending sorted order. This isn't a coincidence—it's a direct consequence of the BST property. This single fact makes inorder traversal one of the most important algorithms in computer science, enabling efficient sorted iteration, range queries, and BST validation.
By the end of this page, you will master inorder traversal—understanding its algorithm, implementing it recursively and iteratively, and most importantly, understanding its deep connection to Binary Search Trees. You'll see why "process in the middle" unlocks powerful capabilities for ordered data.
Inorder traversal follows this precise rule:
For each node, do these three things in this exact order:
The key insight: the current node is visited between its left and right subtrees—hence "in-order" (in the middle of the order). For binary trees in general, this produces a specific but seemingly arbitrary order. For BSTs, it produces something magical: sorted output.
12345678910111213141516171819202122
INORDER TRAVERSAL ALGORITHM═══════════════════════════════════════════════════════════════ Input: Root node of a binary tree (or null) Output: Sequence of node values in inorder Procedure INORDER(node): 1. If node is null: Return (base case: nothing to visit) 2. INORDER(node.left) ← First, traverse left subtree 3. VISIT(node) ← Then, process current node 4. INORDER(node.right) ← Finally, traverse right subtree ═══════════════════════════════════════════════════════════════ Mnemonic: "LVR" — Left, Visit, Right The V (Visit) comes IN the middle, hence "IN-order" (Think: the root value is IN-between left and right in output)The name reflects the position of Visit: In the middle, between left and right subtree traversals. Another way to remember: for a BST, inorder produces values "in order" (sorted). The naming is both descriptive of the algorithm structure AND its most important application.
The recursive implementation is beautifully symmetrical. Notice how the visit operation sits exactly between the two recursive calls—a visual representation of "in the middle":
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
/** * Binary tree node definition */interface TreeNode<T> { value: T; left: TreeNode<T> | null; right: TreeNode<T> | null;} /** * Inorder traversal - recursive implementation * * Time Complexity: O(n) - visits each node exactly once * Space Complexity: O(h) - recursive call stack depth equals tree height * * For BSTs: produces values in ASCENDING sorted order! * * @param root - The root of the tree (or subtree) * @param result - Array to collect values (accumulator pattern) * @returns Array of values in inorder sequence */function inorderTraversal<T>( root: TreeNode<T> | null, result: T[] = []): T[] { // Base case: empty tree/subtree if (root === null) { return result; } // Step 1: LEFT - Traverse left subtree first inorderTraversal(root.left, result); // Step 2: VISIT - Process current node (the "IN" in inorder) result.push(root.value); // Step 3: RIGHT - Traverse right subtree last inorderTraversal(root.right, result); return result;} // ─────────────────────────────────────────────────────────────// Example with a BST (values are sorted!)// ───────────────────────────────────────────────────────────── /* * BST structure: * 4 * / \ * 2 6 * / \ / \ * 1 3 5 7 * * BST Property: left < root < right at every node */ const bst: TreeNode<number> = { value: 4, left: { value: 2, left: { value: 1, left: null, right: null }, right: { value: 3, left: null, right: null }, }, right: { value: 6, left: { value: 5, left: null, right: null }, right: { value: 7, left: null, right: null }, },}; console.log(inorderTraversal(bst));// Output: [1, 2, 3, 4, 5, 6, 7] ← SORTED! 🎉// This is NOT a coincidence—it's guaranteed for any BSTCompare this to preorder: the ONLY difference is the position of result.push(). In preorder, it's before both recursive calls. In inorder, it's between them. This tiny change produces fundamentally different output—especially for BSTs where inorder gives sorted order but preorder does not.
This is perhaps the most important insight about inorder traversal. Let's understand why inorder traversal of a BST produces sorted output—not just accept that it does.
The BST Property: For every node in a BST:
The Inorder Order:
The Magic: Since left < current < right, and we visit left, then current, then right, we visit smaller values first, then the middle value, then larger values. This is exactly ascending order!
1234567891011121314151617181920212223242526272829303132333435363738394041
WHY BST INORDER = SORTED ORDER═══════════════════════════════════════════════════════════════════════════ BST Property at each node: Inorder visits: ───────────────────────── ─────────────── left subtree < node left subtree first node < right subtree node in middle right subtree last ═══════════════════════════════════════════════════════════════════════════ Example BST: 50 / \ 30 70 / \ / \ 20 40 60 80 Analysis at root (50):• Left subtree {20, 30, 40} — all values < 50• Right subtree {60, 70, 80} — all values > 50• Inorder: [left subtree] + [50] + [right subtree] = [20, 30, 40] + [50] + [60, 70, 80] = [20, 30, 40, 50, 60, 70, 80] ← SORTED! The same logic applies recursively:• Inorder of left subtree {20, 30, 40} is [20, 30, 40] (sorted)• Inorder of right subtree {60, 70, 80} is [60, 70, 80] (sorted)• Combining: small sorted + middle + large sorted = fully sorted ═══════════════════════════════════════════════════════════════════════════ THEOREM: Inorder traversal of a BST produces values in ascending order. PROOF (by induction):Base case: Empty tree → empty sequence (trivially sorted)Inductive step: Assume inorder(left) and inorder(right) are sorted. - All values in inorder(left) < root.value (BST property) - All values in inorder(right) > root.value (BST property) - inorder(tree) = inorder(left) ⊕ [root.value] ⊕ inorder(right) - This is sorted sequence: (small sorted) + (middle) + (large sorted) ∎Inorder traversal of a general binary tree does NOT produce sorted output. The sorted property depends entirely on the BST ordering invariant. For non-BST trees, inorder still produces a deterministic sequence, but it won't be sorted. The BST structure is what makes the magic happen.
Let's trace through inorder traversal step by step. Pay attention to how we go all the way left before visiting anything:
Sample BST:
4
/
2 6
/
1 3
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748
INORDER TRAVERSAL EXECUTION TRACE═══════════════════════════════════════════════════════════════════════════ BST: 4 / \ 2 6 / \ 1 3 ═══════════════════════════════════════════════════════════════════════════Step Call Stack Action Result So Far═══════════════════════════════════════════════════════════════════════════ 1 inorder(4) Call inorder(2) [] 2 └─inorder(2) Call inorder(1) [] 3 └─inorder(1) Call inorder(null) [] 4 └─null Return (base case) [] 5 └─inorder(1) VISIT 1 ★ [1] 6 └─inorder(1) Call inorder(null) [1] 7 └─null Return (base case) [1] 8 └─inorder(1) Return [1] 9 └─inorder(2) VISIT 2 ★ [1, 2]10 └─inorder(2) Call inorder(3) [1, 2]11 └─inorder(3) Call inorder(null) [1, 2]12 └─null Return (base case) [1, 2]13 └─inorder(3) VISIT 3 ★ [1, 2, 3]14 └─inorder(3) Call inorder(null) [1, 2, 3]15 └─null Return (base case) [1, 2, 3]16 └─inorder(3) Return [1, 2, 3]17 └─inorder(2) Return [1, 2, 3]18 inorder(4) VISIT 4 ★ [1, 2, 3, 4]19 inorder(4) Call inorder(6) [1, 2, 3, 4]20 └─inorder(6) Call inorder(null) [1, 2, 3, 4]21 └─null Return (base case) [1, 2, 3, 4]22 └─inorder(6) VISIT 6 ★ [1, 2, 3, 4, 6]23 └─inorder(6) Call inorder(null) [1, 2, 3, 4, 6]24 └─null Return (base case) [1, 2, 3, 4, 6]25 └─inorder(6) Return [1, 2, 3, 4, 6]26 inorder(4) Return [1, 2, 3, 4, 6]═══════════════════════════════════════════════════════════════════════════ FINAL RESULT: [1, 2, 3, 4, 6] ← SORTED! KEY OBSERVATIONS:★ Visit operations happen BETWEEN left and right explorations• Node 4 (root) is visited in the MIDDLE of the sequence• Leftmost node (1) is visited FIRST• We descend all the way left before visiting anything• Each node is visited after its left subtree, before its right subtreeNotice that the first VISIT doesn't happen until step 5—after going all the way to the leftmost node. This "go all the way left first" pattern is characteristic of inorder and is key to the iterative implementation we'll see next.
The iterative inorder traversal is more complex than iterative preorder. We need to simulate the behavior of going all the way left, then processing, then going right. This requires carefully tracking our position in the tree.
The key insight: use the stack to remember which nodes we still need to process after returning from the left subtree.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
/** * Inorder traversal - iterative implementation using explicit stack * * Algorithm: * 1. Go all the way left, pushing nodes onto stack * 2. When can't go left, pop and visit the node * 3. Move to right child and repeat * * The stack holds nodes we've seen but not yet visited * (we went left past them; now we need to come back) */function inorderIterative<T>(root: TreeNode<T> | null): T[] { const result: T[] = []; const stack: TreeNode<T>[] = []; let current: TreeNode<T> | null = root; // Continue while we have nodes to process // Either current is not null (we can go somewhere) // Or stack is not empty (we have nodes to return to) while (current !== null || stack.length > 0) { // Phase 1: Go all the way LEFT // Push each node onto stack as we pass it while (current !== null) { stack.push(current); current = current.left; } // Phase 2: Process (we've gone as far left as possible) // Pop the node - this is the next in inorder sequence current = stack.pop()!; result.push(current.value); // VISIT // Phase 3: Move RIGHT // Now explore the right subtree (repeat the process) current = current.right; } return result;} // ─────────────────────────────────────────────────────────────// Detailed state trace// ───────────────────────────────────────────────────────────── /* * BST: 4 * / \ * 2 6 * / \ * 1 3 * * State transitions: * * current=4 stack=[] → push 4, go left * current=2 stack=[4] → push 2, go left * current=1 stack=[4,2] → push 1, go left * current=null stack=[4,2,1] → can't go left, pop 1 * VISIT 1 Result: [1] * current=null stack=[4,2] → 1's right is null, pop 2 * VISIT 2 Result: [1,2] * current=3 stack=[4] → 2's right is 3, go left from 3 * current=null stack=[4,3] → push 3, 3's left null, pop 3 * VISIT 3 Result: [1,2,3] * current=null stack=[4] → 3's right null, pop 4 * VISIT 4 Result: [1,2,3,4] * current=6 stack=[] → 4's right is 6, go left from 6 * current=null stack=[6] → push 6, 6's left null, pop 6 * VISIT 6 Result: [1,2,3,4,6] * current=null stack=[] → 6's right null, stack empty, DONE * * Final: [1, 2, 3, 4, 6] ✓ */The outer while has two conditions: current !== null OR stack not empty. We need both because: (1) current being null doesn't mean we're done—there might be nodes on the stack to return to. (2) Empty stack doesn't mean we're done—we might still be traversing right subtrees. Only when BOTH are exhausted are we truly finished.
Both recursive and stack-based iterative approaches use O(h) space. Is it possible to do inorder traversal with O(1) extra space? Remarkably, yes—using Morris Traversal, an ingenious algorithm that temporarily modifies the tree structure.
The idea: Instead of using a stack to remember where to return, we create temporary "threaded" links from nodes back to their inorder successors. These links let us find our way back up the tree without storing anything on a stack.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061
/** * Morris Inorder Traversal - O(1) space complexity! * * Key Idea: Temporarily create "thread" links from nodes to their * inorder predecessors, allowing us to return without a stack. * * Time Complexity: O(n) - each edge traversed at most 3 times * Space Complexity: O(1) - no stack, no recursion! * * Note: Modifies tree temporarily, restores it before returning. * Not safe for concurrent access during traversal. */function morrisInorder<T>(root: TreeNode<T> | null): T[] { const result: T[] = []; let current = root; while (current !== null) { if (current.left === null) { // No left subtree: visit current, move right result.push(current.value); current = current.right; } else { // Has left subtree: find inorder predecessor let predecessor = current.left; // Predecessor is rightmost node in left subtree // (but stop if we find our thread back to current) while (predecessor.right !== null && predecessor.right !== current) { predecessor = predecessor.right; } if (predecessor.right === null) { // First time here: create thread and go left predecessor.right = current; // Create thread current = current.left; } else { // Second time here: thread exists, we're returning predecessor.right = null; // Remove thread (restore tree) result.push(current.value); // Visit current current = current.right; } } } return result;} /* * How threads work: * * Original: 4 With thread: 4 * / \ / \ * 2 6 2 6 * / \ / \ * 1 3 1 3 * \ * → 4 (thread!) * * The thread from 3 to 4 lets us return to 4 after visiting 3, * without needing the stack to remember 4 was waiting. */Morris is rarely needed in practice—O(h) space is usually acceptable. Use it when: (1) memory is extremely constrained, (2) the tree is very deep and stack overflow is a concern, or (3) you need to demonstrate advanced algorithm knowledge. For interviews, mention it as an optimization but implement the simpler stack version unless specifically asked.
Inorder traversal's sorted property for BSTs makes it indispensable for many operations:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546
/** * Find k-th smallest element in a BST using inorder traversal * * Since inorder visits BST nodes in ascending order, * the k-th node we visit is the k-th smallest! */function kthSmallest(root: TreeNode<number> | null, k: number): number | null { let count = 0; let result: number | null = null; function inorder(node: TreeNode<number> | null): void { if (node === null || result !== null) { return; // Base case or already found } // LEFT inorder(node.left); // VISIT - this is where we count and check count++; if (count === k) { result = node.value; return; // Early exit - no need to continue } // RIGHT inorder(node.right); } inorder(root); return result;} /* * BST: 5 * / \ * 3 6 * / \ * 2 4 * / * 1 * * k=1: returns 1 (smallest) * k=3: returns 3 (third smallest) * k=6: returns 6 (sixth smallest, which is largest) */Just as preorder produces prefix notation, inorder traversal of expression trees produces infix notation—the standard mathematical notation we use daily where operators appear between operands (like 3 + 4).
However, there's a catch: infix notation requires parentheses to preserve operator precedence. The traversal must add parentheses around subexpressions to maintain correctness.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859
/** * Generate fully-parenthesized infix notation from expression tree * Uses inorder traversal: operand OPERATOR operand */interface ExprNode { value: string; left: ExprNode | null; right: ExprNode | null;} function toInfix(root: ExprNode | null): string { if (root === null) { return ""; } // Leaf node (operand) - no parentheses needed if (root.left === null && root.right === null) { return root.value; } // Internal node (operator) - inorder with parentheses const leftExpr = toInfix(root.left); // LEFT const operator = root.value; // VISIT (root) const rightExpr = toInfix(root.right); // RIGHT // Wrap in parentheses to preserve structure return `(${leftExpr} ${operator} ${rightExpr})`;} // Expression tree for: (3 + 4) * (5 - 2)const expressionTree: ExprNode = { value: "*", left: { value: "+", left: { value: "3", left: null, right: null }, right: { value: "4", left: null, right: null }, }, right: { value: "-", left: { value: "5", left: null, right: null }, right: { value: "2", left: null, right: null }, },}; console.log(toInfix(expressionTree));// Output: "((3 + 4) * (5 - 2))" /* * Expression Tree: * * * / \ * + - * / \ / \ * 3 4 5 2 * * Inorder: 3, +, 4, *, 5, -, 2 → with parens: ((3+4)*(5-2)) * Preorder: * + 3 4 - 5 2 (prefix - no parens needed) * Postorder: 3 4 + 5 2 - * (postfix - no parens needed) */Unlike prefix and postfix, infix notation is ambiguous without parentheses. '3+45' could mean (3+4)5 or 3+(45). Prefix (+345) and postfix (34+5*) are unambiguous because the structure is encoded in the order. This is why computers often convert infix to postfix for evaluation.
A powerful application of iterative inorder traversal is building a BST Iterator—an object that allows you to step through BST elements one at a time in sorted order, without computing the entire traversal upfront.
This is essential when:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485
/** * BST Iterator - iterate through BST in sorted order, one node at a time * * This is essentially "controlled" inorder traversal where the caller * decides when to advance to the next element. * * Time Complexity: * - next(): O(h) worst case, but O(1) amortized over all calls * - hasNext(): O(1) * Space Complexity: O(h) for the stack */class BSTIterator<T> { private stack: TreeNode<T>[] = []; constructor(root: TreeNode<T> | null) { // Initialize by going all the way left this.pushAllLeft(root); } /** * Push node and all left descendants onto stack * This is the "go all the way left" phase of inorder */ private pushAllLeft(node: TreeNode<T> | null): void { while (node !== null) { this.stack.push(node); node = node.left; } } /** * Returns true if there are more elements */ hasNext(): boolean { return this.stack.length > 0; } /** * Returns the next smallest element */ next(): T { // Pop the next smallest (leftmost unvisited) const node = this.stack.pop()!; // If it has a right subtree, next smallest could be there // Go all the way left from the right child if (node.right !== null) { this.pushAllLeft(node.right); } return node.value; }} // ─────────────────────────────────────────────────────────────// Usage example// ───────────────────────────────────────────────────────────── /* * BST: 7 * / \ * 3 15 * / \ * 9 20 */ const bstRoot: TreeNode<number> = { value: 7, left: { value: 3, left: null, right: null }, right: { value: 15, left: { value: 9, left: null, right: null }, right: { value: 20, left: null, right: null }, },}; const iterator = new BSTIterator(bstRoot); console.log(iterator.next()); // 3console.log(iterator.next()); // 7console.log(iterator.hasNext()); // trueconsole.log(iterator.next()); // 9console.log(iterator.next()); // 15console.log(iterator.next()); // 20console.log(iterator.hasNext()); // falseThe BST Iterator is LeetCode problem #173 and frequently appears in interviews. It tests understanding of iterative inorder traversal, stack usage, and iterator design patterns. Practice implementing it from scratch without looking at the solution.
Inorder traversal is arguably the most important traversal for practical programming due to its deep connection with Binary Search Trees. Let's consolidate what we've learned:
When to choose inorder:
What's next:
We've covered preorder (Root → Left → Right) and inorder (Left → Root → Right). The final DFS traversal is Postorder (Left → Right → Root). You'll see why processing children before parents is essential for problems like tree deletion, height calculation, and postfix expression evaluation.
You now understand inorder traversal deeply—from algorithm to implementation to the critical BST connection. You can implement it recursively, iteratively, and even with O(1) space using Morris. Most importantly, you understand WHY inorder produces sorted output for BSTs. This knowledge is fundamental for tree-based problem solving.