Level Order Traversal

 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<intlevelOrder(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;
    }
};

Post a Comment

0 Comments