Advertisement
Guest User

Untitled

a guest
Aug 25th, 2019
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.07 KB | None | 0 0
  1. /**
  2. * Perform level order traversal for a tree,
  3. * aka Breadth First Search.
  4. *
  5. * @param tree {BinarySearchTree}
  6. * @returns {boolean|[]}
  7. */
  8. function bfs(tree) {
  9. if (!tree.root) {
  10. return false;
  11. }
  12.  
  13. return bfsHandler(tree.root);
  14. }
  15.  
  16. function bfsHandler(root) {
  17. // Use an array as a queue by using some of
  18. // built-in array functions like push and shift.
  19. let queue = [];
  20. // Use an array to track the traversed nodes for
  21. // printing out using console.
  22. let traversedNodes = [];
  23.  
  24. // Enqueue the root node into the queue.
  25. queue.push(root);
  26.  
  27. while (queue.length) {
  28. let current = queue[0];
  29. traversedNodes.push(current);
  30.  
  31. if (current.left) {
  32. queue.push(current.left);
  33. }
  34.  
  35. if (current.right) {
  36. queue.push(current.right);
  37. }
  38.  
  39. // Dequeue the front element in the queue.
  40. queue.shift();
  41. }
  42.  
  43. return traversedNodes;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement