Binary search tree & insertion operation

Ø  Binary search tree – a binary search tree is also known as an ordered binary tree, is a variant of binary tree in which the nodes are arranged in an order. binary search tree is node based binary tree data structure which has the following properties -

The left sub tree of a node contains less value (smaller value) than root node.

The right sub tree of a node contains greater values than root node.

Tree node –

Struct node

{

            Int data;

            Struct node *left child;

            Struct node *right child;

};

Operations of binary search tree –

1.      Insertion – insertion means to add a new element in a tree.

Algorithm –

            If root==NULL

                        Create root node

                        Return

            If root not exist then

            If data>node

                        Go to right sub tree

            Else

Go to left sub tree

                        End if

Insert data

                        End if

                                                OR

·         Step 1: Create a new_node with given value and set its left and right to NULL.

·         Step 2: Check whether tree is Empty.

·         Step 3: If the tree is Empty, then set set rootto newNode.

·         Step 4: If the tree is Not Empty, then check whether value of new_node is smaller or larger than the node (here it is root node).

·         Step 5: If new_node is smaller than or equal to the node, then move to its left child. If new_node is larger than the node, then move to its right child.

·         Step 6: Repeat the above step until we reach to a leaf node (i.e., reach to NULL).

·         Step 7: After reaching a leaf node, then insert the new_node as left child if new_node is smaller or equal to that leaf else insert it as right child.