0

I'm trying to make a binary search tree without using recursion anywhere. I'm having trouble with the destructor though. I've been thinking about using a stack to help me keep track of the nodes but I'm not sure exactly how I would implement that.

Any ideas?

Relevant code:

```
class BST
{
public:
BST(); //constructor
//~BST(); //destructor
bool empty();
bool search(const T& item);
void insert(const T& item);
void remove(const T& item);
private:
class BinNode
{
public:
T data;
BinNode* left;
BinNode* right;
BinNode() : left(0), right(0) {}
BinNode(T item): data(item), left(0), right(0) {}
};
typedef BinNode* BinNodePtr;
BinNodePtr myRoot;
};
#endif
```

I'm also thinking about using my remove function in the destructor:

```
void BST::remove(const T &item)
{
bool found = false;
BinNodePtr parent = 0, temp = myRoot;
while(!found && temp){
if(item < temp->data){
parent = temp;
temp = temp->left;
}else if(item > temp->data){
parent = temp;
temp = temp->right;
}else{
found = true;
}
}
if(!found){
cout << "Item not found." << endl;
}else{
if(temp->left && temp->right){
BinNodePtr tempSucc = temp->right;
parent = temp;
while(tempSucc->left){
parent = tempSucc;
tempSucc = tempSucc->left;
}
temp->data = tempSucc->data;
temp = tempSucc;
}
BinNodePtr subtree = temp->left;
if(subtree == 0){
subtree = temp->right;
}if(parent == 0){
myRoot = subtree;
}else if(parent->left == temp){
parent->left = subtree;
}else{
parent->right = subtree;
}
delete temp;
}
}
```