Binary Tree Traversals
The three depth-first traversals are the same recursive walk with one statement in three different places. That is genuinely all that separates them, and it explains why inorder produces sorted output on a BST while postorder is the only safe way to delete a tree — the position of the visit determines what has already happened when you arrive.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
struct Node {
int val;
Node* left;
Node* right;
};
Node* make(int v) {
Node* n = new Node();
n->val = v; n->left = NULL; n->right = NULL;
return n;
}
void inorder(Node* r) {
if (r == NULL) return;
inorder(r->left);
cout << r->val << ' ';
inorder(r->right);
}
int main() {
Node* root = make(4);
root->left = make(2); root->right = make(6);
root->left->left = make(1); root->left->right = make(3);
inorder(root);
return 0;
}Inorder on this tree prints 1 2 3 4 6; move the cout above the first recursive call for preorder, or below the second for postorder.
How it works, step by step
The walk is always the same
Every traversal descends left, then right, then returns. The recursion visits each node exactly three times — on arrival, between the two children, and on departure. Which of those moments you print at is the entire choice.
Preorder: act before you descend
Printing before both calls means a node is emitted before anything beneath it. That gives you the root first, which is what you want for copying a tree or serialising it — the parent must exist before its children can be attached.
Inorder: act between the children
The left subtree is fully processed, then the node, then the right. On a binary search tree this yields values in sorted order for free, because everything left is smaller and everything right is larger, recursively.
Postorder: act after you descend
Both subtrees are complete before the node is touched. That is the only correct order for freeing memory or computing a value that depends on both children's results, such as subtree size or height.
The base case is where the depth is bounded
if (r == NULL) return; is what stops the recursion at the leaves. Every node's two null children each generate one call that immediately returns, so a tree of n nodes produces about 2n+1 calls in total.
Complexity
Every node is visited a constant number of times, so time is linear regardless of shape; the space is the recursion stack, which is O(log n) for a balanced tree and O(n) for a degenerate one that has become a linked list.
Common bugs
Missing or misplaced base case
Without if (r == NULL) return;, the first leaf dereferences a null pointer and segfaults. Putting the check after the first recursive call is equally broken — the crash happens on the way down, before the guard is ever reached.
Expecting inorder to be sorted on any tree
Inorder produces sorted output only on a binary search tree. On an arbitrary binary tree it produces an order that reflects the shape, not the values. If your inorder output is not sorted, check whether the tree actually satisfies the BST property before suspecting the traversal.
Freeing nodes in preorder
delete r before recursing destroys the node whose left and right pointers you are about to read. It often appears to work because freed memory is not immediately overwritten, then crashes intermittently under load. Deletion must be postorder: free the children, then the parent.
Deep recursion on a degenerate tree
A tree built by inserting already-sorted values becomes a linked list of height n, and the traversal needs n stack frames. At a few hundred thousand nodes that overflows. Watching the call stack grow one frame per node makes the difference between a balanced and degenerate tree immediately visible.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
What is the difference between inorder, preorder and postorder traversal?
They differ only in when the current node is processed relative to its children. Preorder handles the node before both subtrees, inorder between the left and right subtrees, and postorder after both. The traversal path through the tree is identical in all three; only the moment of the visit moves.
Why does inorder traversal of a BST give sorted output?
Because the BST property guarantees every value in the left subtree is smaller than the node and every value in the right is larger. Inorder emits the entire left subtree, then the node, then the entire right subtree — applied recursively, that is exactly ascending order.
Which traversal should I use to delete a tree?
Postorder. You must free both children before freeing the parent, because once the parent is deleted its left and right pointers are no longer valid to read. Preorder deletion reads through a freed pointer, which is undefined behaviour that often appears to work in testing.
What is the space complexity of tree traversal?
O(h), where h is the tree's height, because the recursion holds one stack frame per level on the current path. That is O(log n) for a balanced tree but O(n) for a degenerate one, which is why inserting sorted data into an unbalanced BST can turn a traversal into a stack overflow.