I am working on an insert algorithm for a binary tree data structure being implemented in C++. The psuedocode that I am following in a book states that the insert function should have two parameters. One being the address of current node in a BST, and two being the address of the node containing the data to be inserted. (I am doing this recursively). I am not sure what exactly the "address of current node in a BST" is referring to. I am doing this object oriented, and in the driver file, I read data in from a datafile, dynamically allocate memory, place the data inside the allocated memory, and then I am not sure exactly what parameters I need to send to the insert function. I realize I need to send the newly allocated memory (newnode), but like I said before im not sure what the algorithm is referring to when it says "root is address of current node in a BST". Any comments / suggestions are highly appreciated.

I'm not a c++ guy, but generally speaking, A binary tree is a node who has two children, both of which are either binary trees or leaf nodes. So to insert a node into a binary tree, it needs to have a reference to the root of the (sub)tree you want to insert this in. If you always pass it the top-level root for the first parameter, the program will work. You would only give it a node other than the root if you knew something about the subtree the node is at the root of. This would speed up the program, but would yield incorrect results if you made a bad assumption about the subtree. Good luck, -SN

Well, it seem to me like you are using pointers. When dealing with pointers, the pointer name also represents its address, so passing the address is actually means passing the name of the pointer. This pointer could be the root or your newnode. When doing this recursively, you need to pass both the root and the newnode, the function should compare the key of the newnode versus the key of the root, and decide to call itself with (the left child or the right child) and the newnode until it reaches the leaf and then inserts. I hope this helps.

SN: This is how I have my program structured. I have two classes. A node class and a BST class. For simplicity reasons, my node class has all public members. *right, *left, int data, char key. My BST class has a public method to insert, and two private members...root and tree. I made tree so I would have a constant pointer to the first node in the tree. But im not sure where to put it. This is how the program is set up. The driver program reads in a key(char) and data(int) from a data file. Memory is dymanically allocated in the driver file, and everything is placed inside the node. I then invoke the insert function by .insert(.getRoot(), newnode) Now the FIRST time this function call is made, root AND tree should be null. they are initialized to NULL when the BST default constructor is invoked. So the first time its called (it resides in a while not end of file loop), it sends NULL and the address of the newnode into the insert function. An algorithm that im looking at simply says to see if root is NULL for the first test. Now, remember I have a private data member called root, and the formal parameter in this function is called root, which is it referring to? And where would I place tree to point to since I need a constant reference to the first node of the tree, AKA the root, but I feel uncomfortable to use the word root cause it really doesnt convey its meaning. Thanks!

Hi Matt- You're on the right track, and probably closer than you think. A couple of thoughts: 1. You don't need a BST class. I'm assuming that you are putting it in there because of a requirement of the homework, but just be aware that each node could have an insert function, and that way the user (or your driver) only has to retain a pointer to the root node, and call its insert function for each new one. This is what makes BST's cool. You just write the insert function once and call it recursively. Nevertheless, if it's a BST class you want, then dagnabbit you should be able to have one. 2. What are root and tree in the BST class? I think you said that root is always a pointer to the very highest root in the tree, but what is tree? I can't think of anything else you need. 3. the algorithm you're looking at is referring to the parameter root, not the data member root. This way, the insert method can be called recursively. If it was passed the absolute root of the BST every time, you would end up in an infinite loop. 4. If I were to do this assignment, I would do it like this (in pseudocode - I'm not a c++ guy and you seem proficient enough in the language to get my drift) class node {  node left;  node right;  int key;  insert(newnode)  {    if newnode.key >= key    {      if right = null      {        right = newnode;      }      else right.insert(newnode)    }    else    {      if left = null      {        left = newnode;      }      else left.insert(newnode)    }//end else  }//end insert }//end class Then in my driver, I would create the first node manually (as the root of the tree), and insert the rest into it. In this algorithm, the insert method of the root is called, whereas in your algorithm the insert method of the new node is called. I think it's much more simple this way. No extra classes, insert only takes one parameter, and it's just as functional as the other way. Post back with probs. Best of luck, -SN

BTW-disregard my first post...I wasn't thinking recursively. My bad. -SN

SN - So confused I have no idea to even begin to explain it. I will try to explain as clearly as possible and answer your questions. 1. I'm going to use the class, im so used to using classes, its just a sure thing for me. 2. I have two private data members in my BST class, 1 being tree, 2 being root. Now I was planning on using tree as the constant pointer to the first node in the tree. The way my driver is set up, is it reads the data in from the file, places it in the node, and the DRIVER calls the insert algorithm, and sends in the current address of tree, and the dynamically allocated node. So my call looks exactly like this......myTree.insert(myTree.getTree(), newnode); Now, when I instantiate an instance of BST earlier in the program, it invokes the default constructor which does the following...tree = NULL and root = NULL. So when I make that first call to insert, the address of tree is sent in, which equates to NULL, and the first node is sent in. The heading of my insert function looks like this: void BST::insert(nodetype*, nodetype*) You know what, i just confused myself even more, I'm going to stop typing now.