Traversals
Tree traversal is about choosing when to visit the node relative to its children, which determines whether the algorithm sees roots first, sorted BST values, subtree results, or complete levels.
The Four Core Orders
Depth-first traversal has three main orders. Preorder is node, left, right. Inorder is left, node, right. Postorder is left, right, node. Breadth-first traversal, also called level-order, visits nodes by depth from top to bottom using a queue.
For a tree like [1,2,3,null,4], preorder sees the root before descendants, inorder places the root between left and right sides, postorder waits until subtrees finish, and BFS sees 1, then 2 and 3, then 4.
When Each Order Is Used
Use inorder when a BST should produce sorted output or when you need predecessor, successor, or kth-smallest behavior. Use postorder when the node needs completed child answers first, such as height, balance, diameter, subtree deletion, or freeing nodes. Use preorder when the root decision should happen before children, such as copying a tree, serializing with null markers, or passing inherited state downward.
Use level-order when the problem speaks in levels: right side view, averages of each level, zigzag traversal, minimum depth, nearest target, or any prompt where the first layer found is important.
Recursive vs Iterative DFS
Recursive DFS uses the call stack as the traversal stack. The code is short because each function call represents one pending node and its unfinished children. The trade-off is stack depth: a skewed tree can use O(n) call stack space.
Iterative DFS makes that stack explicit. Preorder is especially direct with a stack because you pop a node, visit it, then push right before left so left is processed next. Inorder iterative traversal walks left while pushing ancestors, then pops and moves right. Postorder iterative traversal usually needs a previous pointer, two stacks, or a modified preorder strategy.
BFS With a Queue
BFS uses a queue because nodes are processed in the order they are discovered. Start with the root, repeatedly remove the front node, and add its children to the back. To separate levels, capture the queue size before processing a layer; exactly that many nodes belong to the current depth.
Queue invariants are powerful in interviews. At the start of each outer loop, the queue contains exactly the nodes for the next level. After processing that many nodes, it contains exactly the children for the following level.
Choosing the Traversal
Do not memorize traversal names in isolation. Ask what information the current node needs. If it needs ancestor information, preorder or top-down DFS is natural. If it needs child summaries, postorder is natural. If the tree is a BST and sorted order matters, inorder is natural. If the question is organized by depth, BFS is natural.
This pattern-recognition step is often the difference between a clean interview solution and a forced one. The traversal order should match the dependency direction of the data you are computing.
Recursive inorder traversal
Inorder visits the left subtree, then the node, then the right subtree; on a BST, that produces sorted ascending values.
BFS level-order template
Capturing levelSize before the inner loop keeps one BFS iteration aligned with exactly one tree depth.
Key Takeaways
- Preorder visits **node, left, right**; inorder visits **left, node, right**; postorder visits **left, right, node**.
- Inorder is the sorted-order traversal for BSTs, while postorder is the natural order for subtree aggregation.
- Recursive DFS uses the call stack; iterative DFS uses an explicit stack to control the same pending work.
- BFS uses a queue and is the right default when a problem asks about levels.