Depth-first vs breadth-first

Two ways to explore a tree — go deep, or go wide. · 14 min read

Concept

Strip away the exact visit order and tree traversal splits into two large families. Depth-first search (DFS) follows one branch as far as it can before backtracking. Breadth-first search (BFS) explores every node at the current depth before moving deeper.

The difference is not just visual. DFS asks, 'What happens if I keep going down this path?' BFS asks, 'What can I reach in 0 steps, then 1 step, then 2 steps?' That one choice decides memory usage, first-found answers, and which problems feel natural.

DFS mechanics

Interactive visualization: DFS — go deep first (pre-order) — step through it frame by frame on this page.

DFS behaves like a stack. The most recently discovered unfinished node gets processed next. In recursive DFS, the call stack stores the path from the root to the current node. Each call remembers: 'I am at this node, I have already handled some child work, and after the child returns I know where to continue.'

For the sample tree, a pre-order DFS reads 8, 3, 1, 6, 10, 14. Notice how it goes 8 -> 3 -> 1 before it ever looks at 10. That is the depth-first personality: finish the current corridor, then backtrack.

bool contains(Node* root, int target) {
    if (!root) return false;
    if (root->key == target) return true;
    return contains(root->left, target) || contains(root->right, target);
}

When DFS is the right tool

DFS is natural when the answer is about subtrees or complete paths: height of a tree, subtree sum, validating a BST, printing all root-to-leaf paths, expression-tree evaluation, serialization, and tree dynamic programming. It is also the base pattern for backtracking: choose, recurse, undo.

A post-order DFS can compute subtree sizes because it waits until child answers are ready:

int subtreeSize(Node* root) {
    if (!root) return 0;
    int left = subtreeSize(root->left);
    int right = subtreeSize(root->right);
    return 1 + left + right;
}

BFS mechanics

BFS behaves like a queue. Nodes discovered earlier are processed earlier, so all depth-d nodes are expanded before any depth-d+1 node. On the sample tree, BFS reads 8, 3, 10, 1, 6, 14: the tree is scanned in horizontal layers.

Interactive visualization: BFS — go wide, level by level — step through it frame by frame on this page.

BFS is the right choice when distance in edges matters. In a tree, the first time BFS finds a target, that target has the minimum depth among all matching nodes because all nodes at depth d are processed before any node at depth d+1.

Worked example

If the root is depth 0, its children are depth 1, grandchildren depth 2, and so on. DFS might find a target at depth 5 before checking a different branch at depth 2. BFS cannot do that: it exhausts depth 0, then 1, then 2. That layer invariant is the same idea behind BFS shortest paths in unweighted graphs.

Tree vs graph detail

On a tree, there is exactly one path from the root to any node, so traversal does not need a visited set if you only follow child pointers downward. On a general graph, cycles exist, so DFS and BFS must mark visited vertices. Without that, a graph traversal can loop forever.

// Graph BFS needs visited/dist because neighbours can point back.
queue<int> q;
vector<int> dist(n, -1);
q.push(start);
dist[start] = 0;

while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

Time and space complexity

On a tree with n nodes, DFS and BFS both take O(n) time in the worst case because they may need to inspect every node. DFS auxiliary space is O(h) for height; on a balanced tree that is O(log n), while a skewed tree is O(n). BFS auxiliary space is O(w) for width; a complete tree can have about n/2 nodes on the last level, so worst-case queue space is O(n).