BST Implementation.. correct?

Kalcor (188)
I couldn't understand something in this BST implementation, first here is the insert function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
BstNode* GetNewNode(int data) {
	BstNode* newNode = new BstNode();
	newNode->data = data;
	newNode->left = newNode->right = NULL;
	return newNode;
}
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;
}


And in main:
1
2
3
4
5
6
7
8
 
BstNode* root = NULL;  // Creating an empty tree
	
	root = Insert(root,15);	
	root = Insert(root,10);	
	root = Insert(root,20);
	root = Insert(root,25);
	root = Insert(root,8);
	root = Insert(root,12);


What I don't understand is.. why are we re-assigning root when any tree can only have 1 root ?
Last edited on
ne555 (10692)
because you didn't bother to encapsulate that behaviour in a tree class.
The first time you assign the newly create node, the rest are self-assignments. You may rewrite it as 
1
2
3
4
 
BstNode *root = NULL;
root = Insert(NULL, 15);
Insert(root, 10);
//...
however, it's too much to ask the developer to note if the tree is or not empty.
So they write the form root = Insert(root, value); which «works in every case». Besides, ¿who doesn't love repetition?


Also, consider that you wrote a `GetNewNode()' function that does what would be expected of a constructor.
Kalcor (188)
Yea you right when I traced the recursion later on I got why both methods work, thanks
Topic archived. No new replies allowed.