Inserting an element in Binary Tree

Question

Tried exploring a lot over the net, but could get any help, Everywhere its like adding a node to the Binary Search tree.

Question: Requesting for algorithm and code snippet for adding a node to the Binary tree. ( or point me to correct URL )

Assumption: As per my understanding, Binary Tree and Binary Search Tree is different? Correct me if I am wrong.

( request: if you are writing your code snippet please use proper variable name, that helps in understanding )

Eg: Binary Tree

5 7 3 x1 x2 x3

                 5

          7               3

   x1       x2       x3       

Binary Search Tree 5 7 3 2 4 6

                   5
          3               7

   2          4       6       





insert(int key, struct node **root)
{
    if( NULL == *root )`
    {
        *root = (struct node*) malloc( sizeof( struct node ) );`
        (*root)->data = key;
        (*root)->left = NULL;    
        (*root)->right = NULL;  
    }
    else if(key < (*root)->data)
    {
        insert( key, &(*root)->left );
    }
    else if(key > (*root)->data)
    {
        insert( key, &(*root)->right );
    }
}

Solution 1

The difference between a Binary Tree and a Binary Search Tree is that though they both have restrictions that each node can have at most 2 child nodes, a Binary Search Tree (BST) also must have its left child be of equal or lesser value and the its right child must be of greater or equal value. This is why it is called a "Search" tree because everything is ordered numerically and it has an O(logn) run time for searching.

Because there isn't the requirement of being a BST, a Binary Tree can be stored in a vector (array). As you insert into the vector you build the Binary Tree in level-order fashion. The code is below:

// typedef the node struct to NODE
// nodeVector similar to STL's vector class
insert(int key, NODE** nodeVector)
{
    NODE *newNode = (NODE*) malloc( sizeof( NODE ) );
    newNode->data = key;
    newNode->left = NULL;    
    newNode->right = NULL;

    // add newNode to end of vector
    int size = nodeVector->size();
    nodeVector->push_back(newNode);

    // if newNode is not root node
    if(nodeVector->size() > 1)
    {
        // set parent's child values
        Node* parent = (size/2)-1; // take advantage of integer division instead of using floor()
        if (parent->left == NULL)
        {
            parent->left = newNode;
        }
        else
        {
            parent->right = newNode;
        }
    }
}

Solution 2

A Queue data structure can be used for inserting element in to a Binary Tree, since in Binary Tree the order of nodes is not maintained so we will insert the node as soon as we find any null. Using Queue we will be traversing the Binary Tree in Level Order Traversal.

struct Treenode* temp;

Q = CreateQueue();
EnQueue(Q,root);

while(!IsEmptyQueue(Q))
{
    temp = DeQueue(Q);
    if(temp->left)
        EnQueue(Q,temp->left);
    else
    {
        temp->left=newNode;
        DeleteQueue(Q);
        return;
     }
     if(temp->right)
        EnQueue(Q,temp->right);
    else
    {
        temp->right=newNode;
        DeleteQueue(Q);
        return;
     }
}

Comments

[CLearner]

If you are talking about binary search tree and if you are trying to do some instertion, maybe this could help?: en.wikipedia.org/wiki/Binary_search_tree#Insertion

[Abdullah Shoaib]

Wrong binary search tree

[Raa]

@AbdullahShoaib Tell me what will be the right order of BST.

[Raa]

@Cleaner : insertHelper() at the given link also checks for the value < node->key , where as Binary tree should not bother whether the value is less or greater. it should go ahead and place the next node to left if its available or else to right. I hope you understand whats the difference between Binary tree and Binary Search Tree is? according to that do you think its correct.

[wildplasser]

BTW: the example in the question looks like a binary search tree to me.

[Raa]

@wildplasser : yes its a BST , I am looking for the Binary tree.. not getting an algorithm to do the same

[wildplasser]

A binary Search tree is a Binary Tree with an imposed order. A binary tree is just a tree where every node has two child nodes (or fewer), without any restrictions on the order.

[Raa]

@wildplasser : Thanks, but I am not getting how exactly to modify my code to insert the node in a Binary tree

[wildplasser]

It is the same. Just replace your compare (key > (*root)->key) by a random decision. Anything goes...

[Raa]

Thanks for the clarification @bagel. I have updated my BST code for insertion, can you please suggest what changes should i incorporate to make this BST to Binary tree

[sbru]

post the code you are currently using and I'll see what I can do.

[Raa]

just posed it in the question, as i was a bit struggling to get it formatted. please ignore ` character.

[Raa]

what should my left value when I am calling the insert() function from my main ?

[sbru]

it can be either true or false, it doesn't really matter, that bool is just to make it so it is not a linked list.

[sbru]

You are correct, upon coming back to this answer 1.5 years further through my degree I see my mistake :). I'll attempt to fix the issue. Thanks

[sbru]

Ok, I've made some changes, what are your thoughts on it now?

[Ravi]

@bagelboy: I still have issues with your code. I am commenting under your post directly.

[Ravi]

@bagelboy: If we follow your code for insertion of 10,7,8,12,9. This is my output. <br>10</br> / \ 7 8 / \ 12 9 and my tree will keep growing on the right side leaving the left side unoccupied.

[Ravi]

@bagelboy: If we follow your code for insertion of 10,7,8,12,9. This is my output. node 10 (root) - left child 7, right child 8 & for node 7 - No children & for node 8 - left child 12, right child 9 and my tree will keep growing on the right side leaving the left side unoccupied.

[sbru]

@Ravi you are correct. To be fair, a Binary Tree (or BST for that matter) has no requirements on being balanced so technically this isn't incorrect. If that is an additional requirement you want in your BST then take a look at AVL trees. That being said, you are totally in the right having issues with my code because this is almost identical to a linked list. So now, with another 2 years of education under my belt I will attempt to provide a more desirable solution. :)