Binary Trees

[riechan]

Hi guys, sorry I have some questions about Binary Trees. Hope you guys don't mind answering them:

    // If val < ROOT->data, then it goes to the left side of the tree
    if(val < (*tree)->data){
        insert(&(*tree)->left, val);
	// If val > ROOT->data, then it goes to the right side of the tree
    } else if(val > (*tree)->data) {
        insert(&(*tree)->right, val);
    }

Given that my tree is:

       [9]
  [4]        [15]
[2] [6]    [12] [17]

Let's say there were no data in the third level (2,6,12,17) yet. And I'm going to insert 2 and 6 respectively. The rule states that:

If val < ROOT->data, then it goes to the left side of the tree
If val > ROOT->data, then it goes to the right side of the tree

So, as I was saying, I'll insert 2. Will the comparison be:
2 < 4 or 2 < 9?

By ROOT->data, are we referring to the root node of the CURRENT child node? Or the very first node?

[keskiverto]

While your comment says ROOT, the code says (*tree). Who is "tree"?

insert() is apparently a recursive function. It considers only one (current) node. It has basically two options: (1) recurse into existing child, or (2) create a child.

[riechan]

Sorry, here:

struct bin_tree {
	int data;
	struct bin_tree * right, * left;
};
typedef struct bin_tree node;

void insert(node ** tree, int val)
{
    node *temp = NULL;
	
	// Check if tree is empty
    if(!(*tree)){
		
		// Create temp node
        temp = (node *)malloc(sizeof(node));
		
		// Initialize tempROOT's child nodes as NULL
        temp->left = temp->right = NULL;
		
		// Initialize tempROOT's value
        temp->data = val;
		
		// Set tempROOT as *tree
        *tree = temp;
        return;
    }

	// Will call insert function recursively
	// If val < ROOT->data, then it goes to the left side of the tree
    if(val < (*tree)->data){
		// Will proceed to if(!(*tree))
		// When this reaches the leftmost node as NULL, it will insert a new node
        insert(&(*tree)->left, val);
	// If val > ROOT->data, then it goes to the right side of the tree
    } else if(val > (*tree)->data) {
        insert(&(*tree)->right, val);
    }

}

This is just a sample code that I got from the Internet that I was trying to study, as I have yet to learn how binary trees actually work.

[keskiverto]

Language: C.

You main program must refer to the tree somehow. Let say it has node * root.
You already have values {4, 9, 15} in the tree.

1. You call insert( &root, 6 );
The "tree" is not null and 6 < 9.

2. The insert() calls insert( &(*tree)->left, 6 );
The "tree" is not null and 6 > 4.

3. The insert() calls insert( &(*tree)->right, 6 );
Now "tree" is null, so a new node is created.