CODEWITHSUNDEEP
c++pointersbinary-search-tree
Adi
Adi

Reputation: 23

Pointer field not behaving as expected in C++

The following is an example code where I am unable to root cause the error.

#include<iostream>
using namespace std;
struct node
{
    int value;
    node* left;
    node* right;
    node* parent;

    node()
    {
    }

    node(int value)
    {
        this->value = value;
        this->left = NULL;
        this->right = NULL;
        this->parent = NULL;
    }
};



int coun = 0;

void check(node** root)
{
    if(coun == 0)
    {
        coun++;
        check(&((*root)->right));
    }

    else
    {

        node *parentOfCurrent,*childOfCurrent;
        parentOfCurrent = (*root)->parent;
        childOfCurrent = (*root)->right;
        cout << "Value before the statement" << (*root) << "\n";
        parentOfCurrent->right = childOfCurrent;
        cout << "Value after the statement" << (*root) << "\n";
    }
}



int main()
{
    node *node1,*node2,*node3,*node4,**temp,*temp2;
    node1 = new node(1);
    node2 = new node(2);
    node3 = new node(3);
    cout << "Node1 Node2 Node3" << node1 << " " << node2 << " " << node3 << "\n";
    node1->right = node2;
    node2->right = node3;
    node2->parent = node1;
    node3->parent = node3;

    check(&node1);

    //cout << node2->value;
}

In this example I have created a tree as descibed here I am trying here trying to assign node1's right field to node3. The procedure I am following is :

parentOfCurrent->right = childOfCurrent; is executed.

This statement intends to assign the .right field of node1 to node3. What is happening is it value of *root before and after the statement is different. 

Value before the statement: 0x9e17b8
Value after the statement: 0x9e6f30

What is happening is that the pointee of parentOfCurrent->right which is (*root) is being set to childOfCurrent, but I am unable to explain why is this happening?

Upvotes: 0

Views: 97

Answers (1)

molbdnilo
molbdnilo

Reputation: 66371

You have this "tree":

  1 
 /\
x  2
   /\
  x  3

When you enter the recursion, root holds the address of 1's right pointer.

  1 
 /\
x  2  <-- *root (root == &node1->right)
   /\
  x  3

parentOfCurrent->right points to 1's right child (it has the same value as *root).
childOfCurrent points to the 3 node.

After the assignment, root is still the address of 1's right pointer, but 1's right child is now the 3 node:

  1 
 /\
x  3  <-- *root (root == &node1->right)
   /\
  x  x

The double pointer indirection seems unnecessary here.
Try this:

void check(node* root)
{
    if(coun==0)
    {
        coun++;
        check(root->right);
    }
    else
    {   
        node *parentOfCurrent, *childOfCurrent;
        parentOfCurrent = root->parent;
        childOfCurrent = root->right;
        cout<<"Value before the statement"<<root<<"\n";
        parentOfCurrent->right = childOfCurrent;
        cout<<"Value after the statement"<<root<<"\n";
    }
}

int main()
{
    node *node1,*node2,*node3;
    node1 = new node(1);
    node2 = new node(2);
    node3 = new node(3);
    cout<<"Node1 Node2 Node3"<<node1<<" "<<node2<<" "<<node3<<"\n";
    node1->right = node2;
    node2->right = node3;
    node2->parent = node1;
    node3->parent = node2;  // You had a bug here, making node3 its own parent. 
    check(node1);
    cout << node1->right->value; // Prints 3
}

Note that you also want to adjust the parent pointer of a node that you're moving, but I left that out.

Upvotes: 1

Related Questions