binary search tree confusion

[DonnaPin]

Hello, I am learning data structures from youtube - mycodeschool, and most is really easy to follow apart from this binary search tree. The code from the video is below, and I am really confused about the BstNode * root, that is being used in the main function and in insert.

I thought BstNode* root was being used in the same way head would be in a linked list, that it should always contain the address of the first node. But from what im understanding (which there is a very high chance i am wrong) it looks that what the BstNode* contains is being changed to the most recent insert, and so there is nothing keeping track of the root node. I am really confused at how this is working, if anyone could maybe help clear it up for me, it would be greatly appreciated.

 // Binary Search Tree - Implemenation in C++
// Simple program to create a BST of integers and search an element in it 
#include<iostream>
using namespace std;
//Definition of Node for Binary search tree
struct BstNode {
	int data; 
	BstNode* left;
	BstNode* right;
};

// Function to create a new Node in heap
BstNode* GetNewNode(int data) {
	BstNode* newNode = new BstNode();
	newNode->data = data;
	newNode->left = newNode->right = NULL;
	return newNode;
}

// To insert data in BST, returns address of root node 
BstNode* Insert(BstNode* root,int data) {
	if(root == NULL) { // empty tree
		root = GetNewNode(data);
	}
	// if data to be inserted is lesser, insert in left subtree. 
	else if(data <= root->data) {
		root->left = Insert(root->left,data);
	}
	// else, insert in right subtree. 
	else {
		root->right = Insert(root->right,data);
	}
	return root;
}
//To search an element in BST, returns true if element is found
bool Search(BstNode* root,int data) {
	if(root == NULL) {
		return false;
	}
	else if(root->data == data) {
		return true;
	}
	else if(data <= root->data) {
		return Search(root->left,data);
	}
	else {
		return Search(root->right,data);
	}
}
int main() {
	BstNode* root = NULL;  // Creating an empty tree
	/*Code to test the logic*/
	root = Insert(root,15);	
	root = Insert(root,10);	
	root = Insert(root,20);
	root = Insert(root,25);
	root = Insert(root,8);
	root = Insert(root,12);
	// Ask user to enter a number.  
	int number;
	cout<<"Enter number be searched\n";
	cin>>number;
	//If number is found, print "FOUND"
	if(Search(root,number) == true) cout<<"Found\n";
	else cout<<"Not Found\n";
}

[jonnin]

you are correct, root is like head of a list, and it is not changing anywhere.
where do you think root is modified?

this code uses recursion, which is really handy for working with trees. Do you understand recursion yet?
assuming that is a 'no',
recursion makes use of the operating system/code execution call stack.
that is, there is a 'stack' - like 'container' out there that helps your code run.
it works like this:
foo()
{
bar();
}
main()
foo();

program starts, main is pushed onto the stack.
foo is called and pushed onto the stack.
bar is called by foo, also pushed onto the stack.
bar ends and pops off, and foo resumes from where it was.
foo ends, is popped off the stack, and main resumes from where it was.
main ends, and there is nothing left.

recursion does the same thing, but it looks like
foo is called
foo calls foo, and a second copy is pushed on the stack
foo2 calls foo, and a third copy is pushed...
and when all the popping is done, the original foo's root variable is not changed (see search or insert either one).
inside the chain of foos, (haha..) the parameter is changing, the first time its root, then its root-> left maybe, then root->left->right perhaps, and so on.

all that to say: do yourself a favor and change the word ROOT to anything else when it is a parameter into insert or search. It is not a good name; it confuses you with the root variable in main, which sometimes the parameter IS that value, and sometimes it is NOT.

[DonnaPin]

you are correct, root is like head of a list, and it is not changing anywhere.
where do you think root is modified?

I am actually so confused with this Im beginning to confuse myself even worse, Where I am thinking the root is changing is because in insert i set root = getNewNode() and then root is returned back to the main calling function, so to me, I am taking that to mean that root now has the address of the new node in it. Then since the main function called root = insert(root, n) I am thinking that the returned root (the one I am thinking contains the new node address) is being put into the root ptr in main.

i have touched slightly on recursion, I do need to go over it in a lot more depth. I know the very basic point of it, but thinking it through etc is still very difficult for me. I dont know if thats maybe where my misunderstanding in this is coming from

[jonnin]

the problem is the word root being used in 3 places -- try, as I said, changing the parameters and uses of the word 'root' in the insert and search functions to another name. It will help.

the recursion is confusing, but you must unravel it ... its 2/3 of the code and you need to get what it is doing...

root IS returned from insert, but only changes if root was null to begin with.
otherwise, its basically doing x=x ... yes, its an assignment, no, it didn't change ;)

[seeplus]

Note that in C++ nullptr is used instead of NULL

Also, this would usually be a class - so the user of the class won't need to know about root etc. Although it is important to understand how data structures like these work.

It would be instructive if you used the debugger to trace through the code to see how the recursion operates in practice.

[jonnin]

yea this looks like older code, C++ converted over from C. Maybe on purpose, to keep it simple? OOP gets in the way of the 'tree' part, if you don't have a good handle on it yet.