# Thread: Recursion and new operator

1. ## Recursion and new operator

I'm writing a BST class and have a very strange (at least to me) problem. I can't insert a key in tree using recursion. Iteration works fine, but I would really like to know why recursive way doesn't work.
The code I wrote seems to be fine, so if anyone could point me in right direction...

My code is:
Code:
```struct sData
{
long key;
char name[20];
};

struct sTINode
{
sData data;
sTINode* left;
sTINode* right;
};

class cBST :
public cAbsTelefonskiImenik
{
public:
cTelefonskiImenikBST(void);
~cTelefonskiImenikBST(void);
bool insert(long key, char name[20]);
private:
// root
sTINode *root;
void insertLeaf(long key, char name[20], char, sTINode *node);
};

cBST::cTelefonskiImenikBST(void)
{
root=NULL;
}

bool cBST::insert(long key, char name[20]);
{
insertLeaf(key, name, root);
return true;
}

void cTelefonskiImenikBST::insertLeaf(long key, char name[20], sTINode *node)
{
if (node==NULL)
{
node=new sTINode;
node->data.key=key;
strcpy(node->data.name, name);
node->left=NULL;
node->right=NULL;
return;
}
else
{
if (node->data.key>key)
insertLeaf(key, name, node->left);
else if (node->data.key<key)
insertLeaf(key, name, node->right);
}
}```

2. You could allocate and create your node in the insert function and then pass it to the insertLeaf function, rather than allocating it there.

3. ...and your code isn't working because you've got to insert it to the right or left of an existing node, so you should be checking whether node->left==NULL or node->right==NULL, not whether the node itself is NULL (otherwise your new node is never attached and has no parent).

4. Heh, I had to do so much crap just to get this to compile, and so little to actually fix what was wrong with your code. Basically, you have to remember that pointers are passed by value by default. In making the pointers sent by reference to the insertLeaft code, the code worked fine.

Code:
```struct sData
{
long key;
char name[20];
};

struct sTINode
{
sData data;
sTINode* left;
sTINode* right;
};

class cBST
{
public:
cBST(void);
~cBST(void);
bool insert(long key, char* name);
void print();
private:
void print(sTINode *node);
// root
sTINode *root;
void insertLeaf(long key, char* name, sTINode *&node);
void remove(sTINode* node);
};

#include <iostream>

void cBST::print() {
print(root);
}

void cBST::print(sTINode* node) {
if (node != 0 ) {
std::cout << '\t' << node->data.key << ' ' << node->data.name ;
print(node->left);
print(node->right);
}
}

cBST::cBST(void)
{
root=NULL;
}

cBST::~cBST(void)
{
remove(root);
}

void cBST::remove(sTINode* node) {
if (node != 0) {
remove(node->left);
remove(node->right);
delete node;
}
}

bool cBST::insert(long key, char* name)
{
insertLeaf(key, name, root);
return true;
}

void cBST::insertLeaf(long key, char name[20], sTINode *&node)
{
if (node==NULL)
{
node=new sTINode;
node->data.key=key;
strcpy(node->data.name, name);
node->left=NULL;
node->right=NULL;
return;
}
else
{
if (node->data.key>key)
insertLeaf(key, name, node->left);
else if (node->data.key<key)
insertLeaf(key, name, node->right);
}
}

int main() {
cBST tree;
tree.insert(1, "rob");
tree.insert(2, "blah");
tree.insert(3, "dan");
tree.insert(0, "otherthing");
tree.print();
char wait; cin >> wait;
}```

5. Many thanks, SilentStrike.
I though that pointer are always passed by reference (I am Delphi programmer and what little of what I know abot C++ I learned at university)...so I have some reading to do about the subject.

6. The pointers refer to values. However, copies of the actual pointer are sent by default.