Binary Tree Insertion: setting parent

[ahmadsbokhari]

I need to set a parent for each new node being inserted but I can't get to incorporate that into my insert function.

Here's a part of my code:

struct bst_node
{
        string value;
        T key;
        bst_node<T> *left;
        bst_node<T> *right;
        bst_node<T> *parent;
};

template <class T>
void bst<T>::insert(string val, T key1)
{
	bst_node<T> *nova = new bst_node<T>(val, key1);
	bst_node<T> *temp = nodefinder(key1, root);
	if (temp != NULL) {
		temp->value = val;
	} else {
		nodein(val, key1, *&root, NULL);
	}
}

template <class T>
void bst<T>::nodein(string val, T key1, bst_node<T> *&nova) {
	if (nova == NULL) {
		nova = new bst_node<T>(val, key1);
	} else {
		if (key1 < nova->key) {
			nodein(val, key1, nova->left, nova);
		} else {
			nodein(val, key1, nova->right, nova);
		}
	}
}

[Smac89]

Where have you defined nodefinder (line 14), and where have you defined nodein (line 18)?

What does bst class look like??

[ahmadsbokhari]

thankyou so much. I've managed to do it. now I'm wrestling with delete :p i've defined nodefinder and nodein in the cpp file and they work perfectly fine.

template <class T>
class bst
{
	bst_node<T> *root;

	public:

bst_node<T>* parent(bst_node<T> *nova, bst_node<T> *p);
	bst();
	void insert(string val,T key1);
    void nodein(string val, T key1, bst_node<T> *&nova);
    bst_node<T>* nodefinder(T key1, bst_node<T> *nova);
	bst_node<T>* search(T key1);
	void delete_node(T key1);
	int height(bst_node<T>* temp);
    void replace(T old_key,T new_key);
	bst_node<T>* getroot();
};