[FIXED] How to update pointers when pushed on to std::stack using iteration?

Issue

Here is the situation:

Given a pointer to the root of a binary search tree(of integers) root and an integer data, perform the rotate function (predefined) on all the ancestral nodes of the node containing data using iterative method. For simplicity, assume data exists and always occurs on the leaf nodes.

The rotate function passes the pointer by reference as follows:

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

void rotate(Node* &root); // performs some rotation on the root and reflects the change.

void search(Node* &root, int data)
{
    stack<Node*> s;
    while(root->data!=data)
    {
        s.push(root);
        if(data<root->data)
            root=root->left;
        else
            root=root->right;
    }

    while(!s.empty())
    {
        rotate(s.top()); // does not reflect changes to root
        s.pop();
    }
}

The iterative version requires the use of a stack. std::stack::push() function pushes the pointer by value. As a result, while popping the ancestral pointers, I would be reflecting changes in the stack instead.

What is the best work around for this situation?

Solution

This solves my problem.

void search(Node* &root, int data)
{   
    if(root->data==data)
        return;

    stack<Node**> s;
    while(root->data!=data)
    {
        if(data<root->data)
        {
            s.push(&root->left);
            root=root->left;
        }
        else
        {
            s.push(&root->right);
            root=root->right;
        }
    }
    s.pop(); // to avoid leaf
    while(!s.empty())
    {
        rotate(*s.top())
        s.pop();
    }
    rotate(root);
}

Answered By - DoubtExpert

Answer Checked By - Willingham (PHPFixing Volunteer)