Levelorder Traversal

[Vijay0753]

Given a binary tree, write a function to perform a level order traversal and return a vector of integers containing the data of the visited nodes in the correct order.

  vector<int> level_order(treeNode* root)
{        
    vector<int> level_ordered_list ;//= new vector<int>();           
    if (root == NULL) return level_ordered_list;
    queue<treeNode*> que;
    treeNode* ptr;
    que.push(root);          /* Insert the root node in the queue */

    while(!que.empty()) {
        ptr = que.front();      /* get a Tree node from head of the queue */
        que.pop();
        if (ptr != NULL)
            level_ordered_list.push_back(ptr->value);        /* mark the node visited */
        if (ptr->left != NULL) /* move the left child node of the tree node in the queue */
            que.push(ptr->left);  
        if (ptr->right != NULL) /* move the right child node of the tree node in the queue */
            que.push(ptr->right);   
    } 
    return level_ordered_list;
}

Here, in the while loop, the pointer is being made to point to the root in the queue first, it is popped right after. Does this not cause the pointer to point to NULL in the queue?

[dutch]

Does this not cause the pointer to point to NULL in the queue?

No, although your question is hard to understand.

#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
using namespace std;

struct treeNode {
    int value;
    treeNode *left, *right;
    treeNode(int n) : value{n}, left{}, right{} {}
};

vector<int> calc_level_order(treeNode* root) {
    vector<int> level_order;
    if (!root) return level_order;
    queue<treeNode*> que;
    que.push(root);
    while (!que.empty()) {
        treeNode *ptr = que.front(); que.pop();
        level_order.push_back(ptr->value);
        if (ptr->left)  que.push(ptr->left);
        if (ptr->right) que.push(ptr->right);
    }
    return level_order;
}

void print(treeNode* node) {
    if (!node) return;
    print(node->left);
    cout << node->value << ' ';
    print(node->right);
}

void print(treeNode* node, int indent) {
    if (!node) return;
    print(node->right, indent + 1);
    cout << setw(indent * 4) << "" << node->value << '\n';
    print(node->left, indent + 1);
}

void insert(treeNode*& root, int n) {
    if (!root) root = new treeNode(n);
    else {
        treeNode** node = &root;
        while (*node)
            node = n < (*node)->value ? &(*node)->left : &(*node)->right;
        *node = new treeNode(n);
    }
}

int main() {
    treeNode* root = nullptr;
    for (int n: {6, 4, 7, 8, 5, 1, 3, 9, 0, 2}) insert(root, n);
    print(root, 0); cout << '\n';
    auto level_order = calc_level_order(root);
    for (int n: level_order) cout << n << ' '; cout << '\n';
}

[Vijay0753]

while(!que.empty()) {
        ptr = que.front();      /* get a Tree node from head of the queue */
        que.pop();
        if (ptr != NULL)

My question is, initially we make the pointer point to the front of the queue, correct?
Now it contains the root of the tree.

Right after that, when we pop the queue, doesn't the pointer lose access to the root? How does this work?

[dutch]

No, ptr doesn't "point to the front of the queue".
Instead, ptr is set equal to the pointer that is stored in the front of the queue, which initially is root (due to the initial que.push(root)).
So ptr equals root.
Then that entry (root) is popped off of the queue.
But that's okay, since ptr has already copied it.

[Vijay0753]

Thanks dutch