-4

I’m trying to implement a level-order traversal of a binary tree in C++ without using recursion. The goal is to traverse the tree level by level, starting from the root, and print the nodes in the correct order.

I’ve read that this can be done using a queue, but I’m struggling with a few details:

How do I initialize and use a std::queue to store the nodes for traversal? What is the correct way to enqueue the left and right children of a node? How do I ensure that the loop stops after processing all nodes? Are there any edge cases I need to handle, such as an empty tree or a tree with only one node?

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

Here’s a basic structure of my binary tree:

I’ve written some code, but it doesn’t seem to work correctly, and I keep running into segmentation faults when I try to access child nodes. Can someone explain the correct approach to implement this traversal and help me understand what might be going wrong?

I tried implementing level-order traversal using a std::queue in C++. My idea was to enqueue the root node, then repeatedly dequeue the front node, process its value, and enqueue its left and right children (if they exist).

Here’s what I tried:

#include <iostream>
#include <queue>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void levelOrderTraversal(TreeNode* root) {
    std::queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();

        std::cout << current->val << " ";

        if (current->left != nullptr) {
            q.push(current->left);
        }
        if (current->right != nullptr) {
            q.push(current->right);
        }
    }
}

I expected this code to print the level-order traversal of the tree.

However, I ran into some issues:

Segmentation Fault: The program crashes when the tree is empty, or when trying to access current->left or current->right for a node that doesn’t exist. Incorrect Output: In some cases, the traversal order isn’t as expected, and I’m unsure if my queue operations are correct. I’m not sure how to handle these problems effectively. How should I modify my code to handle edge cases like an empty tree or ensure the traversal order is correct? Any guidance would be greatly appreciated!

Improve this question
5
  • 3
    Please post a minimal reproducible example Commented Jan 5 at 1:06
  • 1
    "The program crashes when the tree is empty" I suppose you should check whether root is null before pushing it into the queue. "when trying to access current->left or current->right for a node that doesn’t exist" How did "node that doesn't exist" end up in the queue to begin with? This suggests that the code that constructs the tree (not shown) is already problematic. Commented Jan 5 at 1:10
  • 1
    Please create a main function that builds the tree that causes the issue. Commented Jan 5 at 2:12
  • One question per question. You should focus on one of your segmentation faults ("when the tree is empty" and "when trying to access current->left or current->right for a node that doesn’t exist" should be assumed to be distinct seg faults until proven otherwise), rather than question your entire approach. Which line causes the fault, and what are the values of your variables at that point? Commented Jan 5 at 2:13
  • Is that real node? Absence of rule 3/5/0 compliance may result in that the code that generates tree is incorrect and leads to UB. Commented Jan 5 at 2:29

2 Answers 2

Reset to default
2

There are three places in your code where you push a node in the queue. Two of them are conditional. It is inconsistent that the first occurrence is not conditional, and this is the cause of the error you got.

If you make the first one conditional too, it will work. In fact, you could just exit if the tree happens to be empty:

if (!root) return;

But if you prefer to use the same if construct as you did for the other push calls, then that is fine too, and has a nice consistency to it. To avoid code repetition you could put this conditional-push logic in a function:

void pushIfNotNull(std::queue<TreeNode*> &q, TreeNode* node) {
    if (node) q.push(node);
}

void levelOrderTraversal(TreeNode* root) {
    std::queue<TreeNode*> q;
    pushIfNotNull(q, root);
    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();
        std::cout << current->val << " ";
        pushIfNotNull(q, current->left);
        pushIfNotNull(q, current->right);
    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

pushIfNotNull could become even more concise by defining it as a lambda inside the method. :)
1

Right now you're trying to prevent null pointers from being pushed into the queue, and when you traverse the tree, relying on the fact that you won't encounter any null pointers.

One way to make it work is to check whether the root you're passed is a null pointer, and if so, just return.

I think it's simpler to allow null pointers to go in the queue, but make sure the traversal function doesn't mis-behave when it encounters them.

void breadthFirstTraversal(TreeNode* root) {
    std::queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();

        if (current != nullptr) {
            std::cout << current->val << " ";
            q.push(current->left);
            q.push(current->right);
        }
    }
}

At least as I've written it, this does have the disadvantage of making the queue larger by storing null pointers into the queue. If that's really a problem, you can do like your code does, and only push them if they're not null. But given a choice, I prefer the simplicity of only having to care/check for null pointers in one place.

Improve this answer

6 Comments

Difficult? Can't you just do an if (root == nullptr) return;?
@nocomment: Yes, you can do that pretty easily (you're simply changing the expectations). But it's kind of self contradictory--on one hand, trying to ensure against encountering a null pointer, but also trying to deal with what happens if you do encounter one.
What do you mean with changing expectations?
@nocomment: Just that you don't have a consistent expectation throughout the code. Some places you expect a possibly null pointer, other places you don't (and you need to look at the entirety of the code to separate which parts expect what).
Meh, I don't really see a difference in that regard or in difficulty. Both ways are equally trivial. I actually would've done it the same way you did, but only because it's less code. The other way isn't difficult and doesn't need avoiding calling the function. Your second paragraph is just wrong.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.