Fixed it, got a working randomDelete() function that finds the node based on the key portion, then zaps it from within the function, no passing pointers and more pointers. My new deleteRandomSymmetrically, which has to toggle between predecessors and successors with each successive delete, however, doesn't work. I'm dead-tired (it's almost 2 a.m.), so maybe I'm just not seeing the solution now, but do you have any ideas?

Thanks again!

Code:

template<class T>
void BinSearchTree<T>::deleteRandomSymmetrically()
{
if(z == 1)
{
z++;
}
else if(z == 2)
{
z--;
}
int elToDelete = rand()%countEls();
int myInt = 1;//add 1 for node since I incremented with each child access
Queue<BinSearchNode<T>*> queue;
BinSearchNode<T> *p = root;
if(p != 0)
{
queue.enqueue(p);
while(!queue.empty())
{
p = queue.dequeue();
if(p->left != 0)
queue.enqueue(p->left);
myInt++;
if(myInt == elToDelete)
{
if(z == 1)
{
if(p->right != 0)
p = p->right;
while(p != 0 && p->left != 0)
p = p->left;
delete p;
}
else if(z == 2)
{
if(p->left != 0)
p = p->left;
while(p != 0 && p->right != 0)
p = p->right;
delete p;
}
}
if(p->right != 0)
queue.enqueue(p->right);
myInt++;
if(myInt == elToDelete)
{
if(z == 1)
{
if(p->right != 0)
p = p->right;
while(p != 0 && p->left != 0)
p = p->left;
delete p;
}
else if(z == 2)
{
if(p->left != 0)
p = p->left;
while(p != 0 && p->right != 0)
p = p->right;
delete p;
}
}
}
}
}