Binary Search Tree - non-recursive destructor help

[pandaEater]

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;
	}
}

[pandaEater]

Nevermind, I think I figured it out. I thought I was stuck but I looked at it again and got something to work.

Here it is: (I don't think there are any bugs)

BST::~BST()
{
	BinNodePtr parent = 0, temp = myRoot;
	while(!empty()){
		if(temp->left){
			parent = temp;
			temp = temp->left;
		}else if(temp->right){
			parent = temp;
			temp = temp->right;
		}else{
			if(parent == 0){
				myRoot = 0;
			}else{
				if(parent->left == temp){
					parent->left = 0;
				}else if(parent->right == temp){
					parent->right = 0;
				}
			}
			cout << temp->data << " "; //Test to show that destructor is working
			delete temp;
			BST::~BST();
		}
	}
}

[Narue]

>BST::~BST();
How is it non-recursive when you try to call the destructor recursively (not a good idea)? Personally, I'm a fan of unraveling the tree into a vine to simplify destruction. Then it just becomes a linked list destruction algorithm:

BST::~BST()
{
    BinNodePtr save;

    for (BinNodePtr it = myRoot; it != NULL; it = save) {
        if (it->left == NULL) {
            save = it->right;
            delete it;
        }
        else {
            // Rotate the left link into a right link
            save = it->left;
            it->left = save->right;
            save->right = it;
        }
    }
}

[pandaEater]

>BST::~BST();
How is it non-recursive when you try to call the destructor recursively (not a good idea)? Personally, I'm a fan of unraveling the tree into a vine to simplify destruction. Then it just becomes a linked list destruction algorithm:

BST::~BST()
{
    BinNodePtr save;

    for (BinNodePtr it = myRoot; it != NULL; it = save) {
        if (it->left == NULL) {
            save = it->right;
            delete it;
        }
        else {
            // Rotate the left link into a right link
            save = it->left;
            it->left = save->right;
            save->right = it;
        }
    }
}

Yeah I realized this morning that I ended up making it recursive even though I was attempting to make it non-recursive so I was going to try to correct that problem today.

Thanks for the help