**A Binary Search Tree (BST)**is a rooted binary tree, whose nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree should satisfy the BST property, which states that the key in each node must be greater than all keys stored in the left sub-tree, and not greater than all keys in the right sub-tree. Ideally, only unique values should be present in the tree.

Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays (maps, multimaps, etc).

**Insertion:**

When looking for a place to insert a new key, we traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees. In other words, we examine the root and recursively insert the new node to the left subtree if its key is less than that of the root, or the right subtree if its key is greater than or equal to the root.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <bits/stdc++.h> using namespace std; // Data structure to store a Binary Search Tree node struct Node { int data; Node *left, *right; }; // Function to create a new binary tree node having given key Node* newNode(int key) { Node* node = new Node; node->data = key; node->left = node->right = nullptr; return node; } // Function to perform inorder traversal of the tree void inorder(Node* root) { if (root == nullptr) return; inorder(root->left); cout << root->data << " "; inorder(root->right); } // Recursive function to insert an key into BST using a reference parameter void insert(Node* &root, int key) { // if the root is null, create a new node an return it if (root == nullptr) { root = newNode(key); return; } // if given key is less than the root node, recuse for left subtree // else recuse for right subtree if (key < root->data) insert(root->left, key); else // key >= root->data insert(root->right, key); } // main function int main() { Node* root = nullptr; int keys[] = { 15, 10, 20, 8, 12, 16, 25 }; for (int key : keys) insert(root, key); inorder(root); return 0; } |

We can modify the above solution to return the root node from the function instead of passing it by reference.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Recursive function to insert an key into BST Node* insert(Node* root, int key) { // if the root is null, create a new node an return it if (root == nullptr) return newNode(key); // if given key is less than the root node, recuse for left subtree if (key < root->data) root->left = insert(root->left, key); // if given key is more than the root node, recuse for right subtree else root->right = insert(root->right, key); return root; } |

**Iterative Version – **

Another way to explain the insertion is that in order to insert a new node in the tree, its key is first compared with that of the root. If its key is less than the root’s, it is then compared with the key of the root’s left child. If its key is greater, it is compared with the root’s right child. This process continues, until the new node is compared with a leaf node, and then it is added as this node’s right or left child, depending on its key: if the key is less than the leaf’s key, then it is inserted as the leaf’s left child, otherwise as the leaf’s right child.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
// Iterative function to insert an key into BST. // Root is passed by reference to the function void insertIterative(Node*& root, int key) { // start with root node Node *curr = root; // pointer to store parent node of current node Node *parent = nullptr; // if tree is empty, create a new node and set root if (root == nullptr) { root = newNode(key); return; } // traverse the tree and find parent node of key while (curr != nullptr) { // update parent node as current node parent = curr; // if given key is less than the current node, go to left subtree // else go to right subtree if (key < curr->data) curr = curr->left; else curr = curr->right; } // construct a new node and assign to appropriate parent pointer if (key < parent->data) parent->left = newNode(key); else parent->right = newNode(key); } |

The time complexity of above solution is O(h) where h is the height of the BST. The height of the BST in worst case is as much as number of keys in BST. The worst case happens when given keys are sorted in ascending or descending order and we get a skewed tree (all the nodes except leaf have one and only one child).

For a height balanced BSTs, with each comparison we skip about half of the tree, so that each insertion operation takes time proportional to the logarithm of the number of items n stored in the tree i.e. log_{2}n. This is much better than the linear time required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables.

**Exercise:** Modify the solution to construct a height balanced BST.

(Hint – Sort the keys first)

**References:**

https://en.wikipedia.org/wiki/Binary_search_tree

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply