Every graph traversal needs a visited set. Without one, cycles send you in circles forever, and even acyclic graphs waste time revisiting nodes from multiple parents. This part is obvious.

What is not obvious is that the visited set has a timing decision baked into it. When exactly do you mark a node as visited? You have two choices: the moment you enqueue it (mark-on-push), or later, when you dequeue it to process (mark-on-pop).

Both feel reasonable. Both produce correct output in the sense that every node gets visited eventually. But one of them does dramatically more work than the other. The wrong choice turns an O(V+E) traversal into O(V²) -- and the code looks almost identical in both cases. The bug hides in plain sight because the program still produces the right answer, just slowly.

This lesson is about that single timing decision and why it matters more than you think.

To see why the timing matters, picture a concrete scenario. Node A, node B, and node C all have edges pointing to the same unvisited node X. All three are in the BFS queue. As each one gets processed, it looks at its neighbors and finds X.

Mark-on-push (enqueue time): A processes first, sees X is unvisited, marks X visited, enqueues X. Now B processes, sees X is already visited, skips it. C does the same. X enters the queue exactly once.

Mark-on-pop (dequeue time): A processes first, sees X is unvisited (nobody has dequeued and marked it yet), enqueues X. B processes, sees X is still unvisited (X is sitting in the queue but has not been popped), enqueues X again. C does the same. X now sits in the queue three times. Each copy gets dequeued and processed separately, each one enqueuing X's neighbors redundantly.

Scrub through both strategies below. Watch the queue -- in mark-on-push, X enters exactly once. In mark-on-pop, the duplicates cascade.

On a dense graph where many nodes share neighbors, this duplication cascades. Each redundant enqueue spawns more redundant enqueues. What should be O(V+E) balloons toward O(V²) or worse -- not because the algorithm is wrong, but because the timing of one boolean flip is off by a few lines of code.

Theory is one thing. Seeing the queue explode is another.

You just read about two timing strategies for the visited mark. Both sounded plausible in prose -- and that is exactly the problem. When two approaches sound equally reasonable but one is dramatically worse, the only way to build reliable intuition is to watch both run on the same input and see where they diverge. Prose cannot convey the moment the queue starts growing out of control; you have to watch the numbers climb.

Below is the same graph run with both marking strategies. Start with mark-on-push and step through -- notice how the queue stays lean, with each node appearing exactly once. Every enqueue is purposeful: it represents a genuinely new node that BFS has never seen before. Then switch to mark-on-pop and step through again. Watch the queue bloat as the same node gets enqueued by multiple parents. Each duplicate represents wasted work -- a node that will be dequeued, processed, and have its neighbors scanned, all redundantly.

Pay special attention to the queue length at each step. In mark-on-push, it grows and shrinks predictably. In mark-on-pop, it swells with duplicates that all represent the same node. The visit order stays the same -- both produce correct BFS output. The waste is invisible in the result and visible only in the work.

Now see both strategies head-to-head on the same graph. The left side uses mark-on-push; the right uses mark-on-pop. An operation counter tracks every enqueue.

This is the kind of performance difference that does not show up in correctness tests. Both strategies produce the same BFS traversal -- the same visit order, the same set of reachable nodes, the same shortest distances. If you wrote unit tests that check output, both implementations would pass. The difference only appears in the operation count, and on small inputs, even that difference looks negligible.

On this small graph, the gap might look minor -- maybe 8 enqueues versus 14. But the ratio worsens with graph density because the duplication is multiplicative. On a complete graph with V nodes, mark-on-pop can enqueue O(V²) times because every node can be reached from every other node, and each reaching-node re-enqueues it. Mark-on-push stays at O(V) enqueues because each node enters the queue at most once -- the visited flag at enqueue time prevents any re-entry.

Watch the counters diverge and notice: the visit order is identical. Both strategies produce the same BFS traversal. The difference is purely in wasted work -- redundant enqueues, redundant processing, redundant neighbor scans. On competitive programming judges, this is the difference between AC (accepted) and TLE (time limit exceeded).

So mark-on-push wins for BFS. Case closed? Not quite. DFS plays by different rules.

In BFS, the only question is “have I seen this node before?” A boolean is enough -- visited or not. But DFS needs to answer a harder question: "Is this node still on my current recursion path, or did I finish processing it earlier and leave?"

The distinction matters for cycle detection in directed graphs. If DFS encounters a node that is still being processed (it is somewhere on the current recursion stack), that is a back edge -- a genuine cycle. But if DFS encounters a node that was fully processed and returned from, that is a cross edge or forward edge -- perfectly safe, no cycle.

A simple boolean visited flag cannot distinguish these two cases. It says “yes, I've seen this node,” but not “is this node still in progress?” That ambiguity leads to false positives: reporting cycles that do not exist.

The solution is to replace the boolean with three colors:

• White: unvisited -- DFS has never touched this node
• Gray: on the recursion stack -- DFS entered this node and has not yet returned
• Black: fully processed -- DFS entered, explored all descendants, and returned

The color transitions are mechanical. A node turns gray when DFS enters it. It turns black when DFS finishes processing all its neighbors and returns. It never goes back to white.

Now the cycle detection rule is simple: if DFS is about to visit a neighbor and that neighbor is gray, it means the neighbor is an ancestor on the current recursion path. The edge from the current node back to that ancestor is a back edge -- the hallmark of a cycle. If the neighbor is black, it was fully processed in an earlier branch. That is a cross edge or forward edge, and it is safe.

Gray means “I'm your ancestor -- you're about to form a loop.” Black means “I'm finished -- move along.”

Here is the full picture. Same graph, two traversals running side by side. BFS on the left uses mark-on-push with a binary visited set. DFS on the right uses three-color marking.

This side-by-side view reveals something that is easy to miss when studying each algorithm in isolation: BFS and DFS face different bookkeeping problems, and the visited strategy that works perfectly for one can fail silently for the other. BFS needs to prevent duplicate enqueues -- a binary flag at enqueue time handles this completely. DFS needs to distinguish “in-progress ancestor” from “fully-finished node” -- a binary flag cannot make this distinction, which is why it needs three colors.

Both are answering the same fundamental question: “When do I mark a node, and how many states do I need?” But they arrive at different answers because their traversal shapes create different problems. BFS spreads uniformly -- every node at distance d before any at d+1 -- so the only question is “have I seen this node?” DFS dives deep, creating long chains of in-progress nodes, so the question is “have I seen this node, and is it still on my current path?”

Tap to advance both simultaneously. Watch how the visited set on the left stays binary (visited or not) while the color state on the right cycles through three phases. Same graph, same nodes, different bookkeeping -- and each strategy is correct for its traversal.

def bfs(graph, start):

  queue = [start]

  visited = {start}     # mark on PUSH

  while queue:

    node = queue.pop(0)

    for nbr in graph[node]:

      if nbr not in visited:

        visited.add(nbr)  # mark NOW

        queue.append(nbr)

def dfs(graph, start):

  stack = [start]

  color = {start: GRAY}  # mark on PUSH

  while stack:

    node = stack[-1]

    if all_done(node):

      color[node] = BLACK  # done

      stack.pop()

    else:

      nbr = next_child(node)

      color[nbr] = GRAY    # in-progress

      stack.append(nbr)

You now know what mark-on-pop looks like and why it is wrong for BFS. But would you spot it in real code?

This is the hardest version of the problem because the code works. It compiles, runs without errors, produces the correct set of visited nodes, in the correct BFS order. Nothing about the output says “bug.” The only evidence is a performance number that is higher than it should be -- and unless you are counting enqueues, you will never notice.

Below is a BFS implementation with the mark-on-pop bug hiding in plain sight. The code is clean, well-structured, and uses descriptive variable names. A code reviewer skimming for correctness would approve it. The visited check is there. The queue usage is correct. The neighbor iteration is correct. The bug is not in what the code does -- it is in when the code does it. The visited mark happens at dequeue time instead of enqueue time, which means nodes can be enqueued multiple times before any of those copies gets dequeued and marked.

Your job: find the exact line where the visited mark happens too late, then pick the fix that moves it to enqueue time. The fix is a rearrangement of existing logic, not new code.

Three scenarios, each requiring you to choose the correct marking strategy.

The visited-set timing decision you have been studying is one of those details that separates someone who “knows BFS and DFS” from someone who can implement them correctly under pressure. In an interview, nobody asks “explain mark-on-push versus mark-on-pop.” Instead, you get a graph problem, you write BFS or DFS, and either your visited logic is correct or it introduces a subtle performance bug (BFS) or correctness bug (DFS). The knowledge is tested implicitly through your code, not explicitly through your explanation.

One scenario is a BFS on a dense graph, where mark-on-push prevents the queue explosion you saw earlier. One is a DFS for cycle detection on a directed graph, where three colors are required to distinguish back edges from cross edges. One is a trick question where both strategies produce identical results -- because the graph structure eliminates the conditions that cause them to diverge.

For each scenario, decide: binary visited with mark-on-push, binary visited with mark-on-pop, or three-color DFS? And more importantly -- why? The reasoning matters more than the answer, because in an interview you will face graphs you have never seen before, and the right strategy will depend on what the traversal needs to track.