Preorder Traversal
Visits the root first, then recursively traverses left and right subtrees.
Recursively traverses the left subtree, visits the root, then the right subtree.
Inorder traversal visits each node in a binary tree in the order: left subtree, root, right subtree. For a Binary Search Tree (BST), this produces nodes in sorted ascending order -- a property that makes inorder traversal one of the most practically important tree traversal methods. The term "inorder" reflects that the root is visited in between its two subtrees.
For a BST with root 10, left subtree containing 5 and 7, and right subtree containing 15 and 20, inorder visits: 5, 7, 10, 15, 20 -- perfectly sorted. This happens because the BST property guarantees that all left descendants are smaller and all right descendants are larger than any given node, and inorder traversal respects exactly that ordering.
Consider a concrete seven-node BST: root 8, left child 3 (with children 1 and 6, where 6 has children 4 and 7), right child 10 (with right child 14, which has left child 13). Inorder traversal yields: 1, 3, 4, 6, 7, 8, 10, 13, 14. The algorithm dives as deep left as possible, visits that leaf, backtracks to the parent, then explores the right subtree -- a pattern that naturally extracts values in ascending order.
The iterative implementation uses a stack. Push nodes while going left. When you cannot go further left, pop a node, visit it, then move to its right child and repeat. This mirrors the recursive call stack explicitly and is useful when recursion depth could cause a stack overflow.
| Case | Time | Space |
|---|---|---|
| All cases | O(n) | O(h) where h = tree height |
Every node is visited exactly once. The space is determined by the maximum depth of the recursion stack (or explicit stack), which equals the tree height h. For a balanced BST, h = O(log n). For a completely skewed tree (essentially a linked list), h = O(n).
The defining characteristic of inorder traversal on a BST is that it yields elements in sorted order. This property is not merely convenient -- it is the theoretical basis for several important algorithms. BST validation works by performing an inorder traversal and checking that each value is strictly greater than the previous one. If any value is out of order, the tree violates the BST property. Finding the kth smallest element in a BST reduces to performing an inorder traversal and stopping at the kth node visited. Converting a BST to a sorted array or sorted linked list is a direct application of inorder traversal.
In expression trees, where internal nodes represent operators and leaves represent operands, inorder traversal produces infix notation -- the standard mathematical notation humans use, such as 3 + 5 or (a * b) + c. However, inorder traversal alone does not produce parentheses, so the output may be ambiguous without additional logic to insert parentheses based on operator precedence. This subtlety makes inorder traversal of expression trees more nuanced than it first appears.
An advanced technique called Morris traversal, developed by Joseph Morris in 1979, performs inorder traversal in O(n) time and O(1) space by temporarily modifying the tree structure using threaded pointers. It creates temporary links from the rightmost node of each left subtree back to the current node, effectively threading the tree so that no stack is needed. After visiting each node, the temporary links are removed, restoring the original tree structure.
Choose inorder traversal when you need sorted output from a BST, when validating BST properties, when finding the kth smallest or largest element, or when converting a BST to a sorted sequence. For non-BST binary trees, inorder traversal still visits every node but does not guarantee any particular ordering. If you need to process parents before children, use preorder. If you need bottom-up computation, use postorder.