Binary Tree Inorder Traversal: Left, Root, Right Explained
Learn binary tree inorder traversal with recursive JavaScript DFS, a BST sorting trace, complexity analysis, and left-root-right intuition.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Inorder traversal delays a node until its left subtree is complete. That one delay creates the sequence left, root, right, and on a binary search tree it produces values in ascending order without sorting them.
It is tempting to remember inorder as “the sorted traversal.” That is only half true. Inorder is defined for every binary tree, but the sorted property comes from the BST invariant: every left-subtree value is smaller than the node and every right-subtree value is larger. On an arbitrary tree, inorder remains deterministic, not necessarily sorted.
The problem
Given a binary tree root, return its values by traversing the left subtree first, then recording the current node, then traversing the right subtree. Null children stop the recursion.
Tree: 2
/ \
1 3
Output: [1, 2, 3]For this example, 1 must be emitted before 2 because it is in the left subtree. The root cannot be recorded when the traversal first reaches it; its left-hand obligation is still unfinished. That “wait, then record” behavior is the whole pattern.
The brute force baseline
A common wrong shortcut is to collect every value and sort the array afterward.
function inorderBySorting(root) {
const values = [];
function collect(node) {
if (!node) return;
values.push(node.val);
collect(node.left);
collect(node.right);
}
collect(root);
return values.sort((a, b) => a - b);
}This does not perform inorder traversal at all. collect is preorder because it pushes before visiting children, and sorting erases the tree's structural order. It happens to return the same values as inorder for a valid BST, but it gives the wrong answer for a general binary tree and adds O(n log n) work.
For example, a root 2 with left child 3 has inorder output [3, 2]; sorting produces [2, 3]. Traversal is about where a value appears relative to its descendants, not about arranging values numerically.
The key insight: postpone the root
Each dfs(node) call is responsible for one subtree. It first descends left until it reaches a null pointer. Only while calls return does it record the nodes that were waiting on the path. After recording a node, it explores that node's right subtree.
The recursive call stack stores the postponed roots for free. When dfs(node.left) is running, the frame for node stays alive, retaining the instruction to append node.val next. This is exactly why inorder iterators use a stack: they need to preserve the same pending path when recursion is unavailable.
On a BST, all nodes in the left subtree are smaller than the root, and all nodes in the right subtree are larger. Inorder fully emits the smaller group, then the root, then the larger group. Applied recursively, that yields ascending values.
The optimal solution
The visualizer's canonical JavaScript solution records a value between two DFS calls. That placement must remain exactly in the middle; moving it above or below both calls changes the traversal.
function inorderTraversal(root) {
const result = [];
function dfs(node) {
if (!node) return;
dfs(node.left);
result.push(node.val);
dfs(node.right);
}
dfs(root);
return result;
}The null guard is more than defensive code. It defines empty subtrees as producing no output, which lets a leaf follow the same three-step rule as any other node: its left call returns, its value is pushed, and its right call returns. No special leaf case is needed.
You can step through it interactively to see nodes remain in-flight while their left branches finish, then enter the result array on the return path.
Walkthrough: BST [4, 2, 6, 1, 3, 5, 7]
The input describes a balanced BST. Starting at 4, the algorithm cannot append the root yet; it keeps moving left through 2 to 1. From there, null calls return and the deferred roots are released in order.
| Step | Active call or return | Operation | result |
|---|---|---|---|
| 1 | dfs(4) | Descend left; 4 waits | [] |
| 2 | dfs(2) | Descend left; 2 waits | [] |
| 3 | dfs(1) | Left is null, so append 1 | [1] |
| 4 | return to dfs(2) | Append 2 after its left subtree | [1, 2] |
| 5 | dfs(3) | Append 3 between null children | [1, 2, 3] |
| 6 | return to dfs(4) | Left subtree is done; append 4 | [1, 2, 3, 4] |
| 7 | traverse 6, then 5 and 7 | Finish the right subtree | [1, 2, 3, 4, 5, 6, 7] |
The table also explains the sorted result without invoking a sorting algorithm. At node 4, every value from its left subtree was emitted first; every value from its right subtree comes afterward. The same statement holds at every smaller subtree.
Complexity
| Approach | Time | Extra space | Why |
|---|---|---|---|
| Collect then sort | O(n log n) | O(n) | Sorting dominates and does not preserve general-tree inorder |
| Recursive inorder DFS | O(n) | O(h) | Each node is visited once; active calls form one root-to-leaf path |
| Iterative inorder DFS | O(n) | O(h) | An explicit stack stores the same postponed ancestors |
The returned result array takes O(n) space in all versions because it contains every node value. O(h) describes extra traversal state. A balanced tree has h near O(log n), while a skewed tree can make h equal n and may overflow a language runtime's recursion limit.
Common mistakes
- Appending before going left. That produces preorder, not inorder.
- Appending after going right. That produces postorder, not inorder.
- Claiming inorder always sorts values. It is sorted only when the input obeys the BST ordering invariant.
- Sorting to imitate traversal. Sorting is slower and loses the structural meaning of left-root-right on non-BST trees.
- Dropping the null check. Leaves make recursive calls on null children; the base case is required for every tree shape.
Where this pattern shows up next
These tree traversals differ only in when the parent is processed, but that timing selects the problem each one solves naturally.
- Binary Tree Preorder Traversal records the parent immediately for root-left-right exploration.
The iterative preorder variant translates root-left-right work into a manual stack. An iterative inorder solution pushes left ancestors until one becomes ready to emit, and postorder waits until both children are processed before it records the parent. They are all the same DFS skeleton with one timing decision moved.
For interview work, say that timing aloud before writing code. “Left, node, right” prevents the most common bug: appending the parent on entry and accidentally implementing preorder. It also clarifies why a stack-based implementation needs a loop that keeps descending left before it pops a node.
FAQ
What is inorder traversal in a binary tree?
Inorder traversal visits every node in the left subtree, then the current node, then every node in the right subtree. The recursive template is dfs(left), process root, dfs(right).
Why does inorder traversal sort a BST?
A valid BST places smaller values in each node's left subtree and larger values in its right subtree. Inorder emits the complete smaller group before the node and the larger group after it, so the recursive result is ascending.
Does inorder traversal sort any binary tree?
No. Inorder follows tree structure, not numeric comparisons. A binary tree that violates BST ordering can produce any left-root-right sequence, including one that is not sorted.
What is the time and space complexity of recursive inorder traversal?
It takes O(n) time because each node is visited once. It uses O(h) auxiliary call-stack space for tree height h, plus O(n) space for the returned result array. A skewed tree has O(n) height.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.