Data Structures and Algorithms (Some Questions for You - Answer to Question 6) - Tirthankar Pal - MBA from IIT Kharagpur, GATE, GMAT, IIT Written Test, Interview were a part of MBA Entrance, B.S. in Computer Science from NIELIT

Write an algorithm to insert an element into a binary search tree.

What is Binary Search Tree?

A binary Search Tree is a node-based binary tree data structure which has the following properties:  

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree. 
  There must be no duplicate nodes.

The above properties of Binary Search Tree provides an ordering among keys so that the operations like search, minimum and maximum can be done fast. If there is no ordering, then we may have to compare every key to search for a given key.

How to search a key in given Binary Tree?

For searching a value, if we had a sorted array we could have performed a binary search. Let’s say we want to search a number in the array, in binary search, we first define the complete list as our search space, the number can exist only within the search space. Now we compare the number to be searched or the element to be searched with the middle element (median) of the search space and if the record being searched is less than the middle element, we go searching in the left half, else we go searching in the right half, in case of equality we have found the element. In binary search, we start with ‘n’ elements in search space and if the mid element is not the element that we are looking for, we reduce the search space to ‘n/2’ we keep reducing the search space until we either find the record that we are looking for or we get to only one element in search space and be done with this whole reduction.

Search operations in binary search trees will be very similar. Let’s say we want to search for the number, we start at the root, and then we compare the value to be searched with the value of the root, if it’s equal we are done with the search if it’s smaller we know that we need to go to the left subtree because in a binary search tree all the elements in the left subtree are smaller and all the elements in the right subtree are larger. Searching an element in the binary search tree is basically this traversal, at each step we go either left or right and at each step we discard one of the sub-trees. If the tree is balanced (we call a tree balanced if for all nodes the difference between the heights of left and right subtrees is not greater than one) we start with a search space of ‘n’ nodes and as we discard one of the sub-trees, we discard ‘n/2’ nodes so our search space gets reduced to ‘n/2’. In the next step, we reduce the search space to ‘n/4’ and we repeat until we find the element or our search space is reduced to only one node. The search here is also a binary search hence the name; Binary Search Tree.

Implementation:

• C++
• Java
• Python
• C#
• Javascript

// C function to search a given key in a given BST struct node* search(struct node* root, int key) {     // Base Cases: root is null or key is present at root     if (root == NULL || root->key == key)        return root;          // Key is greater than root's key     if (root->key < key)        return search(root->right, key);       // Key is smaller than root's key     return search(root->left, key); } Insertion of a key : A new key is always inserted at the leaf. We start searching for a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.           100                               100         /   \        Insert 40            /    \       20     500    ———>          20     500       /  \                              /  \       10   30                           10   30                                               \                                                  40 Implementation: C++ C Java Python C# Javascript // C program to demonstrate insert // operation in binary // search tree. #include <stdio.h> #include <stdlib.h>   struct node {     int key;     struct node *left, *right; };   // A utility function to create a new BST node struct node* newNode(int item) {     struct node* temp         = (struct node*)malloc(sizeof(struct node));     temp->key = item;     temp->left = temp->right = NULL;     return temp; }   // A utility function to do inorder traversal of BST void inorder(struct node* root) {     if (root != NULL) {         inorder(root->left);         printf("%d \n", root->key);         inorder(root->right);     } }   /* A utility function to insert    a new node with given key in  * BST */ struct node* insert(struct node* node, int key) {     /* If the tree is empty, return a new node */     if (node == NULL)         return newNode(key);       /* Otherwise, recur down the tree */     if (key < node->key)         node->left = insert(node->left, key);     else if (key > node->key)         node->right = insert(node->right, key);       /* return the (unchanged) node pointer */     return node; }   // Driver Code int main() {     /* Let us create following BST               50            /     \           30      70          /  \    /  \        20   40  60   80 */     struct node* root = NULL;     root = insert(root, 50);     insert(root, 30);     insert(root, 20);     insert(root, 40);     insert(root, 70);     insert(root, 60);     insert(root, 80);       // print inoder traversal of the BST     inorder(root);       return 0; } Output 20 30 40 50 60 70 80 Illustration to insert 2 in below tree:   Start from the root.  Compare the inserting element with root, if less than root, then recursively call left subtree, else recursively call right subtree.  After reaching the end, just insert that node at left(if less than current) or else right.    Time Complexity: The worst-case time complexity of search and insert operations is O(h) where h is the height of the Binary Search Tree. In the worst case, we may have to travel from root to the deepest leaf node. The height of a skewed tree may become n and the time complexity of search and insert operation may become O(n).  Implementation: Insertion using loop. C++ Java Python3 C# // C++ Code to insert node and to print inorder traversal // using iteration #include <bits/stdc++.h> using namespace std;   // BST Node class Node { public:     int val;     Node* left;     Node* right;     Node(int val)         : val(val)         , left(NULL)         , right(NULL)     {     } };   // Utility function to insert node in BST void insert(Node*& root, int key) {     Node* node = new Node(key);     if (!root) {         root = node;         return;     }     Node* prev = NULL;     Node* temp = root;     while (temp) {         if (temp->val > key) {             prev = temp;             temp = temp->left;         }         else if (temp->val < key) {             prev = temp;             temp = temp->right;         }     }     if (prev->val > key)         prev->left = node;     else         prev->right = node; }   // Utiltiy function to print inorder traversal void inorder(Node* root) {     Node* temp = root;     stack<Node*> st;     while (temp != NULL || !st.empty()) {         if (temp != NULL) {             st.push(temp);             temp = temp->left;         }         else {             temp = st.top();             st.pop();             cout << temp->val << " ";             temp = temp->right;         }     } }   // Driver code int main() {     Node* root = NULL;     insert(root, 30);     insert(root, 50);     insert(root, 15);     insert(root, 20);     insert(root, 10);     insert(root, 40);     insert(root, 60);       inorder(root);       return 0; }   // This code is contributed by Tapesh(tapeshdua420) Output 10 15 20 30 40 50 60   Some Interesting Facts:   Inorder traversal of BST always produces sorted output. We can construct a BST with only Preorder or Postorder or Level Order traversal. Note that we can always get inorder traversal by sorting the only given traversal.

 

Tirthankar Pal

MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview
2 year PGDM (E-Business) from Welingkar, Mumbai
4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology
Google and Hubspot Certification
Brain Bench Certification in C++, VC++, Data Structure and Project Management
10 years of Experience in Software Development out of that 6 years 8 months in Wipro
Selected in Six World Class UK Universities:-
King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds