What Is Binary Tree Traversal?
Binary Tree Traversal visits every node of a tree exactly once in a defined order. The main kinds are the depth-first family — preorder, inorder, postorder — and the breadth-first level-order.
The one-line idea: "the three depth traversals differ only in when you visit the root." Left child always comes before right; only the root's position moves to the front, middle, or back.
Three Depth Traversals (DFS Family)
| Traversal | Order | Use |
|---|---|---|
| Preorder | root → left → right | tree copy, prefix expression |
| Inorder | left → root → right | ascending order on a BST |
| Postorder | left → right → root | tree deletion, postfix evaluation |
The "pre/in/post" names refer to when the root is visited relative to its children.
Inorder and the BST
A binary search tree (BST) keeps the rule "left < root < right." So visiting it inorder (left → root → right) yields values in exact ascending order. Sorted output or the k-th value in a BST uses precisely this property.
How It Works
Step 1. If the current node is empty (null), just return (base case).
Step 2. Recursively perform three actions — traverse the left child, visit the current node, traverse the right child.
Step 3. Just reordering these three gives preorder, inorder, or postorder: visit first → preorder, middle → inorder, last → postorder.
Level-order is different — it uses a queue to visit top to bottom, left to right within a level (BFS).
The AlgoNote visualization shows the order in which the same tree is visited under each traversal, step by step.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(n) |
| Space | O(h) ~ O(n) |
Each node is seen once → O(n); recursion space is the tree height h (O(n) for a skewed tree).
Walking Through an Example
A tree with root 2, left 1, right 3:
- •preorder: 2, 1, 3
- •inorder: 1, 2, 3 ← ascending (BST)
- •postorder: 1, 3, 2
- •level: 2, 1, 3
Common Mistakes
- •Confusing the orders: remembering that the only difference is the root's position keeps them straight.
- •Forgetting inorder = sorted: for sorted output on a BST, use an inorder traversal rather than sorting separately.
- •Null handling: skipping the null check blows up the recursion.
See It in Action on AlgoNote
Watch the order in which preorder, inorder, postorder, and level traversals each visit the nodes of the same tree, step by step on AlgoNote.