INTRODUCTION TO TREES

We read the linear data structures like an array, linked list, stack and queue
in which all the elements are arranged in a sequential manner. The
different data structures are used for different kinds of data.

Some factors are considered for choosing the data structure:

 What type of data needs to be stored?: It might be a possibility that a
certain data structure can be the best fit for some kind of data.
 Cost of operations: If we want to minimize the cost for the operations
for the most frequently performed operations. For example, we have a
simple list on which we have to perform the search operation; then, we
can create an array in which elements are stored in sorted order to
perform the binary search. The binary search works very fast for the
simple list as it divides the search space into half.
 Memory usage: Sometimes, we want a data structure that utilizes less
memory.
TREES
A tree is also one of the data structures that represent hierarchical
data. Suppose we want to show the employees and their positions in
the hierarchical form then it can be represented as shown below:
 The above tree shows the organization
hierarchy of some company. In the above
structure, john is the CEO of the company, and John
has two direct reports named as Steve and Rohan.
 Steve has three direct reports named Lee, Bob,
Ella where Steve is a manager. Bob has two direct
reports named Sal and Emma. Emma has two direct
reports named Tom and Raj.
 Tom has one direct report named Bill. This
particular logical structure is known as a Tree.
 Its structure is similar to the real tree, so it is named

a Tree.

 In this structure, the root is at the top, and its

branches are moving in a downward direction.

 Therefore, we can say that the Tree data structure is

an efficient way of storing the data in a hierarchical

way.
LET'S UNDERSTAND SOME KEY POINTS
OF THE TREE DATA STRUCTURE.

 A tree data structure is defined as a collection of

objects or entities known as nodes that are linked

together to represent or simulate hierarchy.

 A tree data structure is a non-linear data structure

because it does not store in a sequential manner.

 It is a hierarchical structure as elements in a Tree

are arranged in multiple levels.

 In the Tree data structure, the topmost node is known as

a root node.

 Each node contains some data, and data can be of any

type.

 In the above tree structure, the node contains the name

of the employee, so the type of data would be a string.

 Each node contains some data and the link or reference

of other nodes that can be called children.

BASIC TERMINOLOGIES USED IN TREE

Let's consider the tree structure, which is

shown below:
In the above structure, each node is labeled with some
number. Each arrow shown in the above figure is known as
a link between the two nodes.
 Root: The root node is the topmost node in the tree
hierarchy.
 In other words, the root node is the one that
doesn't have any parent.
 In the above structure, node numbered 1 is the
root node of the tree.
 If a node is directly linked to some other node,
it would be called a parent-child relationship.
 Child node: If the node is a descendant of any

node, then the node is known as a child node.

 Parent: If the node contains any sub-node, then

that node is said to be the parent of that sub-node.

 Sibling: The nodes that have the same parent are

known as siblings.
 Leaf Node:- The node of the tree, which doesn't
have any child node, is called a leaf node.
 A leaf node is the bottom-most node of the
tree.
 There can be any number of leaf nodes
present in a general tree.
 Leaf nodes can also be called external
nodes.
 Internal nodes: A node has atleast one child
node known as an internal
 Ancestor node:- An ancestor of a node is any
predecessor node on a path from the root to that
node. The root node doesn't have any ancestors. In
the tree shown in the above image, nodes 1, 2, and
5 are the ancestors of node 10.
 Descendant: The immediate successor of the
given node is known as a descendant of a node. In
the above figure, 10 is the descendant of node 5.
 PROPERTIES OF TREE DATA STRUCTURE
 Recursive data structure: The tree is also known as
a recursive data structure.
 A tree can be defined as recursively because the
distinguished node in a tree data structure is known as
a root node.
 The root node of the tree contains a link to all the
roots of its subtrees.
 The left subtree is shown in the yellow color in the
below figure, and the right subtree is shown in the red
color.
 The left subtree can be further split into subtrees
shown in three different colors.
 Recursion means reducing something in a self-similar
manner. So, this recursive property of the tree data
structure is implemented in various applications.
 Number of edges: If there are n nodes, then there
would n-1 edges. Each arrow in the structure
represents the link or path. Each node, except the
root node, will have atleast one incoming link known
as an edge. There would be one link for the parent-
child relationship.
 Depth of node x: The depth of node x can be
defined as the length of the path from the root to the
node x. One edge contributes one-unit length in the
path. So, the depth of node x can also be defined as
the number of edges between the root node and the
node x. The root node has 0 depth.
 Height of node x: The height of node x can be
defined as the longest path from the node x to the
leaf node.
Based on the properties of the Tree data structure, trees are
classified into various categories.
1. Implementation of Tree

The tree data structure can be created by creating the nodes

dynamically with the help of the pointers. The tree in the
memory can be represented as shown below:
 The above figure shows the representation of the tree data structure in the
memory.
 In the above structure, the node contains three fields.
 The second field stores the data; the first field stores the address of the left
child, and the third field stores the address of the right child.

In programming, the structure of a node can be defined as:

struct node
{
int data;
struct node *left;
struct node *right;
}
 The above structure can only be defined for the binary trees because the
binary tree can have utmost two children, and generic trees can have more
than two children.
 The structure of the node for generic trees would be different as compared
to the binary tree.
 APPLICATIONS OF TREES
The following are the applications of trees:
 Storing naturally hierarchical data: Trees are used to store the
data in the hierarchical structure. For example, the file system.
The file system stored on the disc drive, the file and folder are in
the form of the naturally hierarchical data and stored in the form
of trees.
 Organize data: It is used to organize data for efficient insertion,
deletion and searching. For example, a binary tree has a logN
time for searching an element.
 Trie: It is a special kind of tree that is used to store the
dictionary. It is a fast and efficient way for dynamic spell
checking.
 Heap: It is also a tree data structure implemented using arrays.
It is used to implement priority queues.
 B-Tree and B+Tree: B-Tree and B+Tree are the tree data
structures used to implement indexing in databases.
 Routing table: The tree data structure is also used to store the
data in routing tables in the routers.
 TYPES OF TREE
The following are the types of a tree data structure:
 General tree: The general tree is one of the types of tree data structure. In the general
tree, a node can have either 0 or maximum n number of nodes. There is no restriction
imposed on the degree of the node (the number of nodes that a node can contain). The
topmost node in a general tree is known as a root node. The children of the parent node
are known as subtrees.
There can be n number of subtrees in a general tree. In the general tree, the subtrees
are unordered as the nodes in the subtree cannot be ordered.
Every non-empty tree has a downward edge, and these edges are connected to the
nodes known as child nodes. The root node is labeled with level 0. The nodes that
have the same parent are known as siblings.

 Binary tree: Here, binary name itself suggests two numbers, i.e., 0 and 1.
In a binary tree, each node in a tree can have utmost two child nodes. Here, utmost
means whether the node has 0 nodes, 1 node or 2 nodes.
 Binary Search tree: Binary search tree is a non-linear
data structure in which one node is connected to n number of
nodes.
 It is a node-based data structure. A node can be represented
in a binary search tree with three fields, i.e., data part, left-
child, and right-child.
 A node can be connected to the utmost two child nodes in a
binary search tree, so the node contains two pointers (left
child and right child pointer).
 Every node in the left subtree must contain a value less than
the value of the root node, and the value of each node in the
right subtree must be bigger than the value of the root node.
A node can be created with the help of a user-defined data type
known as struct, as shown below:

struct node

int data;

struct node *left;

struct node *right;

The above is the node structure with three fields: data field, the
second field is the left pointer of the node type, and the third
field is the right pointer of the node type.
 AVL tree

 It is one of the types of the binary tree, or we can say

that it is a variant of the binary search tree. AVL tree

satisfies the property of the binary tree as well as of

the binary search tree.

 It is a self-balancing binary search tree that was

invented by Adelson Velsky Lindas. Here, self-

balancing means that balancing the heights of left

subtree and right subtree. This balancing is measured

in terms of the balancing factor.

 We can consider a tree as an AVL tree if the tree
obeys the binary search tree as well as a balancing
factor.
 The balancing factor can be defined as the difference
between the height of the left subtree and the height
of the right subtree.
 The balancing factor's value must be either 0, -1, or
1; therefore, each node in the AVL tree should have
the value of the balancing factor either as 0, -1, or 1.
BINARY TREE
 A binary tree is a tree-type non-linear data structure
with a maximum of two children for each parent.
 Every node in a binary tree has a left and right
reference along with the data element.
 The node at the top of the hierarchy of a tree is called
the root node.
 The nodes that hold other sub-nodes are the parent
nodes.
 A parent node has two child nodes: the left child and
right child.
 Hashing, routing data for network traffic, data
compression, preparing binary heaps, and binary
search trees are some of the applications that use a
binary tree.
TERMINOLOGIES ASSOCIATED WITH BINARY
TREES
 Node: It represents a termination point in a tree.
 Root: A tree’s topmost node.
 Parent: Each node (apart from the root) in a tree that has at
least one sub-node of its own is called a parent node.
 Child: A node that straightway came from a parent node when
moving away from the root is the child node.
 Leaf Node: These are external nodes. They are the nodes that
have no child.
 Internal Node: As the name suggests, these are inner nodes
with at least one child.
 Depth of a Tree: The number of edges from the tree’s node to
the root is.
 Height of a Tree: It is the number of edges from the node to
the deepest leaf. The tree height is also considered the root
height.
 At every level of binary tree, the maximum number
allowed for nodes stands at 2i. (I is level)
 The height of a binary tree stands defined as the longest
path emanating from a root node to the tree’s leaf node.
 Suppose a binary tree placed at a height equal to 3. In
that case, the highest number of nodes for this height 3
stands equal to 15, that is, (1+2+4+8) = 15. In basic
terms, the maximum node number possible for this
height h is (20 + 21 + 22+….2h) = 2h+1 -1.
 Now, for the minimum node number that is possible at
this height h, it comes as equal to h+1.
 If there are a minimum number of nodes, then the height of a
binary tree would stand a maximum.
 On the other hand, when there is a number of a node at its
maximum, then the binary tree m height will be minimum.
 If there exists around ‘n’ number nodes in a binary tree, here is
a calculation to clarify the binary tree definition.
 The tree’s minimum height is computed as:
n = 2h+1 -1
n+1 = 2h+1
Taking log for both sides now,
log2(n+1) = log2(2h+1)
log2(n+1) = h+1
h = log2(n+1) – 1
 The highest height will be computed as:
n = h+1
h= n-1
BINARY TREE COMPONENTS
There are three binary tree components.
Every binary tree node has these three
components associated with it. It becomes an
essential concept for programmers to
understand these three binary tree
components:
1. Data element
2. Pointer to left subtree
3. Pointer to right subtree
 Types of Binary Tree
There are four types of Binary tree:
1. Full/ proper/ strict Binary tree
2. Complete Binary tree
3. Perfect Binary tree
4. Degenerate Binary tree
5. Balanced Binary tree
1. Full/ proper/ strict Binary tree
The full binary tree is also known as a strict binary tree. The
tree can only be considered as the full binary tree if each node
must contain either 0 or 2 children. The full binary tree can
also be defined as the tree in which each node must contain 2
children except the leaf nodes.
Let's look at the simple example of the Full Binary tree.

In the above tree, we can

observe that each node is
either containing zero or two
children; therefore, it is a Full
Binary tree.
Properties of Full Binary Tree
 The number of leaf nodes is equal to the number of internal
nodes plus 1. In the above example, the number of internal
nodes is 5; therefore, the number of leaf nodes is equal to 6.
 The maximum number of nodes is the same as the number of
nodes in the binary tree, i.e., 2h+1 -1.
 The minimum number of nodes in the full binary tree is 2*h-
1.
 The minimum height of the full binary tree is log2(n+1) - 1.
 The maximum height of the full binary tree can be computed
as:
n= 2*h - 1
n+1 = 2*h
h = n+1/2
Complete Binary Tree
The complete binary tree is a tree in which all the nodes are
completely filled except the last level. In the last level, all the
nodes must be as left as possible. In a complete binary tree, the
nodes should be added from the left.
Let's create a complete binary tree.

The above tree is a complete

binary tree because all the
nodes are completely filled,
and all the nodes in the last
level are added at the left first.
Properties of Complete Binary Tree
 The maximum number of nodes in complete
binary tree is 2h+1 - 1.
 The minimum number of nodes in complete
binary tree is 2h.
 The minimum height of a complete binary tree
is log2(n+1) - 1.
 The maximum height of a complete binary tree is
 Perfect Binary Tree
A tree is a perfect binary tree if all the internal nodes
have 2 children, and all the leaf nodes are at the same
level.
Let's look at a simple example of a perfect binary
tree.
The below tree is not a perfect binary tree
because all the leaf nodes are not at the same
level.
 Degenerate Binary Tree
The degenerate binary tree is a tree in which all the
internal nodes have only one children.
Let's understand the Degenerate binary tree through
examples.

The above tree is a degenerate binary tree

because all the nodes have only one child. It is
also known as a right-skewed tree as all the
nodes have a right child only.
The above tree is also a degenerate
binary tree because all the nodes
have only one child. It is also
known as a left-skewed tree as all
the nodes have a left child only.
 Balanced Binary Tree
The balanced binary tree is a tree in which both the left
and right trees differ by atmost 1. For
example, AVL and Red-Black trees are balanced binary
tree.
Let's understand the balanced binary tree through
examples.
The above tree is a
balanced binary tree
because the difference
between the left subtree
and right subtree is zero.
The above tree is not a balanced binary tree because the
difference between the left subtree and the right subtree is
greater than 1.
BENEFITS OF A BINARY TREE
• The search operation in a binary tree
is faster as compared to other trees
• Only two traversals are enough to
provide the elements in sorted order
• It is easy to pick up the maximum
and minimum elements
• Graph traversal also uses binary
trees
• Converting different postfix and
prefix expressions are possible using
binary trees
 Binary Tree Applications
 For easy and quick access to data

 In router algorithms

 To implement heap data structure

 Syntax tree

 In compilers, Expression Trees are used

which is an application of binary tree.

 Huffman coding trees are used in data

compression algorithms.
 Priority Queue is another application of

binary tree that is used for searching

maximum or minimum in O(1) time
complexity.
Basic Operation On Binary Tree:

 Inserting an element.
 Removing an element.
 Searching for an element.
 Traversing an element.
 TREE TRAVERSAL
 Traversal is a process to visit all the nodes of a tree
and may print their values too.
 Because, all nodes are connected via edges (links)
we always start from the root (head) node.
 That is, we cannot randomly access a node in a tree.
 There are three ways which we use to traverse a tree
1. In-order Traversal
2. Pre-order Traversal
3. Post-order Traversal
 Generally, we traverse a tree to search or locate a
given item or key in the tree or to print all the
values it contains.
IN-ORDER TRAVERSAL
 In this traversal method, the left subtree is visited first,
then the root and later the right sub-tree.
 We should always remember that every node may
represent a subtree itself.
 If a binary tree is traversed in-order, the output will
produce sorted key values in an ascending order.
We start from A, and following in-
order traversal, we move to its left
subtree B. B is also traversed in-order.
The process goes on until all the nodes
are visited. The output of inorder
traversal of this tree will be −

D →B→E→A→F→C→G
 ALGORITHM OF INORDER TRAVERSAL
Algorithm: INORD(INFO, LEFT, RIGHT,
4. Repeat Steps 5 to 7 while PTR ≠
ROOT)
A binary tree is in memory. This algorithm NULL: [Backtracking]
does an inorder traversal of T, applying an
5. Apply PROCESS to INFO[PTR]
operation PROCESS to each of its nodes. An
array STACK is used to temporarily hold the 6. [Right Child?] If RIGHT[PTR] ≠
addresses of nodes.
NULL, then :
1. [Push NULL onto STACK and initialize
PTR] Set PTR:= RIGHT[PTR].
Set TOP:=1, STACK[1]:= NULL and
Go to Step 3
PTR:=ROOT.
2. Repeat while PTR ≠ NULL: [End of If structure]
[Pushes left most path onto STACK]
7. Set PTR:= STACK[TOP] and
(a) Set TOP:= TOP+1 and
STACK[TOP]:=PTR [Saves node] TOP:=TOP-1 [Pops Nodes]
(b) Set PTR:= LEFT[PTR]
[End of Step 4 loop]
[update PTR]
[End of loop] 8. Exit
3. Set PTR:= STACK[TOP] and
TOP:=TOP-1 [Pops node from STACK]
 PRE-ORDER TRAVERSAL
In this traversal method, the root node is visited first,
then the left subtree and finally the right subtree.

We start from A, and following

pre-order traversal, we first
visit A itself and then move to
its left subtree B. B is also
traversed pre-order. The
process goes on until all the
nodes are visited. The output
of pre-order traversal of this
tree will be −

A→B→D→E→C→F
→G
 ALGORITHM OF PREORDER TRAVERSAL
Algorithm: PREORD(INFO, LEFT, [Push on STACK]
RIGHT, ROOT) Set TOP:= TOP+1, and
A binary tree is in memory. This STACK[TOP]:=RIGHT[PTR]
algorithm does an preorder traversal of [End of If structure]
T, applying an operation PROCESS to
5. [Left Child?]
each of its nodes. An array STACK is
used to temporarily hold the addresses If LEFT[PTR] ≠ NULL, then :
of nodes. Set PTR:=LEFT[PTR]
1. [Push NULL onto STACK and Else:
initialize PTR] [Pop from stack]
Set TOP:=1, STACK[1]:= Set PTR:= STACK[TOP]
NULL and PTR:=ROOT. and TOP:=TOP-1
2. Repeat Steps 3 to 5 while PTR ≠ [End of If structure]
NULL: [End of Step 2 loop]
3. Apply PROCESS to INFO[PTR] 6. Exit
4. [Right Child?]
If RIGHT[PTR] ≠ NULL, then :
 POST-ORDER TRAVERSAL
In this traversal method, the root node is visited last, hence the name. First
we traverse the left subtree, then the right subtree and finally the root node.

We start from A, and following Post-

order traversal, we first visit the left
subtree B. B is also traversed post-
order. The process goes on until all the
nodes are visited. The output of post-
order traversal of this tree will be −

D→E→B→F→G→C→A
 ALGORITHM OF POSTORDER TRAVERSAL
Algorithm: POSTORD(INFO, [End of If structure]
5 Set PTR:=LEFT[PTR] [Update
LEFT, RIGHT, ROOT) pointer PTR]
A binary tree is in memory. This algorithm
[End of Step 2 loop]
does an postorder traversal of T, applying an
operation PROCESS to each of its nodes. An 6. Set PTR:=STACK[TOP] and TOP:=
array STACK is used to temporarily hold the TOP-1
addresses of nodes. [Pops node from STACK]
1. [Push NULL onto STACK and initialize 7 Repeat while PTR>0:
PTR] (a) Apply PROCESS to INFO[PTR]
Set TOP:=1, STACK[1]:= NULL and (b) Set PTR:= STACK[TOP] and
PTR:=ROOT. TOP=TOP-1
2. [Push left-most path onto STACK] [Pops node from STACK]
Repeat Steps 3 to 5 while PTR ≠ NULL: 8 If PTR<0 then:
3. Set TOP:=TOP+1 and STACK[TOP]:= PTR (a) Set PTR:= -PTR
[Pushes PR on STACK] (b) Go to Step 2
4. If RIGHT[PTR] ≠ NULL, then : [Push [End of If structure]
on STACK]
9. Exit
Set TOP:= TOP+1, and STACK[TOP]:= -
RIGHT[PTR]
 BINARY SEARCH TREE

Binary Search Tree is a node-based binary tree data

structure which has the following properties:
 The left subtree of a node contains only nodes with
keys lesser than the node’s key.
 The right subtree of a node contains only nodes
with keys greater than the node’s key.
 The left and right subtree each must also be a
binary search tree.
 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.
 Let's understand the concept of Binary search tree
with an example.
 In the above figure, we can observe that the root node is 40, and
all the nodes of the left subtree are smaller than the root node,
and all the nodes of the right subtree are greater than the root
node.
 Similarly, we can see the left child of root node is greater than
its left child and smaller than its right child. So, it also satisfies
the property of binary search tree. Therefore, we can say that the
tree in the above image is a binary search tree.
 Suppose if we change the value of node 35 to 55 in the above
tree, check whether the tree will be binary search tree or not.
 In the above tree, the value of root
node is 40, which is greater than its left
child 30 but smaller than right child of
30, i.e., 55.
 So, the above tree does not satisfy the
property of Binary search tree.
 Therefore, the above tree is not a
binary search tree.
ADVANTAGES OF BINARY SEARCH
TREE
 Searching an element in the Binary search tree is
easy as we always have a hint that which subtree
has the desired element.
 As compared to array and linked lists, insertion
and deletion operations are faster in BST.
EXAMPLE OF CREATING A BINARY
SEARCH TREE
 Now, let's see the creation of binary search tree using an example.
 Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50
 First, we have to insert 45 into the tree as the root of the tree.
 Then, read the next element; if it is smaller than the root node,
insert it as the root of the left subtree, and move to the next
element.
 Otherwise, if the element is larger than the root node, then
insert it as the root of the right subtree.
 Now, let's see the process of creating the Binary search tree using
the given data element. The process of creating the BST is shown
below -
 Step 3 - Insert 79.
Step 1 - Insert 45. As 79 is greater than 45, so insert
it as the root node of the right
subtree.

Step 2 - Insert 15.

Step 4 - Insert 90.
As 15 is smaller than 45, 90 is greater than 45 and 79, so
so insert it as the root it will be inserted as the right
node of the left subtree. subtree of 79.
Step 5 - Insert 10. Step 6 - Insert 55.
10 is smaller than 45 and 15, so
it will be inserted as a left 55 is larger than 45 and smaller
subtree of 15. than 79, so it will be inserted as
the left subtree of 79.
Step 7 - Insert 12. Step 8 - Insert 20.
12 is smaller than 45 and 15 but 20 is smaller than 45 but greater than
greater than 10, so it will be 15, so it will be inserted as the right
inserted as the right subtree of subtree of 15.
10.
 Step 9 - Insert 50.
50 is greater than 45 but smaller than 79 and 55. So, it will be
inserted as a left subtree of 55.

 Now, the creation of binary search tree is completed. After that, let's
move towards the operations that can be performed on Binary search
tree.
 We can perform insert, delete and search operations on the binary search
SEARCHING IN BINARY SEARCH
TREE
 Searching means to find or locate a specific element or node in a
data structure. In Binary search tree, searching a node is easy
because elements in BST are stored in a specific order. The steps
of searching a node in Binary Search tree are listed as follows -
1. First, compare the element to be searched with the
root element of the tree.
2. If root is matched with the target element, then
return the node's location.
3. If it is not matched, then check whether the item is
less than the root element, if it is smaller than the
root element, then move to the left subtree.
4. If it is larger than the root element, then move to
the right subtree.
5. Repeat the above procedure recursively until the
match is found.
6. If the element is not found or not present in the
tree, then return NULL.
Now, let's understand the searching in binary tree using an example.
We are taking the binary search tree formed above. Suppose we have
to find node 20 from the below tree.

Step1:
Step2:
Step3:
PROCEDURE FOR SEARCHING
Procedure1: FIND(INFO, LEFT, RIGHT, ROOT, ITEM, LOC,
PAR)
A binary searh tree T is in memory and an item of information is
given. This procedure finds the location LOC of ITEM in T and
also the location PAR of the parent of ITEM. There are three
special cases:
(i) LOC =NULL and PAR=NULL will indicate that the tree is
empty.
(ii) LOC≠ NULL and PAR=NULL will indicate that ITEM is the
root of T.
(iii) LOC=NULL and PAR≠ NULL will indicate that ITEM is not
in T and can be added to T as a child of the node N with
location PAR
1. [Tree empty?]

If ROOT=NULL then: Set LOC:= NULL and

PAR:= NULL and return.
2. [ITEM at root?]
If ITEM = INFO[ROOT] then: Set LOC:= ROOT
and PAR:= NULL and Return
3. [Initialize pointers PTR and SAVE]
If ITEM< INFO[ROOT] then:
Set PTR:= LEFT[ROOT] and SAVE:=ROOT
Else:
Set PTR:= RIGHT[ROOT] and SAVE:= ROOT
[End of If structure]
4. Repeat Steps 5 and 6 while PTR≠ NULL:
5. [ITEM found?]
If ITEM=INFO[PTR] then: Set LOC:= PTR and
PAR:=SAVE and return
6. If ITEM<INFO[PTR] then:
Set SAVE:=PTR and PTR:= LEFT[PTR]
Else:
Set SAVE:= PTR and PTR:= RIGHT[PTR]
[End of If structure]
[End of step 4 loop]
7.[Search unsuccessful] Set LOC:= NULL and PAR:= SAVE
8. Exit
DELETION IN BINARY SEARCH TREE

In a binary search tree, we must delete a node from the

tree by keeping in mind that the property of BST is not
violated. To delete a node from BST, there are three
possible situations occur -
• The node to be deleted is the leaf node, or,
• The node to be deleted has only one child, and,
• The node to be deleted has two children
When the node to be deleted is the leaf
node
 It is the simplest case to delete a node in BST. Here, we
have to replace the leaf node with NULL and simply
free the allocated space.
 We can see the process to delete a leaf node from BST
in the below image.
 In below image, suppose we have to delete node 90, as
the node to be deleted is a leaf node, so it will be
replaced with NULL, and the allocated space will free.
When the node to be deleted has only one child
 In this case, we have to replace the target node with its child,
and then delete the child node.
 It means that after replacing the target node with its child
node, the child node will now contain the value to be deleted.
 So, we simply have to replace the child node with NULL and
free up the allocated space.
 We can see the process of deleting a node with one child
from BST in the below image.
 In the below image, suppose we have to delete the node 79,
as the node to be deleted has only one child, so it will be
replaced with its child 55.
 So, the replaced node 79 will now be a leaf node that can be
easily deleted.
When the node to be deleted has two children
This case of deleting a node in BST is a bit complex among other
two cases. In such a case, the steps to be followed are listed as
follows -

1. First, find the inorder successor of the node to be deleted.

2. After that, replace that node with the inorder successor until
the target node is placed at the leaf of tree.

3. And at last, replace the node with NULL and free up the
allocated space.
 The inorder successor is required when the right child of the
node is not empty. We can obtain the inorder successor by
finding the minimum element in the right child of the node.
We can see the process of deleting a node with two children from BST in the
below image. In the below image, suppose we have to delete node 45 that is the
root node, as the node to be deleted has two children, so it will be replaced
with its inorder successor. Now, node 45 will be at the leaf of the tree so that it
can be deleted easily.
 PROCEDURES & ALGORITHMS OF DELETION IN BST
Procedure2: CASEA (INFO, LEFT, RIGHT,
Else
ROOT, LOC, PAR)
Set CHILD:= RIGHT[LOC]
This procedure deletes the node N at location
LOC where N does not have two children. The [End of If structure]

pointer PAR gives the location of the parent of N 2. If PAR ≠ NULL then:
or else PAR=NULL indicates that N is the root
If LOC = LEFT[PAR], then:
node. The pointer CHILD gives the location of
Set LEFT[PAR]:= CHILD
the only child of N or else CHILD=NULL
Else:
indicates N has no children.
Set RIGHT[PAR] := CHILD
1. [Initializes CHILD]
[End of If structure]
If LEFt[LOC]= NULL and RIGHT[LOC]=
NULL then: 3. Return

Set CHILD:= NULL

Else if LEFT[LOC] ≠ NULL then:

Set CHILD:= LEFT[LOC]

Procedure3: CASEB (INFO, LEFT, (c) Set SUC:= PTR and PARSUC:=
RIGHT, ROOT, LOC, PAR) SAVE
2. [Delete inorder successor using
This procedure deletes the node N at location
Procedure 1]
LOC where N has two children. The pointer Call CASEA(INFO, LEFT, RIGHT,
PAR gives the location of the parent of N or ROOT, SUC, PARSUC)
3. [Replace node N by its inorder
else PAR=NULL indicates that N is the root successor]
node. The pointer SUC gives the location of (a) If PAR ≠ NULL, then:
the inorder successor of N and PARSUC gives If LOC= LEFT[PAR], then:
Set LEFT[PAR]:= SUC
the location of the parent of the inorder
Else:
successor.
Set RIGHT[PAR]:= SUC
1. [Find SUC and PARSUC] [End of If structure]
(a) Set PTR:= RIGHT[LOC] and SAVE:= Else:
LOC Set ROOT:= SUC
(b) Repeat while LEFT[PTR] ≠ NULL: (b) Set LEFT[SUC]:= LEFT[LOC] and
Set SAVE:= PTR and PARSUC:= RIGHT[SUC]:= RIGH[LOC]
SAVE 4. Return
[End of loop]
 ALGORITHM OF BST DELETION
Algorithm: DEL(INFO, LEFT,RIGHT,AVAIL,ITEM)
A binary search tree T is in memory and an ITEM of information is given.
This algorithm deletes ITEM from the tree.
1. [Find the locations of ITEM and its parent using procedure1]
Call FIND (INFO, LEFT, RIGHT,ROOT,ITEM,LOC PAR)
2. [ITEM?]
If LOC= NULL, then: Write item not in tree and exit
3.[Delete node containing ITEM]
If RIGHT[LOC] ≠ NULL and LEFT[LOC] ≠ NULL then
Call CASEB(INFO, LEFT, RIGHT,ROOT,ITEM,LOC PAR)
Else:
Call CASEA(INFO, LEFT, RIGHT,ROOT,ITEM,LOC PAR)
[End of If structure]
4. [Return deleted node to the AVAIL list]
Set LEFT[LOC]:=AVAIL and AVAIL:=LOC
INSERTION IN BINARY SEARCH TREE
 A new key in BST is always inserted at the leaf.
 To insert an element in BST, we have to start searching
from the root node; if the node to be inserted is less than
the root node, then search for an empty location in the left
subtree.
 Else, search for the empty location in the right subtree and
insert the data.
 Insert in BST is similar to searching, as we always have to
maintain the rule that the left subtree is smaller than the
root, and right subtree is larger than the root.
Now, let's see the process of inserting a node into BST using
an example.
 ALGORITHM OF INSERTION IN
BST
Algorithm: INBST(INFO, LEFT, RIGHT,
ROOT, AVAIL, ITEM,LOC) (c) Set LOC:= NEW,

A binary search tree T is in memory and an ITEM LEFT[NEW]:=NULL and

of information is given. This algorithm finds the RIGHT[NEW]:= NULL

location LOC of ITEM in T or adds ITEM as a new 4. [Add ITEM to tree]

node in T at location LOC
If PAR=NULL then:
Call FIND(INFO, LEFT, RIGHT, ROOT, AVAIL,
Set ROOT:= NEW
ITEM,LOC, PAR)
Else if ITEM< INFO[PAR] then:
If LOC≠ NULL then Exit.
Set LEFT[PAR]:= NEW
[Copy ITEM into new in AVAIL list]
Else:
(a) If AVAIL=NULL, then Write: OVERFLOW
and Exit Set RIGHT[PAR]:= NEW

(b) Set New := AVAIL, AVAIL:= [End of If Structure]

LEFT[AVAIL] and 5. Exit

INFO[NEW]:= ITEM
THE COMPLEXITY OF THE BINARY SEARCH TREE
1. Time Complexity:- Where 'n' is the number of nodes in the given tree.

Operations Best case time Average case time Worst case time
complexity complexity complexity
Insertion O(log n) O(log n) O(n)
Deletion O(log n) O(log n) O(n)
Search O(log n) O(log n) O(n)

2. Space Complexity

Operations Space complexity

Insertion O(n)
Deletion O(n)
Search O(n)

•The space complexity of all operations of Binary search tree

is O(n).