How to Learn Flood Fill: Grid Neighbours, BFS/DFS Frontiers, Connectivity, Stack Safety and Production Image Filling

Wait, What?

A paint-bucket tool is really a graph traversal hiding inside a picture.

Flood fill begins with a seed location and expands through every reachable cell or pixel that belongs to the same region. On a screen it looks like “fill this area.” In algorithmic terms, it is a reachability problem on an implicit graph.

That makes flood fill an unusually good teaching algorithm. A beginner can understand it with coloured squares. An intermediate learner can implement it with a queue or stack. An advanced learner can reason about connectivity, invariants and worst-case memory. A professional must also think about recursion limits, masks, tolerance rules, image mutation, cache locality and the difference between a mathematically connected region and a product’s definition of “similar colour.”

Quick Answer

Learn flood fill in this order: seed cell → neighbour rule → target condition → visited state → DFS/BFS frontier → 4- versus 8-connectivity → complexity → recursion safety → tolerance-based filling → masks → scanline ideas → production testing. The key is to see the image as a graph whose edges are created by your neighbour rule.

1. Begin with four squares, not code

Imagine this grid:

Start at the top-left cell and say that movement is allowed only up, down, left and right through cells containing 1. Which cells belong to the same region?

Before writing code, trace the region by hand. This establishes the central idea: flood fill is not about colour replacement first. It is about reachability under a rule.

2. A grid is an implicit graph

You do not need to build a graph object explicitly. Each eligible cell is a vertex. Two cells are adjacent when your connectivity rule says they are neighbours.

For standard 4-connectivity, the candidate neighbours of (r,c) are:

(r-1,c)
(r+1,c)
(r,c-1)
(r,c+1)

For 8-connectivity, diagonals are included too. This modelling decision changes the answer. Two pixels touching only at a corner are disconnected under 4-connectivity and connected under 8-connectivity.

3. The first invariant: every frontier item is eligible

A robust flood fill has a simple invariant: every cell placed on the frontier has already passed the bounds test, region-membership test and visited test.

That means the traversal loop can focus on processing valid work rather than repeatedly rediscovering invalid work.

4. DFS and BFS solve the same reachability problem

Depth-first search uses a stack; breadth-first search uses a queue. For ordinary flood fill, both eventually visit the same connected region if they use the same neighbour and membership rules.

old = image[sr][sc]
if old == new:
    return

queue = [(sr, sc)]
mark (sr, sc)

while queue not empty:
    r, c = pop_front(queue)
    image[r][c] = new

    for each neighbour (nr, nc):
        if inside(nr, nc)
           and not visited(nr, nc)
           and image[nr][nc] == old:
            mark visited
            push_back(queue, (nr, nc))

The visible order may differ during animation, but the final filled component is the same.

5. Why marking on insertion matters

A common bug marks a cell visited only when it is removed from the queue. Multiple neighbours can then enqueue the same cell before its first processing.

Marking at the moment of insertion ensures each cell enters the frontier at most once. This is a small implementation choice with a large effect on memory and reasoning clarity.

6. The dangerous edge case: old colour equals new colour

If the algorithm uses colour replacement itself as the visited marker, and the replacement colour equals the original colour, the state never visibly changes. A naive implementation can keep rediscovering the same cells.

Handle this before traversal:

if original_colour == replacement_colour:
    return

Alternatively, maintain a separate visited structure.

7. Complexity is about the region you actually visit

If the filled region contains R cells and each cell checks a constant number of neighbours, traversal time is O(R). In the worst case the region is the whole m × n image, giving O(mn).

Memory depends on the frontier and visited representation. A recursive DFS can require recursion depth proportional to a long narrow region. An explicit stack or queue moves that memory into a structure you control.

8. Recursive DFS is elegant—and can still be the wrong production choice

Recursive flood fill is often the clearest first implementation. It mirrors the definition of reachability. But a huge connected region can exceed the language runtime’s call-stack limit.

Professional implementations therefore often prefer iterative DFS, BFS or scanline-style filling. The algorithmic idea is unchanged; the memory discipline is improved.

9. Fixed equality is only one membership rule

In a toy grid, membership may mean “same integer as the seed.” In real image processing, the condition can be more subtle.

OpenCV’s floodFill, for example, supports lower and upper colour/brightness differences and distinguishes fixed-range comparisons against the seed from floating-range comparisons against neighbouring pixels. It also supports masks that stop the fill from crossing selected regions.

This reveals a deeper lesson: the traversal is generic; the region predicate defines the application.

10. A useful separation of concerns

Write flood fill as three conceptual parts:

Neighbour generator: which locations can be adjacent?
Membership predicate: which neighbours count as part of the region?
Action: recolour, count, label, collect, measure or transform the region.

This separation makes the same traversal reusable for image filling, maze regions, connected-component labelling, board games and grid-based simulations.

11. Flood fill and connected components are close relatives

Flood fill from one seed finds one component. Connected-component algorithms repeat that operation: scan the whole grid, and whenever an unvisited eligible cell is found, launch a new fill and assign a new component label.

That is why “number of islands” problems are educationally useful. They show that flood fill is not a special paint-program trick; it is a general component-discovery pattern.

12. Beginner trace: make the frontier visible

Use a table:

step | frontier | cell processed | cells newly discovered

Predict the next frontier before revealing it. Then run the code and compare. This turns an invisible state transition into something observable.

Programming-education research on tracing and worked examples supports this read-before-write approach. Novices benefit from predicting and explaining existing code before being asked to construct an implementation from nothing.

13. Intermediate task: swap BFS for DFS

Once a learner owns the BFS version, change only the frontier discipline. Replace the queue with a stack. Ask what changes and what does not.

The visit order changes. The component does not. This is an excellent test of whether the learner understands the algorithm’s invariant rather than merely memorising code.

14. Advanced task: change connectivity

Switch from 4-neighbour to 8-neighbour connectivity. Before running the program, ask which separate regions will merge.

This exercise teaches that many algorithm errors are really modelling errors. A correct traversal can answer the wrong question if the adjacency relation is wrong.

15. Professional task: design the predicate

Suppose the image contains antialiased edges. Exact equality may fragment what a human sees as one region. Introduce a tolerance. Now ask:

Compare every pixel to the seed or to the previous accepted neighbour?
Use RGB distance, another colour space or channel-wise thresholds?
Can tolerance leak across a gradual gradient?
Should an external mask block certain boundaries?

The professional problem is no longer “write BFS.” It is “define a region in a way that matches the product’s meaning.”

16. Scanline flood fill

Pixel-by-pixel frontier methods are conceptually simple but can push many coordinates. Scanline variants fill horizontal runs and queue neighbouring runs instead. They can reduce frontier overhead and improve locality for large raster regions.

You do not need scanline fill to understand the core algorithm, but it is a useful professional extension because it shows how a mathematically equivalent algorithm can be engineered around memory behaviour.

17. Mutation versus separate labels

Replacing pixels in place is memory-efficient when the image may be modified. But some tasks need the original data unchanged. Then keep a visited mask or output label image.

Choose explicitly. Hidden mutation is a common source of bugs when the caller expects to reuse the source image later.

18. Test against tiny oracles

Good tests include:

a one-cell image;
a seed at every corner;
an entirely filled image;
an image with no eligible neighbours;
a thin snake-shaped region;
diagonal-only contact;
old colour equal to new colour;
very large connected regions;
mask boundaries;
tolerance cases exactly on the threshold.

For small grids, a deliberately simple reference implementation is valuable. Compare the set of filled coordinates rather than only the final image appearance.

19. Learning ladder

Beginner: trace one fill by hand and explain 4-connectivity.
Foundation: implement BFS with explicit visited state.
Intermediate: implement iterative DFS and compare traversal order.
Advanced: generalise the neighbour and membership predicates.
Professional: support tolerance, masks, large-region safety, deterministic testing and workload-aware memory choices.

20. Ownership boundary

This article owns flood fill as an algorithmic learning object: seed-based reachability, grid adjacency, BFS/DFS frontier behaviour, connectivity choices, region predicates and production implementation trade-offs. It does not replace general graph algorithms, image-segmentation theory, computer-vision pipelines, learner measurement, MindOS, Bolt or Student/Studying Interface canonical jobs.

Sources and further reading

OpenCV 4.x image-processing documentation, floodFill: OpenCV.
ACM/IEEE-CS/AAAI CS2023, Algorithmic Foundations: CS2023.
Sue Sentance, Jane Waite and Maria Kallia, PRIMM research on predicting, running, investigating, modifying and making programs: SIGCSE 2019.
Matthew Hassan et al., research on code tracing as a foundational programming skill: SIGCSE 2022.
MIT Teaching + Learning Lab, overview of worked examples for novice learning: Worked Examples.

Professional rule: you understand flood fill when you can define exactly what makes two cells connected, prove every eligible reachable cell is visited once, and choose a traversal and memory strategy that remains safe on the largest region your real workload can produce.

Small Group Tutorials