binary tree problem with printing. The user input does not print anything

Question

I am trying to create and print a binary tree by user input but it's not working. I am providing input 8 3 10 1 6 14 4 7 13 -1 but nothing is printing. What am I doing wrong?

#include<iostream>
#include<queue>
using namespace std;
class node
{public:
    int data; //data for node
    node* left;//pointer for left subtree
    node* right;//pointer for right subtree
    node(int d):data(d),left(NULL),right(NULL) //constructor
    {

    }
};

node* createTree() //creating tree
{
    int d;
    cin>>d;
    if(d==-1)
    {
        return NULL; //when user inputs -1 return NULL
    }

    node* root=new node(d);
    root->left=createTree();
    root->right=createTree();
    return root;
}

void printTree(node* root)
{
    if(root==NULL)
    {
        return; //when null is encountered return
    }

    cout<<root->data<<" ";
    printTree(root->left); //printing recursively left subtree
    printTree(root->right);//printing recursively right subtree
}

int main()
{
   node* root=createTree(); 
   printTree(root);
   return 0;
}

Answer 1

This code is forming a tree starting from the left side and it will keep adding nodes to the left subtree recursively till you enter a -1.

i am providing input 8 3 10 1 6 14 4 7 13 -1 but nothing is printing

By entering -1, you are only ending the left subtree of 13. After which the program expects an input for the right subtree of 13 and so on. Hence you need to enter as many -1s as many leaves you have and a -1 every time you want to switch to the right subtree.

I recommend you to dry run your code on paper to understand how the nodes are being added.

Answer 2

I hightly recommend restructuring your program such that it will handle input values differently. So, you're problem was with how you were handling invalid input values. When you would reach an invalid input value at the left child, you would then query for user input again. Also, for each recursive call you were pushing another input prompt that would have to be reevaluated on the stack unwind. To see this occur, put something like cout << ">>>"; before the cin >> d. After doing this input these values 10 1 6 14 4 7 13 -1 -1 -1 -1 -1 -1 -1 -1. Since you pushed 7 values on i.e 10 1 6 14 4 7 13`, each one of these calls is expecting another input on callback, so your createnode signal whether or not to conitnue.

Here is a modified version that follows a similar input pattern.

#include<iostream>
#include<queue>
using namespace std;
class node
{
public:
    int data; //data for node
    node* left;//pointer for left subtree
    node* right;//pointer for right subtree
    node(int d) :data(d), left(NULL), right(NULL) //constructor
    {

    }

};

bool createTree(node ** root) //creating tree
{

    int d;
    cin >> d;
    if (d == -1)
    {
        return false; //when user inputs -1 return NULL
    }

    (*root) = new node(d);

    if (createTree(&(*root)->left))
        return createTree(&(*root)->right);
    return false;

}

void printTree(node* root)
{
    if (root == NULL)
    {
        return; //when null is encountered return
    }

    cout << root->data << " ";
    printTree(root->left); //printing recursively left subtree
    printTree(root->right);//printing recursively right subtree

}

int main()
{
    node* root;
    createTree(&root);
    printTree(root);
    system("pause");
    return 0;
}

Answer 3

Your program is still waiting for input. I'll try to explain why with a call graph. Suppose you run your program with input 8 3 10 1. This will create a function call tree like this:

                                                     (next input)
                                                    /
                                        (4, input=1)
                                       /            \
                          (3, input=10)              (waiting...)
                         /             \
             (2, input=3)               (waiting...)
START:      /            \
(1, input=8)              (waiting...)
            \
             (waiting...)

Here, every node labeled waiting... is corresponds to a call to createTree, which is always going to ask the user for input via the cin>>d; statement. To finish this tree, you would actually need to input 8 3 10 1 -1 -1 -1 -1 -1, to end every waiting node. Also, notice that this tree is very linear, since you're inserting elements depth-first. You could structure your input like 8 3 -1 -1 10 -1 -1, which would create the following tree:

         null
        /
     (3)
    /   \
   /     null
(8)
   \      null
    \    /
     (10)
         \
          null

So you aren't committed to linear trees. If you want to create a balanced tree, one thing you could do is to first read all your input into a std::vector<int> until the first -1 is read, then use that vector to insert the elements in breadth-first order. Alternatively, you could insert the elements one-by-one using the techniques of a binary search tree.