What is a Binary Search
tree?
Concept
• A binary search tree follows some order to arrange the
elements.
• In a Binary search tree, the value of left node must be
smaller than the parent node, and the value of right
node must be greater than the parent node.
• This rule is applied recursively to the left and right
subtrees of the root.
Why do we need a Binary Search Tree?
• The two major factors that make binary search tree an optimum solution to any real-world
problems are Speed and Accuracy.
• Due to the fact that the binary search is in a branch-like format with parent-child relations, the
algorithm knows in which location of the tree the elements need to be searched.
• This decreases the number of key-value comparisons the program has to make to locate the
desired element.
• Additionally, in case the element to be searched greater or less than the parent node, the node
knows which tree side to search for.
• The reason is, the left sub-tree is always lesser than the parent node, and the right sub-tree has
values always equal to or greater than the parent node.
• BST is commonly utilized to implement complex searches, robust game logics, auto-complete
activities, and graphics.
• The algorithm efficiently supports operations like search, insert, and delete.
How Binary Search Tree Works?
• The tree always has a root node and further child nodes, whether on
the left or right.
• The algorithm performs all the operations by comparing values with
the root and its further child nodes in the left or right sub-tree
accordingly.
Operations on Binary Tree
• Search: searches the element from the binary tree
• Insert: adds an element to the binary tree
• Delete: delete the element from a binary tree
Search Operation
Always initiate analyzing tree at the root node and then move
further to either the right or left subtree of the root node
depending upon the element to be located is either less or
greater than the root.
[Link] element to be searched is 10
[Link] the element with the root node 12, 10 < 12,
hence you move to the left subtree. No need to
analyze the right-subtree
[Link] compare 10 with node 7, 10 > 7, so move to the
right-subtree
[Link] compare 10 with the next node, which is 9, 10 >
9, look in the right subtree child
5.10 matches with the value in the node, 10 = 10,
return the value to the user.
Pseudo Code for Searching in BST
search(element, root)
if !root return -1
if [Link] == element return 1
if [Link] < element
search(element, [Link])
else search(element, [Link])
Insert Operation
• First, the root node is inserted, then the next value is compared with the root node.
• If the value is greater than root, it is added to the right subtree, and if it is lesser than the root, it is added to
the left subtree.
[Link] is a list of 6 elements that need to be inserted in a BST
in order from left to right
[Link] 12 as the root node and compare next values 7 and 9
for inserting accordingly into the right and left subtree
[Link] the remaining values 19, 5, and 10 with the root node 12
and place them accordingly. 19 > 12 place it as the right child of
12, 5 < 12 & 5 < 7, hence place it as left child of 7.
Now compare 10, 10 is < 12 & 10 is > 7 & 10 is > 9,
place 10 as right subtree of 9.
Pseudocode for Inserting a Node in BST
insert (element, root)
Node x = root Node
y = NULL
while x:
y=x
if [Link] < element
x = [Link]
else x = [Link]
if [Link] < element
[Link] = element
else [Link] = element
Delete Operations
• For deleting a node from a BST, there are some cases, i.e. deleting a root or deleting a leaf
node.
• we want to delete a leaf node, we can just delete it, but if we want to delete a root, we need to
replace the root’s value with another node.
• Case 1- Node with zero children: this is the easiest situation, you just need to delete the node
which has no further children on the right or left.
• Case 2 – Node with one child: once you delete the node, simply connect its child node with the
parent node of the deleted value.
• Case 3 Node with two children: this is the most difficult situation, and it works on the following
two rules
• 3a – In Order Predecessor: you need to delete the node with two children and replace it with
the largest value on the left-subtree of the deleted node
• 3b – In Order Successor: you need to delete the node with two children and replace it with the
largest value on the right-subtree of the deleted node
[Link] is the first case of deletion in which you delete a node
that has no children. As you can see in the diagram that 19, 10
and 5 have no children. But we will delete 19.
[Link] the value 19 and remove the link from the node.
[Link] the new structure of the BST without 19
[Link] is the second case of deletion in which you delete a
node that has 1 child, as you can see in the diagram that 9 has
one child.
[Link] the node 9 and replace it with its child 10 and add a
link from 7 to 10
[Link] the new structure of the BST without 9
[Link] you will be deleting the node 12 that has two children
[Link] deletion of the node will occur based upon the in order
predecessor rule, which means that the largest element on
the left subtree of 12 will replace it.
[Link] the node 12 and replace it with 10 as it is the largest
value on the left subtree
[Link] the new structure of the BST after deleting 12
1.1 Delete a node 12 that has two children
2.2 The deletion of the node will occur based upon the In
Order Successor rule, which means that the largest element
on the right subtree of 12 will replace it
3.3 Delete the node 12 and replace it with 19 as it is the largest
value on the right subtree
4.4 View the new structure of the BST after deleting 12
delete (value, root):
Node x = root
Node y = NULL
# searching the node
while x:
y = x
if [Link] < value
x = [Link]
else if [Link] > value
x = [Link]
else if value == x
break
# if the node is not null, then replace it with successor
if [Link] or [Link]:
newNode = GetInOrderSuccessor(y)
[Link] = [Link]
• # After copying the value of successor to the root #we're deleting the successor
• free(newNode)
• else
• free(y)