Level Order Traversal in Tree

Question

What are the advantage and disadvantages of Level Order Traversal compare to Depth Order Traversal(in-order, pre-order, post-order) ?

What is your application, tree traversal methods are used generally for specific applications. You might want to start with the wikipedia page. — UglyCode, Nov 11 '15 at 19:15

score 0 · Answer 1 · answered Dec 01 '15 at 14:14

0

I think your problem is the same as Breadth-First-Search VS Depth-First-Search. I couldn't say which is better. It is depend on your application.

answered Dec 01 '15 at 14:14

liuniandxx

1
1

this looks like a comment. not answer – Tejus Prasad Dec 01 '15 at 14:15
Level Order Traversal and Depth Order Traversal have same time complexity and space complexity. – liuniandxx Dec 01 '15 at 14:19

score 0 · Answer 2 · edited May 23 '17 at 12:15

Here : Breadth First Vs Depth First, you can find a good explanation of the two methods (given that by level order you mean a particular kind of breadth search). The pro/cons of the two are various:

if you expect to find data quite up in the graph, than BFS would be better in time since passes to the next depth level only after having explored the whole super-level. If you instead expect to find a node quite at the bottom of the graph, DFS is better for the opposite reason.
if the graph/tree is huge, and particularly large (nodes with lots of children/adjacencies for each level), the queue that BFS implements will require a lot of memory, while the stack memory of the vertical recursive call should be reasonably smaller, so DFS could be preferable: here too, the opposite for really narrow graphs.
for paths in the graph, BFS will always return first the shortest path it encounters, while DFS could return first a path that's not necessarily the shortest.
both have same worst case time complexity (if the required node is the last one you encounter).

Level Order Traversal in Tree

2 Answers2