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;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.