Binary Search Tree

Jayanta Pal
Dept. of IT
Tripura University

1
Binary Search Tree(BST)

• A binary search tree (BST) is a binary tree that is either empty or in

which every node contains a key (value) and satisfies the following
conditions:
• All keys in the left sub-tree of the root are smaller than the key in the root
node
• All keys in the right sub-tree of the root are greater than the key in the root
node

• The left and right sub-trees of the root are again binary search trees

2
Binary Search Tree(BST)

3
Binary Search Tree(BST)
• A binary search tree is basically a binary tree, and therefore it can be
traversed in inorder, preorder and postorder.

• If we traverse a binary search tree in inorder and print the identifiers

contained in the nodes of the tree, we get a sorted list of identifiers in
ascending order.

Inorder Traversal: 1 3 4 6 7 8 10 13 14

4
Why Binary Search Tree?
• Let us consider a problem of searching a list.

• If a list is ordered, searching becomes faster if we use

contiguous list(array).

• But if we need to make changes in the list, such as inserting new

entries or deleting old entries, (SLOWER!!!!)
because insertion and deletion in a contiguous list requires moving many of the
entries every time.

5
Why Binary Search Tree?
• So we may think of using a linked list because it permits insertion and
deletion to be carried out by adjusting only few pointers.

• But in an n-linked list, there is no way to move through the list other
than one node at a time, permitting only sequential access.

• Binary trees provide an excellent solution to this problem. By making

the entries of an ordered list into the nodes of a binary search tree, we
find that we can search for a key in O(logN)

6
Binary Search Tree(BST)

Time Complexity
Array Linked List BST
Search O(n) O(n) O(logn)
Insert O(1) O(1) O(logn)
Remove O(n) O(n) O(logn)

7
Operations on Binary Search Tree (BST)
• Following operations can be done in BST:

• Search(k, T): Search for key k in the tree T. If k is found in some node of tree
then return true otherwise return false.

• Insert(k, T): Insert a new node with value k in the info field in the tree T such
that the property of BST is maintained.

• Delete(k, T):Delete a node with value k in the info field from the tree T such
that the property of BST is maintained.

• FindMin(T), FindMax(T): Find minimum and maximum element from the

given nonempty BST.

8
Searching Through The BST
• Compare the target value with the element in the root node
 If the target value is equal, the search is successful.
If target value is less, search the left subtree.
If target value is greater, search the right subtree.
If the subtree is empty, the search is unsuccessful.

9
Algorithm to Search a Value in a BST

searchElement (TREE, VAL)

Step 1: IF TREE->DATA = VAL OR TREE = NULL, then
Return TREE
ELSE
IF VAL < TREE->DATA
Return searchElement(TREE->LEFT, VAL)
ELSE
Return searchElement(TREE->RIGHT, VAL)
[END OF IF]
[END OF IF]

Step 2: End

10
11
Insertion of a node in BST
• To insert a new item in a tree, we must first verify that its key is different
from those of existing elements.

• If a new value is less, than the current node's value, go to the left subtree,
else go to the right subtree.

• Following this simple rule, the algorithm reaches a node, which has no left
or right subtree.

• By the moment a place for insertion is found, we can say for sure, that a
new value has no duplicate in the tree.

12
Algorithm for insertion in BST
• Check, whether value in current node and a new value are equal. If so,
duplicate is found. Otherwise,

• if a new value is less, than the node's value:

• if a current node has no left child, place for insertion has been found;
• otherwise, handle the left child with the same algorithm.

• if a new value is greater, than the node's value:

• if a current node has no right child, place for insertion has been found;
• otherwise, handle the right child with the same algorithm.

13
Algorithm to Insert a Value in a BST
Insert (TREE, VAL)

Step 1: IF TREE = NULL, then

Allocate memory for TREE
SET TREE->DATA = VAL
SET TREE->LEFT = TREE ->RIGHT = NULL
ELSE
IF VAL < TREE->DATA
Insert(TREE->LEFT, VAL)
ELSE
Insert(TREE->RIGHT, VAL)
[END OF IF]
[END OF IF]

Step 2: End

14
15
16
Deleting a node from the BST
• While deleting a node from BST, there may be three cases:
1. The node to be deleted may be a leaf node:
• In this case simply delete a node and set null pointer to its parents those side
at which this deleted node exist.

17
Deleting a node from the BST
2. The node to be deleted has one child
• In this case the child of the node to be deleted is appended to its parent node.
Suppose node to be deleted is 18

18
Deleting a node from the BST

19
Predecessor and Successor
In the inorder traversal of a binary tree, the neighbors of
given node are called Predecessor (the node lies behind
of given node) and Successor (the node lies ahead of
given node).

Inorder: 5 10 15 18 19 20 25 35 40 44 45
20
49
Deleting a node from the BST

21
Algorithm to Delete from a BST
Delete (TREE, VAL)

Step 1: IF TREE = NULL, then

Write “VAL not found in the tree”
ELSE IF VAL < TREE->DATA
Delete(TREE->LEFT, VAL)
ELSE IF VAL > TREE->DATA
Delete(TREE->RIGHT, VAL)
ELSE IF TREE->LEFT AND TREE->RIGHT
SET TEMP = findLargestNode(TREE->LEFT)
SET TREE->DATA = TEMP->DATA
Delete(TREE->LEFT, TEMP->DATA)
ELSE
SET TEMP = TREE
IF TREE->LEFT = NULL AND TREE ->RIGHT = NULL
SET TREE = NULL
ELSE IF TREE->LEFT != NULL
SET TREE = TREE->LEFT
ELSE
SET TREE = TREE->RIGHT
[END OF IF]
FREE TEMP
[END OF IF]
22
Step 2: End
23
Determining the Number of Nodes
• To calculate the total number of elements/nodes in a BST, we will
count the number of nodes in the left sub-tree and the right sub-
tree.
• Number of nodes = totalNodes(left sub-tree) + total Nodes(right
sub-tree) + 1
totalNodes (TREE)

Step 1: IF TREE = NULL, then

Return 0
ELSE
Return (totalNodes(TREE->LEFT) +
totalNodes(TREE->RIGHT) + 1)
[END OF IF]
Step 2: End

24
Deleting a BST
• To delete/remove the entire binary search tree from the memory,
we will first delete the elements/nodes in the left sub-tree and
then delete the right sub-tree.

deleteTree (TREE)
Step 1: IF TREE != NULL , then
deleteTree (TREE->LEFT)
deleteTree (TREE->RIGHT)
Free (TREE)
[END OF IF]
Step 2: End

25
Finding the Smallest Node in a BST
• The basic property of a BST states that the smaller value will occur
in the left sub-tree.
• If the left sub-tree is NULL, then the value of root node will be
smallest as compared with nodes in the right sub-tree.
• So, to find the node with the smallest value, we will find the value
of the leftmost node of the left sub-tree.
• However, if the left sub-tree is empty then we will find the value of
the root node.
findSmallestElement (TREE)
Step 1: IF TREE = NULL OR TREE->LEFT = NULL, then
Return TREE
ELSE
Return findSmallestElement(TREE->LEFT)
[END OF IF]
Step 2: End

26