Overview
Inorder traversal is a depth-first way to visit every node of a binary tree in the order Left, Root, Right. It fully explores a node's left subtree, then reports the node itself, then explores its right subtree.
Its defining property is that on a Binary Search Tree (BST) inorder traversal produces the keys in ascending sorted order, which makes it the natural way to read a BST out in sequence.
How Inorder Traversal works
- Starting at the root, recursively traverse the entire left subtree first.
- Visit (process) the current node once its left subtree is done.
- Recursively traverse the right subtree.
- The base case is an empty subtree (null), where the recursion simply returns.
When to use it
- Reading the keys of a Binary Search Tree in sorted order without an extra sort.
- Validating that a tree is a correct BST by checking the sequence is strictly increasing.
- Finding the in-order predecessor or successor of a node during BST operations.
Complexity analysis
Inorder traversal visits every node exactly once, so it runs in O(n) time. The recursion stack goes as deep as the tree's height h, using O(h) space — O(log n) for a balanced tree and O(n) for a degenerate, chain-like tree.
Frequently asked questions
Why does inorder traversal give sorted output on a BST?
In a BST every key in the left subtree is smaller than the node and every key in the right subtree is larger. Visiting Left, Root, Right therefore emits keys from smallest to largest.
Can inorder traversal be done without recursion?
Yes. An explicit stack simulates the recursion, and Morris traversal even achieves O(1) extra space by temporarily rewiring null right pointers into threads back to ancestors.