What is the difference between breadth first searching and level order traversal?

by

For a ‘proper’ tree (see below), it’s the same thing, at least by most definitions. Like Wikipedia, for example:

Breadth-first

See also: Breadth-first search

Trees can also be traversed in level-order, …

… a breadth-first (level-order) traversal …

Well, at least level-order traversal is the same as breadth-first traversal. There are many reasons to traverse something, it doesn’t just have to be to search, as breadth-first search seems to imply, although many (or most) don’t make that distinction and use the terms interchangeably.

The only time I’d personally really use “level-order traversal” is when talking about in-, post- and pre-order traversals, just to follow the same “…-order traversal” format.

For a general graph, the concept of a ‘level’ may not be well-formed (although you could just define it as the (shortest) distance from the source node, I suppose), thus a level-order traversal may not be well-defined, but a breadth-first search still makes perfect sense.

I mentioned a ‘proper’ tree above (which is a totally made up sub-classification, in case you were wondering) – this simply means ‘level’ is defined as you’d expect – each edge increases the level by one. However, one may be able to play around with the definition of ‘level’ a bit (although doing this may not be widely accepted), in essence allowing edges to jump over levels (or even have edges between nodes on the same level). For example:

level
  1          1
            / \
  2        /   3
          /   /
  3      2   4

So the level-order traversal would be 1, 3, 2, 4,
while the breadth-first traversal would be 1, 2, 3, 4.

Leave a Comment