Print Level Wise Binary Tree in C++

Question

The output is giving - Runtime Error (SIGSEGV). What could be the problem?

QUestion:

Given a binary tree, print the tree in level wise order. For printing a node with data N, you need to follow the exact format - N:L:x,R:y wherer, N is data of any node present in the binary tree. x and y are the values of left and right child of node N. Print -1. if any child is null. There is no space in between. You need to print all nodes in the level order form in different lines. Input format : Elements in level order form (separated by space) (If any node does not have left or right child, take -1 in its place) Sample Input :

8 3 10 1 6 -1 14 -1 -1 4 7 13 -1 -1 -1 -1 -1 -1 -1

Sample Output :

8:L:3,R:10 3:L:1,R:6 10:L:-1,R:14 1:L:-1,R:-1 6:L:4,R:7 14:L:13,R:-1 4:L:-1,R:-1 7:L:-1,R:-1 13:L:-1,R:-1

Here is the code:

// Following is the Binary Tree node structure
/**************
class BinaryTreeNode {
    public : 
    T data;
    BinaryTreeNode<T> *left;
    BinaryTreeNode<T> *right;

    BinaryTreeNode(T data) {
        this -> data = data;
        left = NULL;
        right = NULL;
    }
};
***************/

    void printLevelWise(BinaryTreeNode<int> *root) {
        if(root == NULL){
            return;
        }
        cout << root->data << ":";
        queue<BinaryTreeNode<int>*> pendingNodes;
        pendingNodes.push(root);
        while(pendingNodes.size() != NULL){
            BinaryTreeNode<int>* front = pendingNodes.front();
            pendingNodes.pop();
            if(front->left->data != -1){
                cout << "L:" << front->left->data << ",";
                pendingNodes.push(front->left);
                }
            else if(front->left->data == -1){
                cout << "L:" << "-1" << ",";
            }
            if(front->right->data != -1){
                cout << "R:" << front->right->data;
                pendingNodes.push(front->right);
            }
            else if(front->left->data == -1){
                cout << "R:" << "-1";
            }
            cout << endl;


        }
        /* Don't write main().
         * Don't read input, it is passed as function argument.
         * Print output and don't return it.
         * Taking input is handled automatically.
         */

    }

Answer 1

if(front->left->data != -1) when your subtree not contain left node and you are checking left->data!=-1 thats why you are getting Runtime Error (SIGSEGV)

Use this code

/**************
class BinaryTreeNode {
    public : 
    T data;
    BinaryTreeNode<T> *left;
    BinaryTreeNode<T> *right;

    BinaryTreeNode(T data) {
        this -> data = data;
        left = NULL;
        right = NULL;
    }
};
***************/

    void printLevelWise(BinaryTreeNode<int> *root) {
        if(root == NULL){
            return;
        }
        queue<BinaryTreeNode<int>*> pendingNodes;
        pendingNodes.push(root);
        while(pendingNodes.size() != NULL){

            BinaryTreeNode<int>* front = pendingNodes.front();
            pendingNodes.pop();
            cout << front->data << ":";
            if(front->left){
               if(front->left->data != -1){
                cout << "L:" << front->left->data << ",";
                pendingNodes.push(front->left);
                }
            else{
                cout << "L:" << "-1" << ",";
               }
            }
           if(front->right){
            if(front->right->data != -1){
                cout << "R:" << front->right->data;
                pendingNodes.push(front->right);
              }
            else{
                cout << "R:" << "-1";
            }
           }
        }
        /* Don't write main().
         * Don't read input, it is passed as function argument.
         * Print output and don't return it.
         * Taking input is handled automatically.
         */

    }

Answer 2

As the description says, you should print "-1" if a child is null.
It does not say that you should print "-1" if the child's data is -1.
This would be the same as printing the data, so it would not be described as a special case.
(It is very important to read problem descriptions thoroughly. I think you're confusing this with the program's input format, which has -1 to indicate the absence of a child node, but that's not the input to your function.)

You need

if(front->left != nullptr) {
    cout << "L:" << front->left->data << ",";
    pendingNodes.push(front->left);
}
else {
    cout << "L:" << "-1" << ",";
}

(You're also going to need to adjust how you print commas, but that's a different problem.)

Answer 3

void printLevelWise(BinaryTreeNode<int> *root)
{
    if (root == NULL)
    {
        return;
    }
    queue<BinaryTreeNode<int> *> pendingNodes;
    pendingNodes.push(root);
    while (pendingNodes.size() != NULL)
    {

        BinaryTreeNode<int> *front = pendingNodes.front();
        pendingNodes.pop();
        cout << front->data << ":";

        if (front->left)
        {
            if (front->left->data != -1)
            {
                cout << "L:" << front->left->data << ",";
                pendingNodes.push(front->left);
            }
        }
        else
        {
            cout << "L:"<< "-1"<< ",";
        }


        if (front->right)
        {
            if (front->right->data != -1)
            {
                cout << "R:" << front->right->data;
                pendingNodes.push(front->right);
            }
        }
        else
        {
            cout << "R:"<< "-1";
        }

        cout<<endl;
    }

}