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 );
    }
}

Answer 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;
        }
    }
}