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.

Answer 2

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

DEFINITION: "The level-order of an ordered tree is a listing of the vertices in the top-to-bottom, left-to-right order of a standard plane drawing of that tree".

Please bear in mind that when we are discussing level-order we are talking exclusively about Trees, and not graphs in general.

And we can be even more specific and say we are discussing about Rooted-Trees.

DEFINITION: "Rooted Tree is a tree with a designated vertex called the root. And each edge is considered to be directed away from the root. Thus, the rooted tree is a directed tree such that the root has indegree = 0 (so no incoming edges)".

*Its important to make the distinction because its this property that allows for the recursive implementation of trees.

Furthermore, level-order traversal would not make sense about a Graph (the tree is one specific type of a graph (no cycle and connected)).

So for graphs we use BFS and the BFS we use for trees has been termed "level-order traversal" (because since we are talking about rooted-trees, then levels do make sense. Whereas in a graph they would not make sense, due to the absence of the root).

Conclusion: Level-order traversal is the breadth-first-search for the case of the specific graph structure named: Tree (specifically Rooted-Trees)

Answer 3

we use level order traversal for trees because in trees there is no cycle and once a node is visited, it is not gonna visit again but in graphs, its is not so. Graph can be cyclic as well and if a graph is cyclic, as per level order if a node is visited, it doesnt check it is visited or not and again it will traverse the same node infinite times. and program will continue to traverse because of cycle. So we use BFS or DFS in case of graph.

Answer 4

In general, traversing is a technique of visiting all the elements only once in a data structure. The process of getting,modifying,checking the data of all nodes in a tree is called Tree Traversal.

Search means looking for an item. It does not mean that you are going to visit all nodes. Let's say you are looking for the first node whose value is less than 10, once you find 10, you exit searching.