emptying BST

[4ET0pfjN]

Why doesn't root in main point to NULL but some other random address?

void destroy_tree (bt_node* node)
{
   if ( node != NULL )
   {
	destroy_tree( node->left );/**A*/
	destroy_tree( node->right );/**B*/
	cout << "Deleting node: " << node->data;
	cout << endl;
	delete node;
	node = NULL;//I added to be able to rebuild a new tree from this null root ptr BUT root in main NOT NULL, it's pointing to some other address
   }
   else
	return;//implicit return to return to caller A, caller B SO I don't need the ELSE but for clarity
}

int main()
{	
   bt_node* root = NULL;
   root = r_bt_insert(root, 1);//root is a pointer so now it points to the  valid address of the new node w/ data: 1
   root = r_bt_insert(root, 7);//This fcn returns an address
   r_bt_insert(root, 1);
   r_bt_insert(root, 8);

   destroy_tree(root);//=> destroy BST starting from root node
	
   if ( !root )//WHY DOESN'T THIS IF TRUE?
	cout << "Empty BT" << endl;
   else
	cout << "BT not cut down yet!" << endl;
	
   return 0;
}

[vlad from moscow]

Parameter bt_node* node of function

void destroy_tree (bt_node* node);

is a local variable. You set it to NULL but it has nothing common with the argument. After exiting the function this local variable will be destroyed.

Consider for example a simple code

#include <iostream>

void f( int x ) { x = 10; }

int main()
{
   int a = 15;

   f( a );
   std:;cout << "a = " << a << std::end; // a will be equal 15 
}

[4ET0pfjN]

So this destroy function is useless unless I pass by ptrs to ptrs or set it to return type as: bst_node* destroy(...)

and then in main:

//do a bunch of insertions etc

//now empty BST
root = destroy(root);

[vlad from moscow]

Yes. You can either pass the pointer by reference or pass a pointer to the pointer or use a return value.

[4ET0pfjN]

Actually for a similar problem with my insert function, it returns either a newNode if the BST is empty initally so I set root to point to this newNode as:
root = r_bt_insert(root, 1);

BUT then why cannot I constantly make root point to a new node if I reassign root as in:

root = r_bt_insert(root, 23);
root = r_bt_insert(root,99);

so I thought if I try output root's data it would be 99 and it lost track of 23 and 1.

struct bt_node
{
 int data;
 bt_node* left;
 bt_node* right;
};

//recursive BT insert function
bt_node* r_bt_insert(bt_node* list, 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 ( list == NULL )//base case: if empty list, new node is root node
		return newNode;//return address of new node and assign to root node declared in main when root node in main initially is empty (=> set to NULL)
	
	else if ( data_ < list->data )//check L subtree
	{
		if ( list->left == NULL )//check if there exists a node (i.e. check if this subtree is empty, I think this is what author Alex's code avoids), otherwise new node must goes here
		{
			list->left = newNode;
			return list;//NB: we are returning the SAME copy of ACTUAL root node in main so of course it stores same address so we're not returning anything meaningful, just to exit fcn, that's all that's being done here!
		}
		else
			return r_bt_insert(list->left, data_);
	}
			
	else//Else if data_ >= list->data, so check R subtree
	{
		if ( list->right == NULL )
		{
			list->right = newNode;
			return list;
		}
		else
			return r_bt_insert(list->right, data_);
	}
}

int main()
{
 bt_node* root = NULL;
 root = r_bt_insert(root, 1);
 cout << root->data << endl;//Expected: 1

 root = r_bt_insert(root, 23);
 cout << root->data << endl;//Expected: 23

 root = r_bt_insert(root, 99);
 cout << root->data << endl;//Expected: 99
 
 return 0;
}

The reason I ask is when I output:

cout << root << endl;
cout << r_bt_insert(root, 23) << endl;

They have DIFFERENT addresses, so that's why I thought by reassigning root = r_bt_insert(root, 23), it would point to the new node.

Is it b/c it's recursive function, so once I find where to insert a node, I return list, which pops off stack, and then each previous version of list gets popped until the first list pointer is popped, which happens to the a COPY of the ACTUAL root node which gets returned to main, b/c if this is the case then why are the addresses DIFFERENT as I shown above but I'll show again:

root = r_bt_insert(root, 1);
cout << root << endl;//some address
root = r_bt_insert(root, 23);
cout << r_bt_insert(root, 23) << endl;//different address so shouldn't second reassignment of root point to this new address? 

[vlad from moscow]

Let consider the code

 bt_node* root = NULL;
 root = r_bt_insert(root, 1);
 cout << root->data << endl;//Expected: 1

 root = r_bt_insert(root, 23);
 cout << root->data << endl;//Expected: 23

 root = r_bt_insert(root, 99);
 cout << root->data << endl;//Expected: 99 

At first root is equal to NULL. Let look through r_bt_insert

if ( list == NULL )//base case: if empty list, new node is root node
		return newNode;//return address of new node and assign to root node declared in main when root node in main initially is empty (=> set to NULL) 

So after the call root is equal to the new pointer.

Now consider statement root = r_bt_insert(root, 23); In r_bt_insert the following code block is executed

else//Else if data_ >= list->data, so check R subtree
{
	if ( list->right == NULL )
	{
		list->right = newNode;
		return list;
	}

which returns previous value of list.

So what you do is what you get.:)

[4ET0pfjN]

so each previous value of list is returned (popped off stack) until the initial list is returned, which is just copy of the original root pointer from main, right? But if this is the case which makes sense, then why is it that when I output the fcn which returns an address, it is a different address. B/c if the top level list is returned, then it wouldn't matter for as many reassignments I make.

root = r_bt_insert(root, 1);
cout << root << endl;//some address
root = r_bt_insert(root, 23);
cout << r_bt_insert(root, 23) << endl;//different address so shouldn't second reassignment of root point to this new address? 

So in line 4 in the code snippet, it is a DIFFERENT address than in line 2, why? Since initially root points to NULL, so I assign it to the function call, which now makes root point to address of the new node 1, BUT if I reassign root for each new node I insert with the statements: root = r_bt_insert(root, 23) etc then I would expect the same address, the initial address of list, so the COPY of original root's address being returned so the code snippet above SHOULD output the SAME addresses, but there different, that's why I'm lost.

I tinkered around and found out that if I'm inserting and change to: return newNode instead of return list, then the reassignment does indeed update the root pointe in main to point to this new node which renders the initial node unreachable, but still is different addressees outputted doesn't make sense as explained in above paragraph.
And actually just by changing in insert process from return list; to return newNode;, I noticed in main root->data updates to the new node, so I don't have to reassign w/: root = r_bt_insert(root, 23);

I hope I make sense...

[4ET0pfjN]

Finally I figured it out, I was mixing up left->left @ each level of recursive call for finding where new node is to be inserted, so initially when tree is empty and I want to insert the following data: 90, 89, 80.

1) root points to NULL
I return the new address of newNode return newNode BUT I have to reassign root or else root still points to NULL so: root = r_bt_insert(root, 90);

2)Now to insert data 89 (NO recursive call made since root node is ONLY node in tree): If will become what list->left points to and list in function parameter is COPY of actual address of root pointe (from main) so when I return list; of course I'm returning the address of the previous node 90's address. So if I reassig root: root = r_bt_insert(root, 89);,
it's redundant since the SAME previous address of the initial node 90's address is reassigned AGAIN to root pointer.

3)Now to insert data 80: I need to make the FIRST recursive call, so the original pointer passed in function of list becomes list->left which is the NEW/CURRENT value of list which is node 89, so I insert node 80 and then return list; and upon doing so, the list that is returned is this current list (NOT the first pointer list passed from the first call by maiin) that is being returned, in other words, it is address of this variable list being returned back to each caller and that is finally returned to first caller: main. So NOW it does matter if I reassign root or not: so root = r_bt_insert(root, 80); will indeed UPDATE value of root so now we lose track of the first node: node 90. So I don't want to reassign, and just assign root if tree is initially empty (i.e. when root points to NULL).

That is a mouthful, but to get it off my chest to help me better understand. It was the recursion, I forgot about that once we reach base case, that is this value that is being returned back to all its callers. I hope that I'm right...