Tree Traversals
Tree traversal is essential in solving tree-related problems, as it determines the order of node visits and the information processed at each node. Traversals are categorized into depth-first search (DFS) and breadth-first search (BFS), with DFS further divided into inorder, preorder, and postorder, while BFS consists of level-order traversal. Each traversal serves specific problem types: inorder for sorted output, preorder for tree copying, postorder for computations dependent on children, and level-order for processing nodes by depth. Understanding the nuances of recursive versus iterative implementations and recognizing common pitfalls is crucial for effective traversal in coding interviews.
Every tree problem eventually reduces to a traversal question: in what order do we visit the nodes, and what do we do at each one? The traversal order determines what information is available at each node during processing. That is why choosing the correct one is important, because the wrong one can produce incorrect results even when the code itself has no bugs.
DFS and BFS
All traversals fall into two categories: depth-first search (DFS) and breadth-first search (BFS). Within DFS, there are three variants (inorder, preorder, and postorder), while BFS has one (level-order). In an interview, you’ll be expected to recognize which one solves the problem quickly, not figure it out by elimination.
DFS visits nodes by going as deep as possible along one path before backtracking. It is the algorithm behind inorder, preorder, and postorder traversals. DFS is the right choice for problems that involve paths, subtrees, or any computation where a node’s result depends on its children.
BFS visits nodes level by level, processing all nodes at the current depth before moving to the next. It is the algorithm behind level-order traversal. BFS is the right choice for problems that involve depth, levels, or the shortest path in an unweighted tree.
Choosing the right traversal
With DFS and BFS as the foundation, the next layer is recognizing which of the four specific traversals solves the problem. This is where candidates separate themselves: those who recognize the pattern immediately vs. those who try approaches until something works.
Inorder traversal
Inorder traversal visits the left subtree, then the current node, then the right subtree. For a BST, this produces nodes in ascending sorted order. Any problem that requires processing BST nodes in sorted order, or validating that a BST is valid, is almost always an inorder traversal problem.
Preorder traversal
Preorder traversal visits the current node first, then the left subtree, then the right subtree. Because the root is processed before its children, preorder is the natural choice for problems that require copying or serializing a tree, where we need to reconstruct the structure from the traversal order. It is also the right choice for any problem where a node needs information from its parent before its children can be processed.
Postorder traversal
Postorder traversal visits the left subtree, then the right subtree, then the current node. Because children are processed before their parent, postorder is the natural choice for problems where the computation at a node depends on results from its children first. Computing height, checking balance, and deleting a tree are all postorder problems.
Level-order traversal
Level-order traversal uses BFS to visit all nodes at each depth before ...