CODEWITHSUNDEEP
c++algorithmbinary-treetraversal
Rakhi
Rakhi

Reputation: 21

level order traversal of binary tree c++

Hi I read this logic over internet and tried implementing the level order tree traversal in c++

void levelorder(struct node* root)
{
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    std::queue<node*> qq;

    if(root==NULL)
    {
        return;
    }
    qq.push(root);

    while(!qq.empty())
    {
        temp=qq.front();
        qq.pop();
        printf("%d",temp->data);
        qq.push(temp->left);
        qq.push(temp->right);
    }
}

But the above is giving me an error segmentation fault which I think is happening because

temp->left

does not exist. Or should i need llQueue for this implementation.Anybody has any idea about this ?

Upvotes: 2

Views: 713

Answers (3)

Danqi Wang
Danqi Wang

Reputation: 1637

Two problems:

  1. the memory allocated for temp is leaked and non-necessary
  2. null pointer at leaf nodes not checked

The implementation proposed by @anumi is correct. But I'd prefer this:

void levelorder(struct node* root)
{
    if(!root) return;
    std::queue<node*> qq;
    qq.push(root);
    while(!qq.empty())
    {
        struct node* node = qq.front();
        qq.pop();
        printf("%d", node->data);
        if(node->left) qq.push(node->left);
        if(node->right) qq.push(node->right);
    }
}

Edit: handle empty tree according to comments.

Upvotes: 2

Codor
Codor

Reputation: 17605

Your idea seems correct, however this is impossible to tell without knowing the actual data. In your code, it might be possible that the left and right members are NULL or point to undefined locations, which means that following the left or right pointers might result in errors.

Upvotes: 0

anumi
anumi

Reputation: 3947

Ths posted code does not take into account the null pointers at the leaves of the tree. It can be fixed along these lines:

void levelorder(struct node* root)
{
    std::queue<node*> qq;
    qq.push(root);
    while(!qq.empty())
    {
        struct node* node = qq.front();
        qq.pop();
        if (node) {
            printf("%d",temp->data);
            qq.push(temp->left);
            qq.push(temp->right);
        }
    }
}

On the other hand, the memory allocation to temp is lost: This space is not freed and, moreover, will leak, as temp is assigned to somethig else.

Upvotes: 3

Related Questions