Four ways to visit every node of a binary tree, and why the order differs.
The idea (a company org chart)
A tree is like an org chart: one boss at the top, and each person has at most two direct reports (a left and a right child). “Traversal” means walking through everyone exactly once. The only question is when you say hello to a person:
Preorder: greet the person first, then their left side, then their right side.
Inorder: left side first, then the person, then the right side. (On a search tree this gives sorted order.)
Postorder: both sides first, the person last. (Children before parents, like deleting a folder tree.)
Level-order: floor by floor, top to bottom. Uses a queue instead of recursion.
The three recursive versions are the same function with the line visit moved. Watch the call stack grow when we go down and shrink when a call returns.
Watch it work
Try it
Run all four modes on the same tree and compare the output lists.
Type 4, 2, 6, 1, 3, 5, 7 and run Inorder. What do you notice about the output?
Make a lopsided tree: 1, null, 2, null, 3, null, 4. How tall does the call stack get?
Watch the nil calls: every missing child still gets a call that returns immediately.
Common mistakes
Forgetting the nil check. Without if n == nil { return } the code dereferences a nil pointer and panics.
Mixing up the orders. Remember: the name says where visit goes relative to the children (pre = before, in = between, post = after).
Very deep trees. Recursion uses one stack frame per level. A tree that is really a long chain can use a lot of stack, so interviewers sometimes ask for an iterative version.
Complexity, in plain English: every node is visited once, so the time grows in step with the number of nodes (O(n)). The recursive versions need space equal to the tree’s height; level-order needs space equal to the widest floor.