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?

Bogosian

Afaik, there's no difference; you can use "breadth-first" and "level-order" interchangeably. – Curd

^This. Everyone seems to define them separately but they literally do the same thing. – Bogosian

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.

Feral

Can trees even use levels in that sort of way? I have never seen that before. – Bogosian

@Bogosian I haven't either, I'm just accounting for the possibility. If "level" has a meaning in your data that doesn't correspond to the meaning of "level" in trees, you could (somewhat confusingly) use level-order traversal to mean traversing that order. – Feral

@Dukeling: I think that would be a "weight-order" traversal, which would you get by using a priority-queue instead of a FIFO queue in the implementation of the traverse (i.e. Dijkstra's algorithm). That's clearly meaningful, even in the case of a general graph, and is even useful. I don't recall hearing the phrase "weight-order traversal" before, but that may be my deteriorating memory; Google was kind enough to find a number of uses of the phrase, including papl.cs.brown.edu/2013/… – Curd

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)

Bohrer

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.

Katusha

I guess based on this interpretation level-order-traversal implies a specific kind logic used in the implementation (not checking whether a node has been visited before or not) while BFS/DFS implies a different kind of underlying logic in the implementation (actually checking if a node has been visited before or not). Correct? – Courser

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.

Irregularity

Answer 5

here is one difference I have come across while doing Leetcode practice problems. Generally, what I have seen in breadth first search is that you have a while loop which is popping nodes from the queue, and for each node you add its children to the queue.

One of the problems that was not in the "BFS" section but rather in the binary tree section, and was called "level order traversal", was asking you to group the nodes into a list of lists where each node in the same level was grouped into the same list. The way of accomplishing this was a slightly tweaked version of the BFS algorithm, where it is done in batches that are corresponding to each level. the way of accomplishing this is by having something like:

level =0
    while len(queue)>0:
        l = len(queue)
        thisLevel =[]
        for i in range(l):
            thisNode = queue.pop(0)
            thisLevel.append(thisNode.val)
            if thisNode.left is not None:
                queue.append(thisNode.left)
            if thisNode.right is not None:
                queue.append(thisNode.right)
        level+=1
        final.append(thisLevel)

Note that there is not only the while loop in here, but also an inner loop which iterates over each level in a batch. the reason for this is so that each time you get to the top of the while loop, all of the nodes in the queue will always have the same level. so by evaluating the length of the queue after each batch, you know how to take only the nodes of the same level (even though you are adding more nodes in the queue for the next level as you process within the level).

At least in LeetCode, this creates a semantic distinction between "DFS" and "Level order Traversal", in that Level Order Traversal is a special case of DFS wherein you process each level in a batch by measuring the length of the queue, and then running an inner loop to add the next level while processing the current level, then measuring the length again, etc.

Perhaps this distinction doesn't correspond to computer science definitions, but it is at least apparently being used soemwhere in practice. And it makes sense to me, because of the emphasis of processing each level in batches.

Vagina