Traversal pointer in tree while insertion

Question

#include<iostream>

using namespace std;

struct node
{
    int data;
    node *right;
    node *left;
} ;

node *root = NULL;
node *right = NULL;
node *left = NULL;

node insert(int data)
{
    node *ptr = new node;
    ptr->data = data;
    ptr->left = NULL;
    ptr->right = NULL;

    if(root==NULL)
    {
        root = ptr;
        cout<<"Inserted "<<root->data<<" at root\n";
    }
    else
    {
        node *pos = root;
        while(pos)
        {
            cout<<pos->data<<" pos->data\n";
            if(pos->data > data)
            {
                cout<<pos->data<<": data\n";
                pos = pos->left;
            }
            else if(pos->data < data)
            {
                cout<<pos->data<<": data\n";
                pos = pos->right;
            }
            if(!pos)
                cout<<"NULL\n";
        }
        pos = ptr;
        cout<<"Inserted\n";
    }
    return *root;
}

void preorder(node *root)
{
    if(root)
    {
        cout<<root->data;
        preorder(root->left);
        preorder(root->right);
    }
}

int main()
{
    insert(2);
    insert(1);
    insert(3);
    insert(4);
    insert(5);
    preorder(root);
    return 0;
}

Here, while inserting the new element, I am pointing root to new variable pos so that root is unaltered so that it becomes parameter to the function preorder() properly as it is the actual root

But, pos isn't inserting all the elements and also not displaying the required results. In short I have to use root instead of pos to insert, but using root directly is altering the 'actual' root (which in this case is 2).

Don't put the C and C++ tag on the same question, if you want help with your C++ program. — hellow
– hellow, Commented Nov 5, 2018 at 9:29
Don't use global variables, they are very error prone and it is almost always better to use scoped variables. — hellow
– hellow, Commented Nov 5, 2018 at 9:31
just the variable pos isn't giving required result.It is not traversing the nodes. It just keep displaying the root again and again. replacing pos with root is giving the solution but the root pointer is changed. — Mann
– Mann, Commented Nov 5, 2018 at 9:34

Hiroki · Accepted Answer · 2018-11-05 14:49:18Z

1

But, pos isn't inserting all the elements and also not displaying the required results.

I think there are mainly two bugs.

root is never updated in the current insert function because ptr is just only assigned to a temporal variable pos after while loop finished.
We should consider the case that the value of the passed argument data is already saved in the binary tree.

In addition, preorder is displaying the root again and again is confusing. An example of fixing the insert and preorder is following one. DEMO is here.

node insert(int data)
{
    node *ptr = new node;
    ptr->data = data;
    ptr->left = nullptr;
    ptr->right = nullptr;

    if(!root)
    {
        root = ptr;
    }
    else
    {
        node *pos = root;

        while(true)
        {
            if(pos->data > data)
            {
                if(!pos->left){
                    pos->left = ptr;
                    break;
                }

                pos = pos->left;
            }
            else if(pos->data < data)
            {
                if(!pos->right){
                    pos->right = ptr;
                    break;
                }

                pos = pos->right;                
            }
            else{
                break;
            }
        }
    }
    return *root;
}

void preorder(node *next)
{
    if(next)
    {
        cout << next->data << std::endl;
        preorder(next->left);
        preorder(next->right);
    }
}

edited Nov 5, 2018 at 14:49

answered Nov 5, 2018 at 13:42

Hiroki

2,8903 gold badges16 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mann Over a year ago

Yes!! got the logic. Thanks :D

Collectives™ on Stack Overflow

Traversal pointer in tree while insertion

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related