Storing a stack in a recursive function

I am trying to search through a binary search tree and store e开发者_JAVA技巧ach node in a stack as I traverse through the tree in order to remember my path so that I can perform rotations.

Here is my code:

template <typename T>
bool BST<T>::contains(const T& v, BSTNode *&t)
{
   stack<BSTNode*> s;
   BSTNode * g;
   BSTNode * p;

   if( t == NULL )
        return false;
   else if( v < t->element ){
        s.push(t);
        return contains( v, t->leftChild);
   }

   else if( v > t->element ){
        s.push(t);
        return contains( v, t->rightChild);
   }
   else
   { 
   t->search_c += 1;

   if(t->search_c > threshold)  //we need to rotate
   {//begin rotation

   cout << s.size();  //outputs 1


   }//end rotation

   return true;
   }
}

I think that the problem is that the stack (s) goes out of scope each time the function is called, so when it find the value I am looking for it is the only thing stored in the stack. So my question is, how do I make it so that the stack contains each item I traversed through instead of just the last one?

Pass a (non-const) reference to the stack along with the other arguments. You might need a "setup" function to create the stack initially.

What usually happens is that you make a private overload which takes a reference to the stack which is on the original called function's local stack.

template<typename T> class BST {
public:
    bool contains(const T&, BSTNode*&);
private:
    bool contains(const T&, BSTNode*&, stack<BSTNode*>&);
};

It looks like you need to make the stack a member of the class, or extract your contains method and the stack into a new class, calling it from the BST class.