Pick the Traversal: DFS Orders and BFS Levels

Every tree problem walks the tree in some order, and the order you pick decides what information is ready when you visit a node. The three depth-first orders differ only in where the visit line sits relative to the two recursive calls. Breadth-first search (BFS) walks level by level instead. Don't just memorize the code; memorize the use case for each.

The idea#

A depth-first walk reaches every node three times: on the way down, between its two subtrees, and on the way back up. Recording the node at one of those moments gives preorder, inorder or postorder.

Order	Visit happens	What is ready at the visit	Use it for
Preorder (root, left, right)	before the children	only the path from the root	serializing and copying: the parent exists before its children
Inorder (left, root, right)	between the children	the whole left subtree	BSTs: values come out in sorted order
Postorder (left, right, root)	after the children	both subtrees, fully processed	deletion and bottom-up answers like height
Level order (BFS)	level by level	everything above this level	min depth, "per level" answers, shortest distance

The postorder row explains most of the patterns in this section: you can't delete a node or know its height until both children are done. The BFS row has its own rule. If the answer is likely near the top, BFS is faster than DFS, because it stops at the first match instead of exploring every path.

How to spot it#

The wording usually names the order for you.

"Sorted order", "k-th smallest", "is it a valid BST": inorder.
"Serialize", "copy", "clone", "build": preorder (the root comes first).
"Delete", "prune", "height", "diameter", anything that needs both children's answers: postorder.
"Minimum depth", "level", "row", "right side view", "nearest": BFS.
"Width", "complete tree", "next pointer": BFS with a little extra state per node.

Template#

The first shape shows all three DFS orders in one walk, so you can see the visit line move. Nodes follow LeetCode's TreeNode(val, left, right).

walk(node):
    if node is None: return
    visit node here for PREORDER     # before children: parent first
    walk(node.left)
    visit node here for INORDER      # between children: sorted for a BST
    walk(node.right)
    visit node here for POSTORDER    # after children: both answers ready

Level-order BFS#

When the question is about levels instead of paths, switch to BFS. Every BFS problem below builds on this shape.

if root is None: return empty result
queue = [root]
while queue is not empty:
    size = length of queue           # snapshot: exactly one level
    repeat size times:
        node = pop from the front of queue
        process node for this level
        push node's non-empty children onto the back
    finish this level's answer

The size line is the level snapshot. You read the queue length once, so children added during the loop wait for the next round.

Iterative DFS#

Recursion is the default. You still need the stack versions for very deep trees, where recursion can hit Python's limit (see Pitfalls).

Preorder: push the right child before the left, so the left pops first.
Inorder: dive left while you push nodes. Pop one, visit it, then move to its right child.
Postorder: the "reverse" trick. Produce root, right, left with the preorder stack, then reverse the output.

Numbering nodes by position#

Width questions count the empty gaps between nodes, so they need each node's position, not just the node. Number the nodes the way an array-backed heap does: a node at index i has children at 2*i and 2*i + 1. Store (node, index) pairs in the queue.

A three-level binary tree with each node labeled by its index within the level: 0; then 0 and 1; then 0 to 3. Arrows show a node at index i giving children 2i and 2i+1

Pitfalls#

These mistakes crash on deep trees or mix up levels.

Skewed trees. A tree shaped like a linked list makes recursion as deep as n. Python's default limit is about 1000 frames, so deep inputs need an iterative walk or a raised limit.
The hidden null. Check node.left before reading node.left.val. Handle the three edge cases up front: no root, no left child, no right child.
Taking the level size too late. Read the queue length once per level, before you start popping. Re-checking while queue inside the level mixes levels.
Treating a one-child node as a leaf. A node is a leaf only when both children are missing.
Empty-tree return type. Counts such as width should return 0 for an empty tree, not [].

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Binary Tree Inorder Traversal

The recursive version puts the visit between the two calls. For the iterative version, dive left while you push nodes, pop one, visit it, then move to its right child.

Hint: Binary Tree Level Order Traversal

This is the BFS template. Collect each level's values in a list during the size loop.

Hint: Minimum Depth of Binary Tree

Max depth needs every path, but min depth doesn't. BFS returns the level of the first leaf it pops. In a DFS version, a missing child must count as float('inf'), not 0, or a one-child node passes for a leaf.

Hint: Kth Smallest Element in a BST

Inorder visits a BST's values in sorted order. Count visits and stop at the k-th.

Hint: Binary Tree Right Side View

Run the level-order template and record the last node of each level.

Hint: Maximum Width of Binary Tree

Width counts the gaps too, so number the nodes by position (2*i and 2*i + 1). Read the level's first index from the front of the queue before the loop. The width is last - first + 1.

Hint: Check Completeness of a Binary Tree

The wording is awkward, but the ask is simple: in level order, no real node may follow an empty spot. Enqueue children even when they are None. Set a flag at the first None you pop; a real node after that means the tree is not complete.

Hint: Populating Next Right Pointers in Each Node

Inside the level loop, the next node of the same level is already at the front of the queue. Link node.next = queue[0] for every node but the last in the level. The same code works for perfect trees (LC 116) and arbitrary ones (LC 117).

Key takeaways#

The three DFS orders are one walk with the visit line in three places.
Inorder means sorted (BSTs), preorder means structure first, postorder means children first.
BFS with a level snapshot answers anything "per level" and finds the shallowest answer first.
Extra state in the queue, such as an index or a None marker, turns plain BFS into width and completeness checks.
Handle the empty tree and missing children before anything else.

Core idea#

The traversal order decides what information is ready when you visit a node. The three DFS orders differ only in where the visit sits around the two recursive calls. BFS walks level by level.

Pick the order#

Order	Ready at the visit	Use it for
Preorder	the path from the root	serialize, copy, build
Inorder	the whole left subtree	BSTs: sorted order, k-th smallest
Postorder	both subtrees	delete, prune, height, diameter
Level order (BFS)	all levels above	min depth, per-level answers, nearest

Key points#

If the answer is likely near the top, BFS beats DFS. It stops at the first match.
Level snapshot: read the queue length once per level, so the loop covers exactly one level.
Min depth: BFS returns the level of the first leaf. In DFS, a missing child counts as float('inf'), not 0.
Width: store (node, index). Children get 2*i and 2*i + 1. Width is last - first + 1.
Completeness: enqueue None children. A real node after the first None means not complete.
Next pointers: inside the level loop, set node.next = queue[0] for all but the last node.
Iterative DFS: preorder pushes right before left. Postorder builds root, right, left, then reverses.

Template#

if root is None: return empty result
queue = [root]
while queue is not empty:
    size = length of queue           # snapshot: exactly one level
    repeat size times:
        node = pop from the front of queue
        process node for this level
        push node's non-empty children onto the back
    finish this level's answer

Pitfalls#

Skewed trees. Recursion depth reaches n, and Python's default limit is about 1000. Use an iterative walk or raise the limit.
The hidden null. Check node.left before you read node.left.val.
Taking the level size inside the loop. It mixes levels.
Wrong empty-tree type. Width returns 0, not [].

Say it in an interview#

"Inorder for sorted BST values, preorder when the parent must exist first, postorder when you need both children."
"BFS with a level snapshot gives the shallowest answer first."