Binary Search Tree

Introduction:

         A Binary Search Tree or BST is a binary tree in which left child of every node contain child whose value is smaller than current node and right child will contain child whose value is greater than current node.

Binary Search Tree

Insertion:

        There are many cases which must be consider to run the program without any error.

        Function execute: Reursive function -> Node* push(data,current_node)

        Every function return node or subtree which contain node to be inserted

        We always start from root node

    

    Let us consider an example of inserting 40 in the given tree

    Case 1: When data < current_node->data

            Step 1: Compere 40 with current_node (here root)->data, 40<50

            Step 2: Move to left subtree and insert node recursively by current_node->left = push(data,current_node->left)

                      

    Case 2: When data > current_node->data

            Step 1: Compere 40 with current_node (here root)->data, 40<30

            Step 2: Move to right subtree and insert node recursively by current_node->right = push(data,current_node->right)

    Case 3: When current_node = NULL

            Step 1: Return 40 and as current_node

                                                            

                                                                 Tree after inserting 40

    Note: 

1. We must return current_node after every condition and it will show that we do some manipulation to the sub-tree and then return the manipulated sub-tree to its parent.
2. If the data = current_node->data then simply return without any manipulation b/c in tree no element repeat.