ETCS-209: DATA

STRUCTURE
ODD SEMESTER 2020
Binary Search Tree

Department of Information Technology

Maharaja Agrasen Institute of Technology,
New Delhi
 Outline of BST
 DEFINATION
 PROPERTIES
 ADVANTAGE AND APPLICATIONS
 TRAVERSAL
 OPERATIONS
1) SEARCHING
2) INSERTION
3) DELETION
THREE CASES
1)DELETE LEAF NODE
2)DELETE NODE WITH ONE CHILD
3)DELETE NODE WITH TWO CHILD 2
(1) Start at the root
(2) Search the tree level by level, until you find
the element you are searching for or you reach
a leaf.
Is this better ?

3
 BINARY SEARCH TREES
• Binary search tree is a data structure that quickly allows
us to maintain a sorted list of numbers.

• It is called a binary tree because each tree node has a

maximum of two children.

• It is called a search tree because it can be used to search

for the presence of a number in O(log(n)) time.

4
 BST
The properties that separate a binary search tree from a regular
binary tree is
1)All nodes of left subtree are less than the root node
2)All nodes of right subtree are more than the root node
3)Both subtrees of each node are also BSTs i.e. they have the
above two properties

A tree having a right subtree with one value smaller than the
root is shown to demonstrate that it is not a valid binary 5
BST

6
BST

7
8
 Difference between BT and BST
• A binary tree is simply a tree in which each node can have at most
two children.
• A binary search tree is a binary tree in which the nodes are
assigned values, with the following restrictions :
1)No duplicate values.
2)The left subtree of a node can only have values less than the node
3)The right subtree of a node can only have values greater than the
node and recursively defined
4)The left subtree of a node is a binary search tree.
5)The right subtree of a node is a binary search tree.

9
 BST Operations
Four basic BST operations

10
Preorder Traversal

Root Left Right

11
Postorder Traversal
Left Right Root

12 20 18 35 52 44 23

12
Inorder Traversal

12 18 20 23 35 44 52

13
 BST
Construct a Binary Search Tree (BST) for the following
sequence of numbers-

50, 70, 60, 20, 90, 10, 40, 100

When elements are given in a sequence,

•Always consider the first element as the root node.

•Consider the given elements and insert them in the BST
one by one.

14
 BST
The binary search tree will be constructed as explained
below-
Insert 50-

Insert 70-
As 70 > 50, so insert 70 to the right
of 50.

15
 BST
Insert 60-

As 60 > 50, so insert 60 to the right of 50.

As 60 < 70, so insert 60 to the left of 70.

16
 BST
Insert 20-

As 20 < 50, so insert 20 to the left of 50.

17
 BST
Insert 90-

As 90 > 50, so insert 90 to the right of 50.

As 90 > 70, so insert 90 to the right of 70.

18
 BST
Insert 10-
As 10 < 50, so insert 10 to the left of 50.
As 10 < 20, so insert 10 to the left of 20.

19
 BST
Insert 40-

As 40 < 50, so insert 40 to the left of 50.

As 40 > 20, so insert 40 to the right of 20.

20
 BST
Insert 100-
As 100 > 50, so insert 100 to the right of 50.
As 100 > 70, so insert 100 to the right of 70.
As 100 > 90, so insert 100 to the right of 90.

21
 Question

Problem-01:

A binary search tree is generated by inserting in order of the

following integers-

50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24

22
ANSWER

23
BST OPERATIONS

24
 Search Operation-

Search Operation is performed to search a particular element in the

Binary Search Tree.
Rules-
For searching a given key in the BST,

1) Compare the key with the value of root node.

2) If the key is present at the root node, then return the root node.
3) If the key is greater than the root node value, then recur for the
root node’s right subtree.
4) If the key is smaller than the root node value, then recur for the
root node’s left subtree.

25
 Consider key = 45 has to be searched in the given BST-

We start our search from the root node 25.

As 45 > 25, so we search in 25’s right subtree.
As 45 < 50, so we search in 50’s left subtree.
As 45 > 35, so we search in 35’s right subtree.
As 45 > 44, so we search in 44’s right subtree but 44
has no subtrees.
26
So, we conclude that 45 is not present in the above BST.
if the tree is empty
return NULL

else if the item in the node equals the target return

the node value

else if the item in the node is greater than the target

return the result of searching the left subtree

else if the item in the node is smaller than the target

return the result of searching the right subtree

27
 Search in a BST: C code

ptnode search(ptnode root, int key)

{
/* return a pointer to the node that
contains key. If there is no such
node, return NULL */

if (!root) return NULL;

if (key == root->key) return root;
if (key < root->key)
return search(root->left,key);
return search(root->right,key);
}
28
 Insertion Operation-
Insertion Operation is performed to insert an element in the
Binary Search Tree.

Rules-

1)The insertion of a new key always takes place as the child of

some leaf node.

2)For finding out the suitable leaf node,

•Search the key to be inserted from the root node till some leaf
node is reached.
•Once a leaf node is reached, insert the key as child of that leaf
node.

29
Consider the following example where key = 40
is inserted in the given BST-

We start searching for value 40 from the root node 100.

As 40 < 100, so we search in 100’s left subtree.
As 40 > 20, so we search in 20’s right subtree.
As 40 > 30, so we add 40 to 30’s right subtree.

30
 BST Operations: Insertion

 Case 1: The Tree is Empty

Set the root to a new node containing the item
 Case 2: The Tree is Not Empty
Call a recursive method to insert the item
10
10 > 7
7

5 9 10 > 9

4 6 8 10
 Insertion in BST ‐ Pseudocode

if tree is empty
create a root node with the new key
else
compare key with the top node if key = node key
replace the node with the new value else if key >
node key
compare key with the right subtree:
if subtree is empty create a leaf node else add key
in right subtree
else key < node key
compare key with the left subtree:
if the subtree is empty create a leaf node else add
key to the left subtree
 Insertion in BST – C‐code

struct node* insert(struct node* node, int key)

{
/* If the tree is empty, return a new node */
if (node == NULL){
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp‐>key = item;
temp‐>left = temp‐>right = NULL;
return temp;
}

/* 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;
}
 Deletion Operation-
Deletion Operation is performed to delete a particular element
from the Binary Search Tree.
When it comes to deleting a node from the binary search tree,
following three cases are possible-

Case-01: Deletion Of A Node Having No Child (Leaf Node)

Case-02: Deletion Of A Node Having Only One Child

Case-03: Deletion Of A Node Having Two Children

34
 Case-01:
Deletion Of A Node Having No Child (Leaf Node)-
Just remove / disconnect the leaf node that is to deleted from
the tree.
Example-
Consider the following example where node with value = 20
is deleted from the BST-

35
 Case-02:
Deletion Of A Node Having Only One Child-
Just make the child of the deleting node, the child of its
grandparent.
Example-
Consider the following example where node with value = 30 is
deleted from the BST-

36
 CASE 2 DELETION(ONE CHILD)

copy the value of its child

to the node and delete the
6 is to be deleted
child 37
FINAL TREE AFTER DELETION

38
 Case-03:
Deletion Of A Node Having Two Children-
Method-01:
1)Visit to the right subtree of the deleting node.
2) Pluck the least value element called as inorder successor.
3) Replace the deleting element with its inorder successor.
Consider the following example where node with value = 15
is deleted from the BST-

39
 Case-03:
Deletion Of A Node Having Two Children-
Method-02:
1)Visit to the left subtree of the deleting node.
2)Pluck the greatest value element called as inorder predecessor.
3)Replace the deleting element with its inorder predecessor.
Example-
Consider the following example where node with value = 15 is
deleted from the BST-

40
 DELETION

3 is to be deleted Copy the value of the Remove the inorder

inorder successor (4) successor from its
to the node original position.
41
Algorithm to delete a node in a Binary Search Tree

1)Input the data of the node to be deleted.

2)If the node is a leaf node, delete the node directly.
3)Else if the node has one child, copy the child to the node to be
deleted and delete the child node.
4)Else if the node has two children, find the inorder successor of
the node.
5)Copy the contents of the inorder successor to the node to be
deleted and delete the inorder successor.

42
/* Function to delete the given node */
struct node* delete_node(struct node* root, int data)
{
if (root == NULL)
return root;
// If the key to be deleted is smaller than the root's key,
if (data < root->data)
root->left = delete_node(root->left, data);
// If the key to be deleted is greater than the root's key,
else if (data > root->data)
root->right = delete_node(root->right, data);

43
44
 Time Complexity-

Time complexity of all BST Operations = O(h).

Here, h = Height of binary search tree
Worst Case-
The binary search tree is a skewed binary search tree.
Height of the binary search tree becomes n.
So, Time complexity of BST Operations = O(n).
In this case, binary search tree is as good as unordered list with
no benefits.

45
 Best case

The binary search tree is a balanced binary search tree.

Height of the binary search tree becomes log(n).
So, Time complexity of BST Operations = O(logn).

46
Yes, certain orders might produce very unbalanced trees!

47
Unbalanced trees are not desirable because search time
increases!

Advanced tree structures, such as AVL, red-black trees

guarantee balanced trees.

48
Types of BST

49
 Applications
Binary Search Tree Applications

1)In multilevel indexing in the database

2)For dynamic sorting
3)For managing virtual memory areas in Unix kernel

50
 Applications

• Used in many search applications where data is

constantly entering/leaving, such as the map and set objects
in many languages' libraries.
• Storing a set of names, and being able to lookup based on a
prefix of the name. (Used in internet routers.)
• Storing a path in a graph, and being able to reverse any
subsection of the path in O(log n) time. (Useful in
travelling salesman problems).
• Finding square root of given number
• allows you to do range searches efficiently.

51