Tree Traversal

Tactic

Tree traversal visits nodes while carrying path, depth, or subtree state. Recursion fits naturally because each child is the root of a smaller tree.

The invariant depends on traversal order. Preorder handles a node before children, inorder exposes sorted order in a BST, postorder solves children before the parent, and level order groups nodes by depth.

Choose the traversal from the data dependency. If the parent needs child answers, use postorder. If children need path state from ancestors, use preorder. If the answer is by level, use BFS.

Value

The value is using tree structure instead of treating nodes as arbitrary graph nodes. Since a tree has no cycles, traversal can avoid a visited set when parent links are absent.

Direct complexity example

Brute force: For each node, recompute information by scanning its subtree repeatedly: $O(n^2)$ time in skewed cases.
With this tactic: Return or carry the needed state in one traversal: $O(n)$ time.
Space: Recursive DFS uses $O(h)$ stack space for tree height. BFS level order can use $O(w)$ space for maximum width.

Challenges this solves

max depth
same tree
path sums
BST validation
level order output
subtree aggregation

When to use it

Use this tactic when these conditions are true:

the input is hierarchical
each node has children and no cycles
the answer depends on path or subtree information
the prompt asks for level, depth, ancestor, descendant, or BST order

When not to use it

Reach for a different tactic when these warning signs appear:

the structure can contain cycles and needs graph traversal with visited state
the tree is too deep for recursion without an iterative version
random access by value is needed and traversal alone is too slow
the problem needs updates and queries over a dynamic tree

Terminology clues

These prompt words often point toward this concept:

tree
root
leaf
subtree
depth
level order
ancestor
BST