Binary Search Tree

1. Search Operation on Binary Search Tree
2. BST Search Algorithm
3. BST Search Illustration
4. Insertion in BST
5. BST Insert Algorithm
6. BST Insert Illustration
7. BST Search & Insert Implementation
8. BST Insert & Search Algorithm Complexity

Binary Search Tree (BST) is an ordered node-based binary tree data structure. The nodes have a value and two child nodes(A binary tree has a maximum of two child nodes) left & right attached to it. Except for the root node, all nodes can be referenced only by their parent. A BST has the following properties:

• All nodes in the left subtree are smaller than the root node.
• All nodes in the right subtree are larger than the root node.
• The left and right subtrees must also be binary search trees.

The tree on the left satisfies all the properties of BST. On the other hand, the tree on the right side seems to be a BST as all nodes in the left subtree are smaller and in the right subtree are larger. But Node 1 on the left subtree dissatisfies BST properties as it is smaller than Node 4 but not greater than root node 3. Hence, it is not a BST.

Since it is an ordered data structure, the elements entered are always organized in a sorted fashion. We can use in-order traversal to retrieve the data stored in BST in sorted order. It gets its name because, just like binary search, it can be used to search the data in O(logn).

Search Operation on Binary Search Tree

We know that in a BST, all elements on the right side of the root are larger, and hence if the target element we are searching for is smaller than the root, the whole right subtree can be neglected. Similarly, if the element is larger than the root then the left subtree can be neglected. We move in a similar fashion until we exhaust the tree or find the target element as the subtree’s root. If the BST is balanced (A tree is called a balanced tree if for all nodes the difference between the height of the left and the right subtree is less than equal to 1.), then the search inside BST performs similar to binary search as both subtrees have around half of the elements which are neglected at every iteration but in case of an unbalanced tree all the nodes may be present on same side and search might perform similar to linear search.

BST Search Algorithm

Let root be the root node of BST and X be the target element being searched.

BST Search Illustration

Suppose we have the above BST, and we want to find the element X = 25.

Insertion in BST

The algorithm to insert an element inside BST is pretty similar to searching an element inside BST because before inserting an element, we have to find its correct position. The only difference in insert and search function is that in case of search, we return the node containing the target value, whereas we create a new node at the node’s appropriate position in case of an insert.

BST Insert Algorithm

Let root be the root node of BST and X be the element we want to insert.

BST Insert Illustration

This is how we insert elements inside a BST.

BST Search & Insert Implementation

#include <iostream>
using namespace std;

class Node {
 public:
  int key;
  Node *left, *right;
};

Node *newNode(int item) {
  Node *temp = (Node *)malloc(sizeof(Node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

void inorder(Node *root) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->key << " ";
    inorder(root->right);
  }
}

Node *insert(Node *root, int key) {
  if (root == NULL) return newNode(key);
  if (key < root->key)
    root->left = insert(root->left, key);
  else
    root->right = insert(root->right, key);

  return root;
}

Node *search(Node *root, int key) {
  if (root == NULL || root->key == key) return root;

  if (root->key < key) return search(root->right, key);

  return search(root->left, key);
}
int main() {
  Node *root = NULL;
  root = insert(root, 5);
  root = insert(root, 3);
  root = insert(root, 8);
  root = insert(root, 6);
  root = insert(root, 4);
  root = insert(root, 2);
  root = insert(root, 1);
  root = insert(root, 7);
  cout << search(root, 5)->key << endl;
}

BST Insert & Search Algorithm Complexity

Time Complexity

• Average Case

On average-case, the time complexity of inserting a node or searching an element in a BST is of the order of height of binary search tree. On average, the height of a BST is O(logn). It occurs when the BST formed is a balanced BST. Hence the time complexity is of the order of [Big Theta]: O(logn).

• Best Case

The best-case occurs when the tree is a balanced BST. The best-case time complexity of insertion and searching is of the order of O(logn). It is the same as average-case time complexity.

• Worst Case

In the worst-case, we might have to traverse from root to the deepest leaf node, i.e., the whole height h of the tree. If the tree is unbalanced, i.e., it is skewed, the tree’s height may become n, and hence the worst-case time complexity of both insert and search operation is O(n).

Space Complexity

The space complexity of both insert and search operation is O(n) due to the space required by recursive calls.