Pop function in queue doesn't seem to work in loop

July 14, 2023

I created Binary Tree (Abstract data type) using template .

#include <bits/stdc++.h>

using namespace std;


template <typename T>class BinaryTree{
public:
    T data;
    BinaryTree*first;
    BinaryTree*second;
    BinaryTree(){
        data=-1;
        first=nullptr;
        second=nullptr;
    }
    BinaryTree(T data){
        this->data=data;
        first=nullptr;
        second=nullptr;
    }
};
template <typename T>BinaryTree<T>*InputBinaryTree(){
   cout<<"Enter root element : "<<endl;
    T data;
    cin>>data;
    BinaryTree<T>*root=new BinaryTree<T>(data);
    queue<BinaryTree<T>*>childrenholder;
    childrenholder.push(root);
    while(!childrenholder.empty()){
                BinaryTree<T>*rooty=childrenholder.front();
                cout<<"Enter first child of "<< rooty->data <<" : "  <<endl;
                T first;
                cin>>first;
                cout<<"Enter second child of "<< rooty->data <<" : "  <<endl;
                T second;
                cin>>second;
                if(first!=-1){
                        BinaryTree<T> * firsty=new BinaryTree<T>(first);
                        rooty->first=firsty;
                        childrenholder.push(firsty);

                }
                if(second!=-1){
                        BinaryTree<T> * secondy=new BinaryTree<T>(second);
                        rooty->second=secondy;
                        childrenholder.push(secondy);
                }
                childrenholder.pop();
    }
    return root;
}
template <typename T>void OutputBinaryTree(BinaryTree<T>*root){
    cout<<root->data<<endl;
    queue<BinaryTree<T>*>childrenholder;
    childrenholder.push(root);
    while(!childrenholder.empty()){
            BinaryTree<T>*rooty=childrenholder.front();
            BinaryTree<T>*firsty=rooty->first;
            BinaryTree<T>*secondy=rooty->second;
            if(firsty->data!=-1){
                cout<<firsty->data<<" , ";
                childrenholder.push(firsty);

            }
            if(secondy->data!=-1){
                cout<<secondy->data<<" ";
                childrenholder.push(secondy);
            }
            cout<<endl;
            childrenholder.pop();
    }
}

int main(){
    BinaryTree<int>*root;
    root=InputBinaryTree<int>();
    OutputBinaryTree<int>(root);

}

class BinaryTree – Binary Tree class.

InputBinaryTree() – function used to get input for binary tree.

OutputBinaryTree() – function used to print binary tree.

childrenholder – queue is used to get element of children of a node.

I considered only Integer as Input. I got input for binary tree in level order wise and expect to print the binary tree in level order wise as well. I am getting error while executing OutputBinaryTree(). Especially on the looping statement of the OutputBinaryTree(). The looping statement doesn’t seem pop the elements in childrenholder queue.

Input given:

Enter root element :
1
Enter first child of 1 :
2
Enter second child of 1 :
4
Enter first child of 2 :
-1
Enter second child of 2 :
3
Enter first child of 4 :
5
Enter second child of 4 :
6
Enter first child of 3 :
-1
Enter second child of 3 :
-1
Enter first child of 5 :
-1
Enter second child of 5 :
-1
Enter first child of 6 :
-1
Enter second child of 6 :
-1

-1 is assumed as no element is present at that node.

Output expected:

1
2 , 4
3 , 5 , 6

Output received:

1
2 , 4

exits.

>Solution :

Your input section does not add a child if the user’s input is -1; the child in that case is the null pointer, not a node with a -1 value.
Then your output section assumes that every valid node has two non-null children, "empty" indicated by a value of -1, and you dereference those pointers unconditionally.
And dereferencing a null pointer is a big no-no.

The output conditions should be