Binary tree level order traversal

by

Level order traversal is actually a BFS, which is not recursive by nature. It uses Queue instead of Stack to hold the next vertices that should be opened. The reason for it is in this traversal, you want to open the nodes in a FIFO order, instead of a LIFO order, obtained by recursion

as I mentioned, the level order is actually a BFS, and its [BFS] pseudo code [taken from wikipedia] is:

1  procedure BFS(Graph,source):
2      create a queue Q
3      enqueue source onto Q
4      mark source
5      while Q is not empty:
6          dequeue an item from Q into v
7          for each edge e incident on v in Graph:
8              let w be the other end of e
9              if w is not marked:
10                 mark w
11                 enqueue w onto Q

(*) in a tree, marking the vertices is not needed, since you cannot get to the same node in 2 different paths.

More Related Contents:

  1. An algorithm for inflating/deflating (offsetting, buffering) polygons
  2. Looping in a spiral
  3. Fastest sort of fixed length 6 int array
  4. How do I check if a number is a palindrome?
  5. Algorithm to compare two images
  6. Finding out nth fibonacci number for very large ‘n’
  7. Programmatically obtaining Big-O efficiency of code
  8. What is the best way to get the minimum or maximum value from an Array of numbers?
  9. How does one convert 16-bit RGB565 to 24-bit RGB888?
  10. Is there an algorithm that tells the semantic similarity of two phrases
  11. Worst case for QuickSort – when can it occur?
  12. Find the first un-repeated character in a string
  13. Find the set of largest contiguous rectangles to cover multiple areas [duplicate]
  14. Undo/Redo implementation [closed]
  15. Box stacking problem
  16. What are good examples of genetic algorithms/genetic programming solutions? [closed]
  17. How can I programmatically determine how to fit smaller boxes into a larger package? [closed]
  18. How to find convex hull in a 3 dimensional space
  19. How do I find a factorial? [closed]
  20. Calculating the position of points in a circle
  21. What are the differences between segment trees, interval trees, binary indexed trees and range trees?
  22. Time Complexity of two for loops [duplicate]
  23. Sign of a symbolic algebraic expression
  24. Shortest path to transform one word into another
  25. Algorithm to simplify a weighted directed graph of debts
  26. Calculating frames per second in a game
  27. Why are hash table expansions usually done by doubling the size?
  28. Find local minimum in n x n matrix in O(n) time
  29. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1
  30. Tetris Piece Rotation Algorithm

Leave a Comment