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?
Level Order traversal is also known as Breadth-First Traversal since it traverses all the nodes at each level before going to the next level (depth).
Breadth-first search (BFS) is a method for exploring a tree or graph. In a BFS, you first explore all the nodes one step away, then all the nodes two steps away, etc. Breadth-first search is like throwing a stone in the center of a pond.
BFS, stands for Breadth First Search. DFS, stands for Depth First Search. BFS uses Queue to find the shortest path. DFS uses Stack to find the shortest path.
Level Order Traversal is the algorithm to process all nodes of a tree by traversing through depth, first the root, then the child of the root, etc. How do you do level order traversal? Level order traversal can be done by using a queue and traversing nodes by depth.
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
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With