Binary Search Trees : Searching, Insertion and Deletion (2024)

Table of Contents
Searching a BST Maximum/Minimum element of a BST Insertion in BST Deletion in BST

Binary Search Tree (or BST) is a special kind of binary tree in which the values of all the nodes of the left subtree of any node of the tree are smaller than the value of the node. Also, the values of all the nodes of the right subtree of any node are greater than the value of the node.

Binary Search Trees : Searching, Insertion and Deletion (1)

In the above picture, the second tree is not a binary search tree because all the values of all the nodes of the left subtree are not smaller than all the nodes of the right subtree.

Binary Search Trees : Searching, Insertion and Deletion (2)

As the name suggests, binary search tree is usually used to perform an optimized search. So, let's look at the searching process of a BST.

Searching a BST

The property that all the values lesser than the value of a node lies on the left subtree and all the values greater than the value of a node lies on the right subtree helps to perform the searching in $O(h)$ time (where h is the height of the tree).

Binary Search Trees : Searching, Insertion and Deletion (3)

Suppose we are on a node and the value to be searched is smaller than the value of the node. In that case, we will search for the value in the left subtree. Otherwise, if the value to be searched is larger, we will just search the right subtree.

Binary Search Trees : Searching, Insertion and Deletion (4)

So, our function will take the element to be searched (x) and the tree (T) i.e., SEARCH(x, T).

We will perform the search operation if the root of the tree is not null - if(T.root != null).

We will first check if the data to be searched is at the root or not. If it is at the root, we will return it.

if(T.root.data == x)
return r

Otherwise, we will search the left subtree if the value to be searched is smaller.

else if(T.root.data > x)
return SEARCH(x, T.root.left)

And if the value to be searched is larger, we will search the right subtree.

else
return SEARCH(x, T.root.right)

SEARCH(x, T) if(T.root != null) if(T.root.data == x) return r else if(T.root.data > x) return SEARCH(x, T.root.left) else return SEARCH(x, T.root.right)

Inorder traversal prints all the data of a binary search tree in a sorted order.

Binary Search Trees : Searching, Insertion and Deletion (5)

To search an element in the tree, we are taking a simple path from the root to leaf. Thus, searching in a binary search tree is done $O(h)$ time.

We also get the maximum and the minimum element of a BST using MAXIMUM and MINIMUM operations. Let's have a look at these.

Maximum/Minimum element of a BST

The smallest element of a binary search tree is the leftmost element of the tree and the largest element is the rightmost one.

Binary Search Trees : Searching, Insertion and Deletion (6)

So, to find the maximum/minimum element, we have to find the rightmost/leftmost element respectively. Thus to find the maximum element, we will go to the right subtree every time until the rightmost element is found i.e., the right child is null.

Binary Search Trees : Searching, Insertion and Deletion (7)

So, we will start by passing a node (n) to our function - MAXIMUM(n).

See Also
Searching In Binary Search Tree In C

Then, we will move to the right subtree every time until the right child is not null.

if(n.right == null)
return n
else
return MAXIMUM(n.right) 

MAXIMUM(T) if(n.right == null) return n else return MAXIMUM(n.right)

Similarly, we can write the MINIMUM function.

MINIMUM(n) if(n.left == null) return n else return MAXIMUM(n.left)

In these two operations also, we are starting from the root and moving to leaf, thus these are also $O(h)$ operations.

We have learned the basic operations to be performed on a binary search tree. Let's learn to insert and delete nodes from a binary search tree so that we can make a binary search tree.

Insertion in BST

We can't insert any new node anywhere in a binary search tree because the tree after the insertion of the new node must follow the binary search tree property.

To insert an element, we first search for that element and if the element is not found, then we insert it.

Binary Search Trees : Searching, Insertion and Deletion (8)

Thus, we will use a temporary pointer and go to the place where the node is going to be inserted.

Binary Search Trees : Searching, Insertion and Deletion (9)

INSERT(T, n)
temp = T.root
while temp != NULL
if n.data < temp.data
temp = temp.left
else
temp = temp.right

Here, we are starting from the root of the tree - temp = T.root and then moving to the left subtree if the data of the node to be inserted is less than the current node - if n.data < temp.data → temp = temp.left.

Otherwise, we are moving right.

We need to make the last node in the above iteration the parent of the new node. So, let's use a variable for this.

Binary Search Trees : Searching, Insertion and Deletion (10)

INSERT(T, n)
temp = T.root
y = NULL
while temp != NULL
y = temp
if n.data < temp.data
temp = temp.left
else
temp = temp.right

We have used a variable y. When the tree won't have any node, the new node will be the root of the tree and its parent will be NULL. So, initially the value of y is NULL. In this case, the loop will also not run.

Otherwise, y will point to the last node.

Binary Search Trees : Searching, Insertion and Deletion (11)

After this, we will make y the parent of the new node.

Binary Search Trees : Searching, Insertion and Deletion (12)

n.parent = y

Lastly, we need to make the new node the child of y. If y is null, the new node will be the root of the tree, otherwise we will check if the data of the new node is larger or smaller than the data of y, and accordingly we will make it either the left or the right child.

Binary Search Trees : Searching, Insertion and Deletion (13)

if y==NULL
T.root = n
else if n.data < y.data
y.left = n
else
y.right = n

INSERT(T, n) temp = T.root y = NULL while temp != NULL y = temp if n.data < temp.data temp = temp.left else temp = temp.right n.parent = y if y==NULL T.root = n else if n.data < y.data y.left = n else y.right = n

Deletion in BST

The last operation we need to do on a binary search tree to make it a full-fledged working data structure is to delete a node.

To delete a node from a BST, we will replace a subtree with another one i.e., we transplant one subtree in place of another.

Binary Search Trees : Searching, Insertion and Deletion (14)

As we are going to use this technique in our delete procedure, so let's first write the code to transplant a subtree rooted at node v in place of the subtree rooted at node u.

Our function to transplant will take the tree T, nodes u and v - TRANSPLANT(T, u, v).

Now, we want to place the subtree rooted at node v in place of the subtree rooted at node u. It means that we need to make v the child of the parent of u i.e., if u is the left child, then v will become the left child of u's parent. Similarly, if u is the right child, then v will become the right child of u's parent.

Binary Search Trees : Searching, Insertion and Deletion (15)

It is also possible that u doesn't have any parent i.e., u is the root of the tree T. In that case, we will simply make v as the root of the tree.

Binary Search Trees : Searching, Insertion and Deletion (16)

So, we will first check if u is root or not i.e., if the parent of u is NULL or not.

if u.parent == NULL //u is root
T.root = v

Now, we will check if u is the left child or the right child. Accordingly, we will place v.

If u is the left child, then the left of u's parent will be u i.e., u == u.parent.left will be true and we will make v as its left child i.e., u.parent.left = v.

Binary Search Trees : Searching, Insertion and Deletion (17)

if u.parent == NULL
...
elseif u == u.parent.left //u is left child
u.parent.left = v
else //u is right child
u.parent.right = v

Lastly, we also need to point the parent of v to the parent of u.

if v != NULL
v.parent = u.parent

So, the overall code would be:

TRANSPLANT(T, u, v) if u.parent == NULL //u is root T.root = v elseif u == u.parent.left //u is left child u.parent.left = v else //u is right child u.parent.right = v if v != NULL v.parent = u.parent

Let's focus on the deletion of a node from a binary search tree.

Suppose the node to be deleted is a leaf, we can easily delete that node by pointing the parent of that node to NULL.

Binary Search Trees : Searching, Insertion and Deletion (18)

We can also say that we are transplanting the right or the left child (both are NULL) to the node to be deleted.

We can also delete a node with only one child by transplanting its child to the node and it will not affect the property of the binary search tree.

Binary Search Trees : Searching, Insertion and Deletion (19)

But things will become a bit little complicated when the node to be deleted has both the children.

Binary Search Trees : Searching, Insertion and Deletion (20)

In this case, we can find the smallest element of the right subtree of the node to be deleted (element with no left child in the right subtree) and replace its content with the node to be deleted.

Binary Search Trees : Searching, Insertion and Deletion (21)

Doing so is not going to affect the property of binary search tree because it is the smallest element of the right subtree, so all the elements in the right subtree are still greater than it. Also, all the elements in the left subtree were smaller than it because it was in the right subtree, so they are still smaller.

The smallest element of the right subtree will have either have no child or one child because if it has left child, then it will not be the smallest element. So, we can delete this node easily as discussed in the first two cases.

Binary Search Trees : Searching, Insertion and Deletion (22)

We have understood the concepts of deleting a node, we can now write the code to do so.

We will start by passing the tree T and the node to be deleted z to the function - DELETE(T, z).

Now, we have to check the number of children of the node z. We will first check if the left child of the node z is NULL or not. If the left child is NULL, then either it has only one child (right one) or none. In both the cases, we can transplant its right child to it.

DELETE(T, z)
if z.left == NULL
TRANSPLANT(T, z, z.right)

Similarly, we will next check if the right child is NULL or not.

DELETE(T, z)
...
elseif z.right == NULL
TRANSPLANT(T, z, z.left)

If none of the above cases are true, the node z has both children and we will find the minimum in the right subtree (y). Now, we have to put this minimum node (y) in the place of z. Firstly, we will transplant the right of y to y and then take the right subtree of z and make it the right subtree of y.

Binary Search Trees : Searching, Insertion and Deletion (23)

After this, we will transplant y to z.

Binary Search Trees : Searching, Insertion and Deletion (24)

However, it can also be possible that the minimum node is the direct child of the node z. In that case, we will just transplant y to z.

Binary Search Trees : Searching, Insertion and Deletion (25)

DELETE(T, z)
...
else
y = MINIMUM(z.right) //minimum element in right subtree
if y.parent != z //z is not direct child
TRANSPLANT(T, y, y.right)
y.right = z.right
y.right.parent = y
TRANSPLANT(T, z, y)

After this, we will change the left child of y to the left child of z.

Binary Search Trees : Searching, Insertion and Deletion (26)

Binary Search Trees : Searching, Insertion and Deletion (27)

DELETE(T, z)
...
else
y = MINIMUM(z.right) //minimum element in right subtree
...TRANSPLANT(T, z, y)
y.left = z.left
y.left.parent = y

DELETE(T, z) if z.left == NULL TRANSPLANT(T, z, z.right) elseif z.right == NULL TRANSPLANT(T, z, z.left) else y = MINIMUM(z.right) //minimum element in right subtree if y.parent != z //z is not direct child TRANSPLANT(T, y, y.right) y.right = z.right y.right.parent = y TRANSPLANT(T, z, y) y.left = z.left y.left.parent = y
  • C
  • Python
  • Java
#include <stdio.h>#include <stdlib.h>typedef struct node {int data;struct node *left;struct node *right;struct node *parent;}node;typedef struct binary_search_tree {node *root;}binary_search_tree;node* new_node(int data) {node *n = malloc(sizeof(node));n->data = data;n->left = NULL;n->right = NULL;n->parent = NULL;return n;}binary_search_tree* new_binary_search_tree() {binary_search_tree *t = malloc(sizeof(binary_search_tree));t->root = NULL;return t;}node* minimum(binary_search_tree *t, node *x) {while(x->left != NULL) x = x->left;return x;}void insert(binary_search_tree *t, node *n) {node *y = NULL;node *temp = t->root;while(temp != NULL) { y = temp; if(n->data < temp->data) temp = temp->left; else temp = temp->right;}n->parent = y;if(y == NULL) //newly added node is root t->root = n;else if(n->data < y->data) y->left = n;else y->right = n;}void transplant(binary_search_tree *t, node *u, node *v) {if(u->parent == NULL) //u is root t->root = v;else if(u == u->parent->left) //u is left child u->parent->left = v;else //u is right child u->parent->right = v;if(v != NULL) v->parent = u->parent;}void delete(binary_search_tree *t, node *z) {if(z->left == NULL) { transplant(t, z, z->right); free(z);}else if(z->right == NULL) { transplant(t, z, z->left); free(z);}else { node *y = minimum(t, z->right); //minimum element in right subtree if(y->parent != z) { transplant(t, y, y->right); y->right = z->right; y->right->parent = y; } transplant(t, z, y); y->left = z->left; y->left->parent = y; free(z);}}void inorder(binary_search_tree *t, node *n) {if(n != NULL) { inorder(t, n->left); printf("%d\n", n->data); inorder(t, n->right);}}int main() {binary_search_tree *t = new_binary_search_tree();node *a, *b, *c, *d, *e, *f, *g, *h, *i, *j, *k, *l, *m;a = new_node(10);b = new_node(20);c = new_node(30);d = new_node(100);e = new_node(90);f = new_node(40);g = new_node(50);h = new_node(60);i = new_node(70);j = new_node(80);k = new_node(150);l = new_node(110);m = new_node(120);insert(t, a);insert(t, b);insert(t, c);insert(t, d);insert(t, e);insert(t, f);insert(t, g);insert(t, h);insert(t, i);insert(t, j);insert(t, k);insert(t, l);insert(t, m);delete(t, a);delete(t, m);inorder(t, t->root);return 0;}
class Node:def __init__(self, data): self.data = data self.right = None self.left = None self.parent = Noneclass BinarySearchTree:def __init__(self): self.root = Nonedef minimum(self, x): while x.left != None: x = x.left return xdef insert(self, n): y = None temp = self.root while temp != None: y = temp if n.data < temp.data: temp = temp.left else: temp = temp.right n.parent = y if y == None: #newly added node is root self.root = n elif n.data < y.data: y.left = n else: y.right = ndef transplant(self, u, v): if u.parent == None: self.root = v elif u == u.parent.left: u.parent.left = v else: u.parent.right = v if v != None: v.parent = u.parentdef delete(self, z): if z.left == None: self.transplant(z, z.right) elif z.right == None: self.transplant(z, z.left) else: y = self.minimum(z.right) #minimum element in right subtree if y.parent != z: self.transplant(y, y.right) y.right = z.right y.right.parent = y self.transplant(z, y) y.left = z.left y.left.parent = ydef inorder(self, n): if n != None: self.inorder(n.left) print(n.data) self.inorder(n.right)if __name__ == '__main__':t = BinarySearchTree()a = Node(10)b = Node(20)c = Node(30)d = Node(100)e = Node(90)f = Node(40)g = Node(50)h = Node(60)i = Node(70)j = Node(80)k = Node(150)l = Node(110)m = Node(120)t.insert(a)t.insert(b)t.insert(c)t.insert(d)t.insert(e)t.insert(f)t.insert(g)t.insert(h)t.insert(i)t.insert(j)t.insert(k)t.insert(l)t.insert(m)t.delete(a)t.delete(m)t.inorder(t.root)
class Node {public int data;public Node left;public Node right;public Node parent;public Node(int data) { this.data = data; this.left = null; this.right = null; this.parent = null;}}class BinarySearchTree {public Node root;public BinarySearchTree() { this.root = null;}public Node minimum(Node x) { while(x.left != null) x = x.left; return x;}public void insert(Node n) { Node y = null; Node temp = this.root; while(temp != null) { y = temp; if(n.data < temp.data) temp = temp.left; else temp = temp.right; } n.parent = y; if(y == null) //newly added node is root this.root = n; else if(n.data < y.data) y.left = n; else y.right = n;}public void transplant(Node u, Node v) { if(u.parent == null) //u is root this.root = v; else if(u == u.parent.left) //u is left child u.parent.left = v; else //u is right child u.parent.right = v; if(v != null) v.parent = u.parent;}public void delete(Node z) { if(z.left == null) { transplant(z, z.right); } else if(z.right == null) { transplant(z, z.left); } else { Node y = minimum(z.right); //minimum element in right subtree if(y.parent != z) { transplant(y, y.right); y.right = z.right; y.right.parent = y; } transplant(z, y); y.left = z.left; y.left.parent = y; }}public void inorder(Node n) { if(n != null) { inorder(n.left); System.out.println(n.data); inorder(n.right); }}public static void main(String[] args) { BinarySearchTree t = new BinarySearchTree(); Node a, b, c, d, e, f, g, h, i, j, k, l, m; a = new Node(10); b = new Node(20); c = new Node(30); d = new Node(100); e = new Node(90); f = new Node(40); g = new Node(50); h = new Node(60); i = new Node(70); j = new Node(80); k = new Node(150); l = new Node(110); m = new Node(120); t.insert(a); t.insert(b); t.insert(c); t.insert(d); t.insert(e); t.insert(f); t.insert(g); t.insert(h); t.insert(i); t.insert(j); t.insert(k); t.insert(l); t.insert(m); t.delete(a); t.delete(m); t.inorder(t.root);}}

In this chapter, we saw that we can insert, search and delete any item in a binary search tree in $O(h)$ time, where h is the height of the tree. But the problem is that for an unbalanced binary tree, $h$ can be pretty large and can go up to $n$, the number of nodes in the tree.

Binary Search Trees : Searching, Insertion and Deletion (28)

In those cases, making a binary search tree won't be of much help rather than using a simple singly linked list. There are some techniques to get a balanced binary search tree after every operation which we are going to study in the next few chapters.

Shall I refuse my dinner because I do not fully understand the process of digestion?

- Oliver Heaviside

Binary Search Trees : Searching, Insertion and Deletion (2024)
Top Articles
Kartoffelpuffer German Potato Pancakes Recipe | Foodal
Sourdough Croissants Recipe - made with sourdough starter
Garage Sales in Wilmington, North Carolina
Wilmington: how a once-red district is a window on North Carolina politics
Latest Posts
Bagel Recipe | New York- Style Bagels Recipe - Sophisticated Gourmet
Best Zesty Italian Dressing Mix (Bulk Recipe)
Article information

Author: Patricia Veum II

Last Updated:

Views: 5752

Rating: 4.3 / 5 (64 voted)

Reviews: 95% of readers found this page helpful

Author information

Name: Patricia Veum II

Birthday: 1994-12-16

Address: 2064 Little Summit, Goldieton, MS 97651-0862

Phone: +6873952696715

Job: Principal Officer

Hobby: Rafting, Cabaret, Candle making, Jigsaw puzzles, Inline skating, Magic, Graffiti

Introduction: My name is Patricia Veum II, I am a vast, combative, smiling, famous, inexpensive, zealous, sparkling person who loves writing and wants to share my knowledge and understanding with you.