Elementary Operations on Binary Search Trees : Insertion

Insertion

In a binary search tree, all elements in the right subtree of a node are greater than the node and all elements in the left subtree of the node are less than the node. Accordingly, if the element to be inserted is greater than the node, it is inserted in its right subtree, and if it is less than the node, insertion is done in the left subtree. For example, in the tree shown below, for insertion of 5 :

1.  5 < 10; so 5 will be in the left subtree of 10.
2. 5 < 6; so 5 will be in the left subtree of 6.
3. 5 > 4; so 5 will be in the right subtree of 4.
4. Since the right subtree of 4 is empty, 5 will be inserted there, i.e., as a right child of 4.

Insertion in a Binary Search Tree

// *****INSERTION AT LEAF NODES***** node * insert(node *ptr,int val) { if(ptr == NULL) return create(val); //a helper function to create the node if(val < (ptr -> data)) ptr -> left = insert(ptr -> left,val); else if(val > (ptr -> data)) ptr -> right = insert(ptr -> right,val); return ptr; } // -----INSERTION AT LEAF NODES ENDS-----


The helper function create(val) used in the above code creates a new node with 'val' as the node value, and NULL left and right children. Here's the create(int) function :

// *****CREATING A NODE***** node * create(int val) { node *t = (node *)malloc(sizeof(node)); t->data = val; t->left = NULL; t->right = NULL; return t; } // -----NODE CREATION ENDS-----



Related links :

Introduction to trees

Binary Search Trees : Traversal

Add Comment

algorithm, c, data structure, programming, trees

Monday, 24 November 2014

Share

Like

G+

Tweet

Tweet

Related Posts