Level Order Traversal - Binary Tree Traversal

Welcome Folks!

From Today, we are going to start our Binary Tree Traversal series. In this article, we are going to see Level order Traversal which is one of the traversing algorithms used to traverse the level-wise paths to every node of a binary tree.

Prerequisite: Basic Knowledge of Queue / Loops / Reference variables

So let’s start our article with what is Tree ?.

A Binary tree is a data structure similar to a linked list but instead of each node pointing simply to the next node in a linear fashion, each node points to at most 2 nodes. It is a non-linear data structure (hierarchical). Component of a Binary Tree –

1. Root Node
2. Edges
3. Leaf Node
4. Child Node
5. Parent Node

Edge refers to the link from parent to child. A node with no children is called a leaf node Each node has at most two children, which are referred to as the left child and the right child except the root node. The root of a tree is the node with no parents.

The set of all nodes at a given depth is called the level of the tree (8 and 4 are on the same level) and the root node (2) is at level zero.

[5, 1, 3] are the leaf nodes.

If we apply the level order traversal on the above binary tree then the output will be:

Output: 2, 8, 4, 5, 1, 3

• 2 -> root node 0 level
• 8, 4 -> Level 1 nodes
• 5, 1, 3 -> Level 2 nodes

Implementation:

There is a recursive approach to do this but it takes O (n^2). So we are going to use some space (Queue) + recursive approach to reduce the time complexity to O (N).

Algorithm (By visiting means pushing the node to the queue)

Visit the root (Push the root in Queue).

1. While traversing level L, keep all the elements at level L+1 in the queue.
2. Go to the next level and visit all the nodes at that level).
3. Repeat the above steps until all levels are processed/traversed (Queue gets empty).

Explanation

As we can see 2 is our root node so according to our algorithm. We will visit root node first by visiting means inserting the node into our queue. Queue is storing the ref/address of the node not the data of the nodes.

Currently, we are at Level 0 and we have completed our first step. Now apply the second step of the algorithm So we have to keep all elements of level +1 which is level 1 in the queue by following these steps

1. Go to the queue store the front element in another variable let’s name the variable as currentNode and pop the front element of the queue and print the front Node.

2. Check whether currentNode has left child if yes then push it to the queue.

1. Check whether currentNode has the right child if yes then push it to the queue

Currently, we are at Level 1 and we have completed our first step. Now apply the second step of the algorithm So we have to keep all elements of level +1 which is level 2 in the queue

• Go to the queue store the front element in another variable (currentNode) and pop the front element of the queue and print the front Node.

2 is already printed so now we have 8 in the front of the queue. so first, we will store it in currentNode and then we will pop it and print it.

• Check whether currentNode has left child if yes then push it to the queue

• Check whether currentNode has the right child if yes then push it to the queue

Again pop the first element of the queue. 2, 8 are already printed so now we have 4 in the front of the queue. so first, we will store it in currentNode, and then we will pop it and print it.

• Check whether currentNode has left child if yes then push it to the queue.

as we do not have any left node for this current node so we will proceed further.

• Check whether currentNode has the right child

Here we are at the last level of the tree so once again we will follow the same steps as we do not have any left and right children nodes then it will be printed in the same order.

[2,8,4] is already printed so now 5 then 1 then 3 will pop out of the queue and will be printed

Final output: 2, 8, 4, 5, 1, 3

Implementation

vector<int> levelOrder(Node* node)
    {
      vector<int> ans;
      if(node==NULL){return ans;}

      queue<Node*> q;
      q.push(node);

      while(!q.empty())
      {
          int c = q.size();
          Node * currentNode= q.front();
          q.pop();

          ans.push_back(currentNode->data);
//either we can store or we can print

          if(currentNode->left){
              q.push(currentNode->left);
          }
          if(currentNode->right){
              q.push(currentNode->right);
          }
      }
      return ans;

    }

Conclusion

• Space Complexity: O(n)
• Time Complexity: O(n)

So stay tuned with us on this journey of Competitive Programming.

I hope you liked it!. Let's catch up in the next articles.

Practice Link: Click Here

If you liked it, Please Support Me