Trees and Graphs: How to Traverse Them

The problem

Some people see a tree or graph in the prompt and immediately assume the problem got ten times harder.

Sometimes it did.

But a lot of the panic comes from how the structure looks, not from the logic the solution actually needs.

Most of these questions start with something very plain:

• how do I visit the nodes?
• in what order?
• how do I avoid getting lost or revisiting the same place for no reason?

If that layer is not clear, everything after it feels messy.

Mental model

Trees and graphs are connection structures.

The big difference is that trees usually come with more order:

• a root
• parent-child relationships
• no cycle

Graphs are more general:

• they can have cycles
• they may not have a root
• they can be directed or undirected
• there can be several ways to reach the same node

That is why a good solution often starts with traversal.

Two families show up all the time:

• DFS: depth-first search
• BFS: breadth-first search

If you want the short version:

Before you solve the fancy part, figure out which walk through the structure actually makes sense.

Breaking it down

DFS in human words

DFS tries to go deep before it comes back.

It is like walking down a hallway and keeping going until you cannot go any farther, then backtracking.

It shows up a lot in:

• tree depth
• structural validation
• path search
• connected component exploration
• problems where the answer depends on a subtree

You can write it with:

• recursion
• an explicit stack

BFS in human words

BFS explores level by level.

First everything that is close.

Then everything one step farther away.

Then two steps away.

It shows up a lot in:

• shortest path in an unweighted graph
• distance by levels
• level-order tree traversal
• problems where the first time you reach something matters

It usually uses a queue.

What visited is really doing

In a tree, you often do not think much about it because there is no cycle.

In a graph, forgetting visited is usually an invitation to:

• revisit the same node
• loop forever
• blow up the runtime without noticing

Visited is not a bureaucratic detail.

It is part of the traversal itself when the structure allows you to come back around.

Turn the prompt into traversal plus a condition

This helps more than people expect.

Examples:

• “find the maximum depth” -> DFS + track depth
• “determine whether a path exists” -> DFS or BFS + stop when you reach the target
• “find the shortest number of steps” -> BFS + distance
• “count how many connected groups exist” -> repeat traversal + count components

A scary prompt gets smaller when you translate it that way.

Simple example

Take a binary tree and this question:

What is the maximum depth?

DFS is usually the natural fit.

Why?

Because the answer at a node depends on the deepest path inside each subtree.

The reasoning is:

1. if the node is null, depth is zero
2. compute the depth of the left subtree
3. compute the depth of the right subtree
4. take the larger one and add one

Now compare that with a different question:

What is the shortest distance from a starting node to another node in an unweighted graph?

Here BFS is usually more natural.

Because it expands by layers.

The first time you reach the target is already the shortest number of edges.

The point is not to memorize “depth means DFS” and “shortest path without weights means BFS.”

The point is to notice that the order of exploration matches the question better.

Common mistakes

• Getting stuck on the structure and forgetting that traversal is the first decision.
• Using DFS where BFS would make the answer cleaner, or the other way around.
• Forgetting visited in a graph with cycles.
• Treating trees and graphs as identical in every way.
• Starting to code traversal before saying what state each step is carrying.

How a senior thinks

People with more experience de-escalate this kind of problem fast.

Their internal questions usually sound like this:

• what structure do I actually have here?
• is there a cycle?
• do I have a root?
• do I need shortest distance or just reachability?
• does the answer depend on a subtree or on layers?

That way of thinking matters because it keeps you from using the traversal you remember best.

And that matters outside interviews too.

Service dependencies, component trees, workflows, permission graphs, job ordering. They all use the same traversal mindset.

What the interviewer wants to see

The interviewer wants to see whether you:

• recognize the right traversal
• understand the difference between BFS and DFS
• know when visited is required
• can explain what state is being carried at each step

If you can say, “This is traversal plus a condition, and BFS makes sense because I need the shortest distance in an unweighted graph,” you are already doing better than someone who just throws a template at the screen.

Trees and graphs get less scary when you stop looking at the whole structure and start looking at the next visit.

In a lot of problems, half the solution is just picking the right walk.