Back to All Algorithms
In-order Traversal
Category: Tree / Graph | Time: O(n) | Space: O(h)
Visualization
Visual representation of the data structure
About In-order Traversal
A tree traversal method that visits nodes in the order: left child, root, right child. For a Binary Search Tree, this traversal visits nodes in ascending order.
Code Editor
The code is for reference. Editing it won't affect the visualization.
1 2 3 4 5 6 7 8 9 10 11 12 13
Variable State
{
"status": "starting traversal"
}In-order Traversal: How It Works
Last updated October 28, 2026
Overview
In-order traversal visits a binary tree in the order left subtree, then the node itself, then the right subtree. It is a depth-first traversal: it goes as far left as possible before visiting anything, then works its way back up.
Its most important property is that, on a binary search tree, it visits keys in ascending order. That makes it the standard way to print a BST in sorted order, to check whether a tree is a valid BST, or to find the k-th smallest element.
The default tree has 10 at the root, 5 and 15 as its children, and 2, 7, 12 and 18 as leaves. In-order traversal visits 2, 5, 7, 10, 12, 15, 18 — sorted, because the default tree is a valid BST.
Step by step
- If the current node is null, return.
- Recursively traverse the left subtree.
- Visit the current node (record or print its value).
- Recursively traverse the right subtree.
Complexity
| Case | Cost | Why |
|---|---|---|
| Time | O(n) | Every node is visited exactly once. |
| Space (balanced tree) | O(log n) | The recursion stack holds one frame per level. |
| Space (skewed tree) | O(n) | A tree shaped like a linked list is n levels deep. |
When to use it
- Getting the keys of a BST in sorted order.
- Validating a BST: the in-order sequence must be strictly increasing.
- Finding the k-th smallest element, or the in-order successor of a node.
Common mistakes
- Very deep trees can overflow the call stack; an iterative version with an explicit stack avoids this.
- In-order alone cannot reconstruct a tree; you need it together with pre-order or post-order.
- On a tree that is not a BST, the output is not sorted — it simply reflects the tree's shape.
Worked Example: In-order Traversal Dry Run
Generated from the same trace that drives the visualizer above, using the default input.
A dry run is the best way to check your understanding of In-order Traversal: follow each row, predict the next one, and compare. The run below takes 60 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.
- Input
- Binary tree (see the input box above)
- Result
- final_path = [2, 5, 7, 10, 12, 15, 18]
| Step | Line | What happens |
|---|---|---|
| 1 | 1 | status = starting traversal |
| 3 | 4 | from_node = 10, action = traversing left |
| 5 | 4 | from_node = 5, action = traversing left |
| 7 | 4 | from_node = 2, action = traversing left |
| 9 | 3 | node = is null, action = return |
| 10 | 7 | current_node = 2, action = visiting node |
| 12 | 10 | from_node = 2, action = traversing right |
| 14 | 3 | node = is null, action = return |
| 15 | 12 | finished_subtree_at = 2, action = return |
| 16 | 7 | current_node = 5, action = visiting node |
| 18 | 10 | from_node = 5, action = traversing right |
| 20 | 4 | from_node = 7, action = traversing left |
| 22 | 3 | node = is null, action = return |
| 23 | 7 | current_node = 7, action = visiting node |
| 25 | 10 | from_node = 7, action = traversing right |
| 27 | 3 | node = is null, action = return |
| 28 | 12 | finished_subtree_at = 7, action = return |
| 29 | 12 | finished_subtree_at = 5, action = return |
| 30 | 7 | current_node = 10, action = visiting node |
| 32 | 10 | from_node = 10, action = traversing right |
| 34 | 4 | from_node = 15, action = traversing left |
| 36 | 4 | from_node = 12, action = traversing left |
| 38 | 3 | node = is null, action = return |
| 39 | 7 | current_node = 12, action = visiting node |
| 41 | 10 | from_node = 12, action = traversing right |
| 43 | 3 | node = is null, action = return |
| 44 | 12 | finished_subtree_at = 12, action = return |
| 45 | 7 | current_node = 15, action = visiting node |
| 47 | 10 | from_node = 15, action = traversing right |
| 49 | 4 | from_node = 18, action = traversing left |
| 51 | 3 | node = is null, action = return |
| 52 | 7 | current_node = 18, action = visiting node |
| 54 | 10 | from_node = 18, action = traversing right |
| 56 | 3 | node = is null, action = return |
| 57 | 12 | finished_subtree_at = 18, action = return |
| 58 | 12 | finished_subtree_at = 15, action = return |
| 59 | 12 | finished_subtree_at = 10, action = return |
| 60 | 15 | final_path = [2, 5, 7, 10, 12, 15, 18] |
Frequently Asked Questions
About In-order Traversal
What is Tree Traversal?
Tree traversal (also known as tree search) is a form of graph traversal and refers to the process of visiting (checking and/or updating) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited.
What is In-order Traversal?
In-order traversal is a depth-first traversal method for binary trees. The order is: traverse the Left subtree, visit the Root, then traverse the Right subtree. For a Binary Search Tree, an in-order traversal visits the nodes in ascending sorted order, which is a key property.
What is the difference between Breadth-First Search (BFS) and Depth-First Search (DFS)?
Breadth-First Search (BFS) explores neighbor nodes first, level by level. It uses a queue to keep track of nodes to visit. Depth-First Search (DFS), which includes in-order, pre-order, and post-order, explores as far as possible along each branch before backtracking.
What is the time complexity for In-order traversal?
The time complexity is O(n), where n is the number of nodes in the tree, because every node is visited exactly once.
What is the space complexity for In-order traversal?
The space complexity is O(h), where h is the height of the tree. This is due to the space required for the recursion stack. In the worst case (a skewed tree), this can be O(n), and in the best case (a balanced tree), it is O(log n).
Can In-order traversal be done iteratively?
Yes, an iterative version can be implemented using an explicit stack. The process involves pushing nodes onto the stack as you go left, and then popping a node, visiting it, and moving to its right child.
Where can I learn more?
You can find a more detailed explanation on GeeksforGeeks.