BST insert

[mx760]

When the current node's L or R pointer is NULL, the new node is returned, BUT where do we assign it to the previous node's L or R pointer? So that's why I'm not sure why the function works...

/**Q: when we insert where new node belongs, how are we linking it to prev node's L or R ptr??*/
bt_node* r_bt_insert_classic(bt_node* node, int data_)//NB: list is a copy of the ACTUAL root ptr declared in main, we don't move it
{
	bt_node* newNode = new bt_node;
	newNode->data = data_;
	newNode->left = NULL;
	newNode->right = NULL;
	
	if ( node == NULL )//base case: if empty list, new node is root node
		return newNode;//return address of new node
	
	else if ( data_ < node->data )//check L subtree
		return r_bt_insert(node->left, data_);
			
	else//Else if data_ >= list->data, so check R subtree
		return r_bt_insert(node->right, data_);
}

As oppose to this which makes sense where the returned new node is linked up BUT this code doesn't work...

bt_node* r_bt_insert_classic(bt_node* node, int data_)//NB: list is a copy of the ACTUAL root ptr declared in main, we don't move it
{
	bt_node* newNode = new bt_node;
	newNode->data = data_;
	newNode->left = NULL;
	newNode->right = NULL;
	
	if ( node == NULL )//base case: if empty list, new node is root node
		return newNode;//return address of new node
	
	else if ( data_ < node->data )//check L subtree
		node->left = r_bt_insert_classic(node->left, data_);// return r_bt_insert(node->left, data_);
			
	else//Else if data_ >= list->data, so check R subtree
		node->right = r_bt_insert_classic(node->right, data_);// return r_bt_insert(node->right, data_);
	return node;
}

[o1vk4iN6]

Well for starters both have a memory leak.

bt_node* newNode = new bt_node; // this should be in if( node == NULL ){ /* ... */ }

If you want to simplify your code than make a constructor for bt_node...

/* ... */

if( node == NULL )
     return new bt_node( data_, NULL, NULL );
/* ... */

Secondly the classic function doesn't work because you are using the "r_bt_insert" function instead of "r_bt_insert_classic".

Thirdly, what happened to your other thread ?

[mx760]

Yes, that was a typo: the recursive calls should be: r_bt_insert_classic, but can you elaborate on what you mean it's a memory leak. Oh, is is b/c the node still exists BUT no one can access it, but if that's the case, then when I outputted the tree (using in-order walk) it output correctly though.

NB: I just noticed I had used r_bt_insert as the recursive calls inside the r_bt_insert_classic function and not just in this post, now it's returning:
"Empty BST" w/ my in-order output.

So in a way I was right that nothing is being "linked up", it was just that I had been using the r_bt_insert_class incorrectly all this time. I didn't even notice that until you pointed it out. So that's probably what you mean by memory leak, new node is made, but no one can access it as we don't keep track. In other words, we don't link it to the newly inserted node.

[o1vk4iN6]

No, it is still a memory leak. Each time that function is called it allocates memory for a bt_node but it is never used, the pointer is lost and thus you never free it. It is allocated even when it is not needed, which is why I suggested another formatting which uses less lines (which it seems, what you wanted to do was make it more readable but in turn created a memory leak). It is not that a single node reference is not set, for example if your binary tree is balanced and has a height of 5, you are going to be creating 7 bt_nodes if you call r_bt_insert_classic(), 6 of which will be memory leaks from traversing the tree.

[mx760]

but still when a base case is reached, meaning time to insert a new node it is returned to previous caller, but there is no linking involved, so there are two ways to "link up":

1) once reach base, we either return to: node->left = r_bt_insert(node->left, data) or node->right = r_bt_insert(node->right);

2) we can check in advance while still pointing to a valid pointer, so from where we are currently, so meaning after we go down L o R subtree and the next node has no L or R subtree, we make the L or R subtree the new node.

e.g.

if ( data < node->data && node->left == NULL )
                node->left = newNode;
                return node;//so return updated L subtree 

I hope that makes sense, the idea of "link up" so updating the L or R subtree which the r_bt_insert_classic doesn't do (even w/o the typo of wrong recursive calls: r_bt_insert which should be: r_bt_insert_classic)