Inorder Traversal, step by step.

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

What is inorder traversal? Left, root, right

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.

How does inorder traversal work? With and without recursion

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.

Inorder traversal pseudocode: recursive and iterative

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.

Inorder traversal example: the stack step by step

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.

Inorder traversal with a stack

All steps as text
  1. Step through the iterative in-order traversal. Use a stack to manage the nodes to be visited.
  2. Start with the root of the tree. Push it onto the stack and apply the next rule. Rule 1: For each node pushed onto the stack, check for a left child. If it exists, push it onto the stack; if not, pop the next node from the stack and visit it.
  3. Push the node (24) onto the stack (according to Rule 1).
  4. Push the node (92) onto the stack (according to Rule 1).
  5. Push the node (1) onto the stack. As this node does not have a left child, according to Rule 1, the next node at the top of the stack needs to be popped and visited.
  6. When visiting nodes, use Rule 2: If a node has a right child, that child needs to be pushed onto the stack, and Rule 1 will then be applied to it. If there is no right child, the next node needs to be popped from the stack and visited.
  7. Pop and visit (92). This node has a right child (9). It needs to be pushed onto the stack (Rule 2).
  8. Push the node (9) onto the stack and check if it has a left child (Rule 1). There is no left child; therefore, the node at the top of the stack is the next one to be popped and visited.
  9. Pop and visit node (9). Again, apply Rule 2 by checking if it has a right child - there is none. Therefore, the next node at the top of the stack needs to be popped and visited.
  10. Pop and visit (24). This node has a right child (11). It needs to be pushed onto the stack (Rule 2).
  11. Push the node (11) onto the stack and check if it has a left child (Rule 1). Since the node (11) has a left child, this left child needs to be pushed onto the stack.
  12. Push the node (84) onto the stack. As this node does not have a left child, according to Rule 1, the next node at the top of the stack needs to be popped and visited.
  13. Pop and visit node (84) and check for the presence of a right child (Rule 2). There is none - therefore, the next node needs to be popped from the stack and visited.
  14. Pop and visit (11). This node has a right child (53). It needs to be pushed onto the stack (Rule 2).
  15. Push the node (53) onto the stack and check if it has a left child (Rule 1). There is no left child; therefore, the node at the top of the stack is the next one to be popped and visited.
  16. Pop and visit node (53). Again, apply Rule 2 by checking if it has a right child - there is none. Therefore, the next node at the top of the stack needs to be popped and visited.
  17. Pop and visit (7). This node has a right child (62). It needs to be pushed onto the stack (Rule 2).
  18. Push the node (62) onto the stack and check if it has a left child (Rule 1). Since the node (62) has a left child, this left child needs to be pushed onto the stack.
  19. Push the node (76) onto the stack (according to Rule 1).
  20. Push the node (72) onto the stack. As this node does not have a left child, according to Rule 1, the next node at the top of the stack needs to be popped and visited.
  21. Pop and visit node (72) and check for the presence of a right child (Rule 2). There is none - therefore, the next node needs to be popped from the stack and visited.
  22. Pop and visit (76). This node has a right child (33). It needs to be pushed onto the stack (Rule 2).
  23. Push the node (33) onto the stack and check if it has a left child (Rule 1). There is no left child; therefore, the node at the top of the stack is the next one to be popped and visited.
  24. Pop and visit node (33). Again, apply Rule 2 by checking if it has a right child - there is none. Therefore, the next node at the top of the stack needs to be popped and visited.
  25. Pop and visit (62). This node has a right child (13). It needs to be pushed onto the stack (Rule 2).
  26. Push the node (13) onto the stack and check if it has a left child (Rule 1). Since the node (13) has a left child, this left child needs to be pushed onto the stack.
  27. Push the node (32) onto the stack. As this node does not have a left child, according to Rule 1, the next node at the top of the stack needs to be popped and visited.
  28. Pop and visit node (32) and check for the presence of a right child (Rule 2). There is none - therefore, the next node needs to be popped from the stack and visited.
  29. Pop and visit (13). This node has a right child (83). It needs to be pushed onto the stack (Rule 2).
  30. Push the node (83) onto the stack and check if it has a left child (Rule 1). There is no left child; therefore, the node at the top of the stack is the next one to be popped and visited.
  31. Pop the node (83) from the stack and visit it. If this node does not have a right child and the stack is empty, it indicates that all nodes have already been visited. The traversal is complete.
  32. Inorder visited the 15 nodes in the order 1, 92, 9, 24, 84, 11, 53, 7, 72, 76, 33, 62, 32, 13, 83: each node after its left subtree and before its right subtree.
Inorder traversal with a stack. Last step: Inorder visited the 15 nodes in the order 1, 92, 9, 24, 84, 11, 53, 7, 72, 76, 33, 62, 32, 13, 83: each node after its left subtree and before its right subtree.

Inorder traversal of a binary search tree (BST): sorted keys and the BST check

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.

Why iterative inorder is harder than iterative preorder

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 vs preorder vs postorder, level order and DFS

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.

What does an inorder traversal of a binary search tree produce?

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.

Which node does inorder traversal visit first?

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.

Can a binary tree be rebuilt from its inorder traversal?

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.

Inorder traversal time and space complexity

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.

Inorder traversal in Python, Java and C++

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++.

Applications of inorder traversal

  • Sorted output: a binary search tree's keys in order, or only those in a range, skipping the subtrees outside it.
  • The kth smallest key of a binary search tree: stop after k visits.
  • Inorder successor: the node visited next. In a binary search tree it holds the smallest key in the right subtree when there is one, else it is the nearest ancestor whose left subtree holds the node. Deleting a node with two children moves the successor into its place.
  • Infix expressions: inorder writes an expression tree in infix form; the tree of (3 + 4) × 2 gives 3 + 4 × 2 unless its subtrees get brackets.

One tree here.
Your own in the app.

In VisiGrab, inorder has a message for every push and pop, and the tree it walks can be one you build.

Your own binary tree

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.

Three more traversals

Preorder, postorder and level order walk the same default tree, each in its own color, with one stack, two stacks and a queue.

Why a search tree comes out sorted

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).

Python, Java and C++

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.

Quiz

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.

Search trees to build

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.

Walk a binary tree
left, node, right.

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