title: How to update pointers when pushed on to std::stack using iteration?
body: <p>Here is the situation:  </p>
  
  <blockquote>
    <p>Given a pointer to the root of a binary search tree(of integers) <code>root</code> and an
    integer <code>data</code>, perform the <code>rotate</code> function (predefined) on all the
    ancestral nodes of the node containing <code>data</code> using iterative method. For simplicity, assume
    <code>data</code> exists and always occurs on the leaf nodes.</p>
  </blockquote>
  
  <p>The <code>rotate</code> function passes the pointer by reference as follows:  </p>
  
  <pre><code>struct Node
  {
      Node *left;
      int data;
      Node *right;
  };
  
  void rotate(Node* &amp;root); // performs some rotation on the root and reflects the change.
  
  void search(Node* &amp;root, int data)
  {
      stack&lt;Node*&gt; s;
      while(root-&gt;data!=data)
      {
          s.push(root);
          if(data&lt;root-&gt;data)
              root=root-&gt;left;
          else
              root=root-&gt;right;
      }
  
      while(!s.empty())
      {
          rotate(s.top()); // does not reflect changes to root
          s.pop();
      }
  }
  </code></pre>
  
  <p>The iterative version requires the use of a stack. <code>std::stack::push()</code> function pushes the pointer by value. As a result, while popping the ancestral pointers, I would be reflecting changes in the stack instead.</p>
  
  <p><strong>What is the best work around for this situation?</strong></p>