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

Question

I don't need code, just an explanation. My textbook says

level order: each node at level i is processed before any node at level i+1

My understanding of breadth first searching is that you explore nodes nearest the root first, starting from the left? How is this any different? Is this a square and rectangle sort of situation?

Answer 1

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.