Inorder traversal visits every node of a binary tree once, at each node taking the left subtree first, then the node, then the right subtree, so a binary search tree yields its keys in ascending order. This page explains how it works, with a step-by-step animation of the stack-based version from the VisiGrab app.
// how inorder traversal works
Inorder traversal, also written in-order or in order, visits every node of a binary tree once: at each node, first the whole left subtree, then the node itself, then the whole right subtree (left, node, right, or LNR). So the walk starts at the leftmost node, reached by following left links down from the root, and ends at the rightmost.
Inorder is mainly a binary-tree order: a node has exactly one place between its two subtrees. A node with three or more children has several such places, so general trees have no single standard inorder; a B-tree, whose keys sit between its children, does have one.
The recursive version follows the definition: traverse the left subtree, visit the node, traverse the right subtree, and stop at an empty link.
The iterative version, which the app animates, keeps the nodes still waiting for their visit on a stack. Starting with the root as the current node, it repeats three steps.
1. Go left: while there is a current node, push it onto the stack and move to its left child. The app calls this Rule 1.
2. Pop and visit: when there is no current node, pop the top node and visit it. Its whole left subtree has already been visited.
3. Go right: make the popped node's right child the current node and go back to step 1; the app calls this Rule 2. With no right child there is no current node, so step 2 pops the next one.
The walk ends when there is no current node and the stack is empty. The stack holds the nodes of the current path whose left subtree is still being walked, the deepest on top.
The app's code shows both versions; the names below drop the Traverse suffix of its listings, and visit prints the node's key. In pseudocode:
recursiveInOrder(node)
if node is none
return
recursiveInOrder(node.left)
node.visit()
recursiveInOrder(node.right)
iterativeInOrder(root)
stack = empty stack
node = root
while stack is not empty
or node is not none
if node is not none
stack.push(node)
node = node.left
else
node = stack.pop()
node.visit()
node = node.right
recursiveInOrder keeps no stack of its own: the call stack holds one open call for each node on the path from the root. In iterativeInOrder, node is the current node: the if branch is step 1, and the else branch, which pops, visits and sets node = node.right, is steps 2 and 3. The loop stops only when the stack is empty and node is none.
The player below runs the app's iterative inorder traversal on its default 15-node tree, with the stack on the right. It visits every node with 15 pushes and 15 pops, from the leftmost, 1, to the rightmost, 83. The keys do not come out in ascending order, because this tree is not a binary search tree.
In a binary search tree, every key in a node's left subtree is smaller than the node's key and every key in its right subtree is larger. Inorder emits the left subtree, the node, then the right subtree, so at every node the smaller keys come out before it and the larger ones after it: the whole sequence ascends. The traversal itself never compares keys.
That gives a test: with distinct keys, a binary tree is a binary search tree exactly when each key in its inorder sequence is larger than the one before. Checking each node against its two children alone is not enough, as the rule covers whole subtrees. Reverse inorder, right subtree first, gives descending order.
Iterative preorder visits a node as soon as it pops it, then pushes its right child and its left child. Inorder cannot visit a node on first reaching it, as its left subtree must come out first. So the node waits on the stack while the walk runs down the left links, and is visited when it is popped on the way back. One stack still suffices; the app's iterative postorder uses two.
Inorder is one of the three depth-first orders, which differ only in when a node is visited relative to its two subtrees. A depth-first search from the root, left child first, lists the nodes in preorder when it records each one on first reaching it and in postorder when it records each one on leaving it for good; inorder's moment, between the two subtrees, has no counterpart in a graph, whose neighbors are not split into left and right. Level order goes level by level, with a queue.
The tree's keys in ascending order: each node comes out after the smaller keys of its left subtree and before the larger keys of its right subtree. The section on inorder traversal of a binary search tree shows how this also tests whether a tree is one.
The leftmost node, reached by following left links down from the root until a node has no left child. It need not be a leaf: it may have a right subtree, which comes next.
No, not from inorder alone: different trees share one inorder sequence, as all binary search trees of the same keys do. With distinct keys, inorder together with preorder or postorder fixes the tree: the first key of the preorder, or the last of the postorder, is the root, and its place in the inorder splits the left subtree's keys from the right subtree's.
Both versions take O(n) time for n nodes: the iterative one pushes and pops each node once, and the recursive one makes 2n + 1 calls, one per node and one per empty link. Extra space is O(h) for a tree of height h, counted in links: the stack holds at most the h + 1 nodes of one path, and recursion nests h + 2 calls deep, counting the call on an empty link. That is O(log n) for a balanced tree and O(n) for a chain; the player's tree has height 3, and its stack peaks at four nodes.
Morris traversal gets the same order in O(1) extra space by temporarily turning empty right links into links back up the tree; the app does not cover it.
The app's listings give both versions in all three languages. Recursion nests one call per level, so a deep, chain-shaped tree can exhaust the call stack; the iterative version has no such limit.
Note
Python's default recursion limit, about 1,000 nested calls, makes recursive inorder raise RecursionError on a chain about that tall. Java and C++ go much deeper before the thread's stack runs out.
The full source code is on GitHub, in Python, Java and C++.
// in the app
In VisiGrab, inorder has a message for every push and pop, and the tree it walks can be one you build.
Custom opens a tree editor on a four-level, 15-node template: Set gives a node a key from 0 to 99, and Delete removes a node with its subtree. With search-tree keys, inorder comes out sorted.
Preorder, postorder and level order walk the same default tree, each in its own color, with one stack, two stacks and a queue.
The info dialog gives the left, node, right order, explains why a binary search tree yields its keys sorted, says a sorted inorder proves a tree is one, and puts both versions at O(n).
The recursive and the iterative version in each language, with a note on why the iterative one heads for the leftmost node first, unlike preorder's. A link opens the full source on GitHub.
Eight questions with every option explained: the order, why a search tree comes out sorted and how that tests one, where the stack walk goes first and after a visit, why it is harder than preorder's, and a tree that is not a search tree.
Binary Search Tree, AVL Tree and Red-Black Tree build the trees whose inorder is sorted, one insertion or deletion at a time. The Binary Search Tree code replaces a deleted node that has two children with its inorder successor.
// build your own
Download VisiGrab to step through inorder on its default tree, then build a tree of your own and walk it again.
Inorder traversal is one of 30+ topics. See them all