Traversals: Depth-First and Breadth-First

The intuition: two ways to explore a house

Imagine you're inspecting a big house full of rooms, hallways, and closets.

• Depth-first (DFS): you go through the first door and keep going until you reach the farthest closet. Then you step back once and try the next door. That's how the "right hand on the wall" maze trick works.
• Breadth-first (BFS): you check every room on the first floor first, then every room on the second floor, then the third. You cover the house floor by floor.

Trees work the same way. DFS dives down a branch, and BFS goes level by level. Almost every tree problem in an interview is one of these two traversals plus a bit of logic on top.

Our tree for the examples

Let's take one tree and traverse it every way we can:

DFS: three orders, one recursion

DFS comes in three variants. They differ in only one thing: when you "process" the current node, before its children, between them, or after them.

Traversal	Order	Result for our tree
Pre-order	node → left → right	4 2 1 3 6 5 7
In-order	left → node → right	1 2 3 4 5 6 7
Post-order	left → right → node	1 3 2 5 7 6 4

How to remember it: the prefix tells you where the node goes. Pre means the node comes before its children, in means the node sits in between them, post means the node comes after its children.

Look at pre-order. We start at the root, dive left, and walk the entire left branch before touching the right one:

The in-order trick. In a binary search tree (BST), it yields the values in sorted order: 1 2 3 4 5 6 7. This fact comes up in interviews all the time, so remember it.

When each order is the one you need:

• Pre-order: when decisions are made top-down. For example, you need to pass depth or the path from the root down to the children, copy the tree, or serialize it.
• In-order: for BSTs, such as finding the k-th smallest element or validating the tree.
• Post-order: when a node needs answers from its children. For example, height, diameter, "is it balanced." Ask the children first, then compute yourself.

The DFS template (recursion)

The template has three "slots." Code in the first slot gives pre-order, in the second gives in-order, in the third gives post-order. Here the print sits in the in-order slot:

def dfs(node):
    if node is None:          # base case: empty subtree
        return
    # 1) pre-order goes here
    dfs(node.left)
    print(node.val)           # 2) in-order goes here
    dfs(node.right)
    # 3) post-order goes here

Move the print to a different slot and you get a different order. That's the whole secret of the three traversals.

BFS: level by level with a queue

BFS keeps a queue of nodes waiting to be processed. You take a node from the front of the queue and put its children at the back. That's why upper levels are always processed before lower ones.

The key interview trick: at the start of each level, record the queue's size. Exactly that many nodes make up the current level.

The levels of our tree: [4], [2, 6], [1, 3, 5, 7].

The BFS template (queue with level size)

As an example, let's count the nodes on each level. For our tree, the result is [1, 2, 4].

from collections import deque

def level_sizes(root):
    if root is None:
        return []
    res, q = [], deque([root])
    while q:
        size = len(q)             # number of nodes on the current level
        for _ in range(size):
            node = q.popleft()
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        res.append(size)
    return res

Complexity

	Time	Space
DFS	O(n)	O(h): the recursion stack, h is the tree's height
BFS	O(n)	O(w): the widest level, up to n/2 nodes

Each node is visited exactly once. If the tree degenerates into a "stick," h = n, and deep recursion can overflow the stack.

Which one to pick in an interview

• The problem mentions "level," "layer," "minimum depth," "right side view," "zigzag" → BFS.
• A node's answer depends on its children's answers (height, diameter, path sum) → DFS, post-order.
• You need to pass something from the top down (a path, the current depth) → DFS, pre-order.
• It's a search tree and you need the values in order → DFS, in-order.

How it sounds out loud: "I'll traverse the tree depth-first with recursion and compute the height on the way back up from the children, so this is post-order. O(n) time, O(h) space for the stack." One sentence like that shows the interviewer you know what you're doing.

Common mistakes

• Forgetting the base case node == null in DFS means an instant crash.
• Not checking for an empty root before putting it into the BFS queue.
• Calling len(q) directly in the level loop condition. The queue grows as you add children, and the levels get mixed together. Save the size in a variable beforehand.
• Using list.pop(0) in Python or shift() in JS. That's O(n) per operation, and the traversal turns into O(n²). Use a deque, or collect the next level in a separate array.
• Mixing up the orders. Go by where the node sits: pre means before the children, in means between them, post means after.

The two templates from this lesson cover most tree problems. Next comes practice, and you'll see them repeat from problem to problem.