Levelorder traversal of a BST

Problem Statement - link #

Levelorder traversal means traversing through the tree level by level, from left to right. Given a BST, find its level-order traversal.

Your Task: You don’t need to read input or print anything. Complete the function levelOrder() that takes the root of the BST as input parameter and returns a list of integers containing the level-order traversal of the BST.

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

Examples #

Example 1:

Input:
    30
   /
 10
   \ 
   20
Output: 30 10 20

Example 2:

Input:
      5
    /   \
   2     7
   \      \
    3      8
Output: 5 2 7 3 8

Constraints #

• 1 <= Number of nodes <= 10^5
• 1 <= Data of a node <= 10^5

Solutions #

// Function to return the level order traversal of a BST.
vector<int> levelOrder(struct Node* node) {
    // code here
    vector<int> v;
    queue<Node*> q;
    q.push(node);
    while (!q.empty()) {
        Node *p = q.front();
        q.pop();
        v.push_back(p->data);
        if (p->left != NULL)
            q.push(p->left);
        if (p->right != NULL)
            q.push(p->right);
    }
    return v;
    
}