Tree Traversals: Breadth-First Search (BFS)

Tree Traversals: Breadth First Search (DFS)

The term traversal means to visit each node in a tree exactly once. In linear lists the order of traversal is vividly first to last. However, in trees there exists no such natural linear order.In this article, breadth first search is studied.

Tree Traversal : BFS

More Information About BFS:

  1. BFS can be defined as an algorithm dedicated to traversing a tree structure, level by level or depth by depth.
  2. This category of tree traversal initializes from the root node and explores all the adjacent nodes on a current level and then moves on to the next level, and so on.

Why Queue is better to traverse than Recursion?

  1. Queues improves the time complexity because recursion gives the time complexity of O(2^n) in the worst case, whereas queue gives time complexity of O(n).
  2. Height of the tree is first calculated to print level order but this is not required in queue.
  3. Implementation is shorter in queues.

Algorithm (Queue):

  1. If the root is NULL, return.
  2. Otherwise push the root in queue.
  3. Print the node’s data and add its left and right child.
  4. Pop the node from the queue.
  5. Repeat until the queue is empty.

Algorithm (Recursion):

  1. Calculate height of tree.
  2. Initialize loop from 0 to height
  3. Recursive call for left and right subtree and decrease level by 1.
  4. If level is 0, print the nodes
Example Of BFS : Tree Traversal BFS