Level Order Traversal

Raunit Verma September 04, 2021

Level Order Traversal

Given a binary tree, find its level order traversal.

Level order traversal of a tree is breadth-first traversal for the tree.

Example 1:

Input:
    1
  /   \ 
 3     2
Output:1 3 2

Example 2:

Input:
        10
     /      \
    20       30
  /   \
 40   60
Output:10 20 30 40 60 N N

Your Task:
You don't have to take any input. Complete the function levelOrder() that takes the root node as input parameter and returns a list of integers containing the level order traversal of the given Binary Tree.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Constraints:
1 ≤ Number of nodes ≤ 105
1 ≤ Data of a node ≤ 105

Solution- Here we use the BFS that is Breadth First Traversal. With the help

of queue, we can easily do that and store the value in a vector. We then make a temporary Node* temp and set the value as the current node. Now we push the adjacent nodes in the queue and the value of temp in the vector. At last, we simply pop out the front element and this continues until the queue is empty. we simply return the vector and it's done.

Solution to the Above Question

class Solution
{
    public:
    
    vector<int> levelOrder(Node* node)
    {   vector<int>v;
        if(node==NULL){
            return v;
        }
      queue<Node*>q;
      q.push(node);
     
      while(!q.empty()){
          Node* temp=q.front();
            v.push_back(temp->data);
            if(temp->left!=NULL){
                q.push(temp->left);
            }
            if(temp->right!=NULL){
                q.push(temp->right);
            }
            q.pop();
      }
      return v;
    }
};