Binary Tree

[alex067]

Can someone explain to me how this insert function works??

I don't get it, I understand with linked lists, you traverse, and then you ACTUALLY IMPLEMENT IT.

For example:

while (current->next != NULL) or while(current)
current = current->next;

then you actually initiate the insert by going;
current->next = ptr, where PTR is the new node to insert.

So there is direct visual representation of initiation right? current->next points to ptr.


However, can someone explain where the insertion is happening in this recurssive function?

void insert(Tree *& tree, int num)
	{
		if (!tree) // if the list is empty
		{
			tree = new Tree(num); //makes it the root of the tree
			return;
		}

		if (tree->value == num) //base case if node value is num value
		{
			return;
		}

		if (num < tree->value) //if num is less than node value
		{
			insert(tree->left, num); //insert to left pointer
		}
		else
			insert(tree->right, num);
	}

Where is the insertion? It simply says, if the value to insert is greater or less than the node value, traverse left or right. It sends pointer left through the function, and then... where is the insertion?

[Texan40]

The insertion would come when tree->left or tree->right are passed back through the function and become "root" of that iteration.

Edit: It may take several passes for the function to reach a leaf node for this to happen (In a leaf node, tree->left / tree->right are guaranteed to be null)