CODEWITHSUNDEEP
c++data-structurestreebinary-tree
Mann
Mann

Reputation: 89

Traversal pointer in tree while insertion

#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).

Upvotes: 2

Views: 90

Answers (1)

Hiroki
Hiroki

Reputation: 2880

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);
    }
}

Upvotes: 1

Related Questions