CODEWITHSUNDEEP
algorithmbinary-search-treegraph-theorybreadth-first-search
munchschair
munchschair

Reputation: 1683

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

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?

Upvotes: 37

Views: 24175

Answers (5)

Paul
Paul

Reputation: 1176

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.

Upvotes: 0

Yilmaz
Yilmaz

Reputation: 49301

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.

Upvotes: 1

Kejsi Struga
Kejsi Struga

Reputation: 560

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.

enter image description here

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)

Upvotes: 3

SUMIT LOHAN
SUMIT LOHAN

Reputation: 47

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.

Upvotes: 1

Bernhard Barker
Bernhard Barker

Reputation: 55609

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.

Upvotes: 30

Related Questions