Binary Search Tree Insert

Ok so we are doing Binary Search Trees. I have to do an insert function to add new data into the tree. The code below calls a recursive function to do this. However we are required to do this non recursively.

I have absolutely no idea where to start for this. a little guidance would be greatly appreciated. Thank you :)

Code:

---

void Insert(string data)
{
        if (root != NULL)
        {
                Insert(data, root);
        }
        else
        {
                root = new node;
                root->data = data;
                root->left = NULL;
                root->right = NULL;
        }
}

---

Quote:

---

Originally Posted by bleuz

Ok so we are doing Binary Search Trees. I have to do an insert function to add new data into the tree. The code below calls a recursive function to do this. However we are required to do this non recursively.

I have absolutely no idea where to start for this. a little guidance would be greatly appreciated. Thank you :)

Code:

---

void Insert(string data)
{
        if (root != NULL)
        {
                Insert(data, root);
        }
        else
        {
                root = new node;
                root->data = data;
                root->left = NULL;
                root->right = NULL;
        }
}

---

---

You simply loop through the tree, going down left or right as the data you want to insert dictates, until you find a 0-node. Then you create it and insert the data.

You do it in the same way you append a node to a linked-list, except that you take one of two possible paths from each node. Can you append to a linked-list?

Quote:

---

Originally Posted by iMalc

You do it in the same way you append a node to a linked-list, except that you take one of two possible paths from each node. Can you append to a linked-list?

---

Yes I can. so all im doing is checking whether my data to be inserted is less than or greater than. as i progress down a side?

Yeah that's pretty much it. Make sure that you attach the node to the correct child of it's parent of course.

One thread at a time -> http://cboard.cprogramming.com/cplus...rch-trees.html