Data Structures

Trees
 Non-linear data structure

The data in a tree are not stored in a

sequential manner i.e., they are not stored
linearly.
They are arranged on multiple levels or we
can say it is a hierarchical structure.

2
 Definition of Tree

A tree is a finite set of one or more nodes

such that:
– There is a specially designated node called
the root.
– The remaining nodes are partitioned into n>=0 disjoint
sets T1, ..., Tn, where each of these sets is a tree.
– We call T1, ..., Tn the subtrees of the root.

3
Trees

4
 Terminology
• Parent Node: The node which is a predecessor of a
node is called the parent node of that node. {B} is
the parent node of {D, E}.
• Child Node: The node which is the immediate
successor of a node is called the child node of that
node. Examples: {D, E} are the child nodes of {B}.
• Root Node: The topmost node of a tree or the node
which does not have any parent node is called the
root node. {A} is the root node of the tree. A non-
empty tree must contain exactly one root node and
exactly one path from the root to all other nodes of
the tree.
6
 Terminology (2)
• Leaf Node or External Node: The nodes which do
not have any child nodes are called leaf nodes. {K,
L, M, N, O, P} are the leaf nodes of the tree.
• Ancestor of a Node: Any predecessor nodes on the
path of the root to that node are called Ancestors of
that node. {A,B} are the ancestor nodes of the
node {E}
• Descendant: Any successor node on the path from
the leaf node to that node. {E,I} are the
descendants of the node {B}.
• Sibling: Children of the same parent node are
called siblings. {D,E} are called siblings.
7
 Terminology (3)
• Level of a node: The count of edges on the path from
the root node to that node. The root node has level 0.
• The depth of a node is the number of edges present
in path from the root node of a tree to that node.
The height of a node is the number of edges present
in the longest path connecting that node to a leaf
node. Depth of node B is 1 while height is 3.
• Degree of a node: is the number of subtrees of the
node. Degree of node B is 2.
• Internal node: A node with at least one child is called
Internal Node.
• Subtree: Any node of the tree along with its
descendant. 8
 Level and Depth
Level
node (13)
degree of a node
A
3
leaf (terminal) 1 1
nonterminal
parent
children
2
B 2
1
C 2
3
D 2 2
sibling
ancestor 2
E 0
F 0
G 1
H 0
I 0
J 3
descendant 3 3 3 3 3 3

level of a node
height of a tree (4)
0
K 4
0
L 4
0
M 4 4

9
 Applications of Tree DS
• File System: This allows for efficient navigation and
organization of files.
• Data Compression: Huffman coding is a popular technique
for data compression that involves constructing a binary tree
where the leaves represent characters and their frequency
of occurrence. The resulting tree is used to encode the data
in a way that minimizes the amount of storage required.
• Compiler Design: In compiler design, a syntax tree is used to
represent the structure of a program.
• Database Indexing: B-trees and other tree structures are
used in database indexing to efficiently search for and
retrieve data.

10
 Advantages of Tree DS
• Trees reflect structural relationships in the data
providing hierarchical representation which makes
it easy to organize and navigate large amount of
information.
• Tree offer Efficient Insertion and
Searching. Depending on the type of tree, with
average search times of O(log n) for balanced trees
like AVL.
• Trees are very flexible data, allowing to move sub
trees around with minimum effort
• The recursive nature of trees makes them easy to
traverse and manipulate using recursive
algorithms. 11
 Disadvantages of Tree DS
• Unbalanced Trees, meaning that the height
of the tree is skewed towards one side,
which can lead to inefficient search times.
• Trees demand more memory space
requirements than some other data
structures like arrays and linked lists,
especially if the tree is very large.
• The implementation and manipulation of
trees can be complex and require a good
understanding of the algorithms.
12
 Representation of Trees
• A tree data structure can be represented in two
methods.
• List Representation
• Left Child - Right Sibling Representation

13
 Level and Depth
Level
node (13)
degree of a node
A
3
leaf (terminal) 1 1
nonterminal
parent
children
2
B 2
1
C 2
3
D 2 2
sibling
ancestor 2
E 0
F 0
G 1
H 0
I 0
J 3
descendant 3 3 3 3 3 3

level of a node
height of a tree (4)
0
K 4
0
L 4
0
M 4 4

14
 Representation of Trees
List Representation
– It uses two types of nodes one for representing the node
with data and another for representing only references.
– Start with a node with data from root node in the tree.
Then it is linked to an internal node through a reference
node and is linked to any other node directly. This
process repeats for all the nodes in the tree.
– ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )
– The root comes first, followed by a list of sub-trees

data link 1 link 2 ... link n

No of link fields ?
List Representation of Trees

Tree with 11 nodes and 10 edges

• In any tree with N nodes there will be
maximum of N-1 edges
• In a tree every individual element is
called Node

16
List Representation of Trees

17
Left Child - Right Sibling Representation
Only one type of node is used which consists of
three fields namely Data field, Left child reference
field and Right sibling reference field.
A

B C D data
E F G H I J left child right sibling
K L M

18
Left Child - Right Sibling Representation

19
Representation as a degree-2 tree (i.e. Binary Tree)
Left child-right child tree representation of a tree

E C

G D
K F

H
L

M I

J
 Types of Trees
A tree can be classified based on number of
children as:
– Binary Tree
– Ternary tree
– N-ary Tree

21
 Binary Trees
A binary Tree is defined as a Tree data structure with at
most 2 children. Since each element in a binary tree can
have only 2 children, we typically name them the left and
right child.
Any tree can be transformed into binary tree.
– by left child-right sibling representation
Types of Binary Tree based on the number of children:
– Full Binary Tree - A full binary tree is a binary tree with either
zero or two child nodes for each node.
– Degenerate Binary Tree - Degenerate Binary Tree is a Binary
Tree where every parent node has only one child node. If the
only child is left child, the tree is called left-skewed tree.

22
 Binary Trees
On the basis of completion of levels, the binary tree can be
divided into following types:
– Complete Binary Tree - all the levels of the tree are filled
completely except the lowest level nodes which are filled from as
left as possible.
– Perfect Binary Tree - All the leaf nodes are at the same depth,
and all non-leaf nodes have two children
– Balanced Binary Tree – The height of the left subtree and right
subtree of any node does not differ by more than 1 and both the
left and right subtree are also height balanced.

23
Binary Trees

24
 Binary Trees

Full BT? No Full BT? No

Complete BT? Yes Complete BT? No

Perfect BT? Yes Perfect BT? No Perfect BT? No

Complete BT? Yes Complete BT? No 25
Balanced BT? Yes
 Ternary Trees
Each node of this tree has only 3 children
A variety of ternary tree is a Ternary Search Tree (TST)

26
 N-ary Trees
Every node stores the addresses of its children and the
very first node’s address will be stored in a separate
pointer called root.
1. Many children at every node.
2. The number of nodes for each node is not known in
advance.

27
Special Types of Trees based on Value
Binary Search Tree
AVL Tree
B Tree
B+ Tree
Expression Tree

28
 Binary Search Tree (BST)
A binary Search Tree is a node-based binary tree data
structure that 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.

29
 AVL Tree
AVL (Adelson-Velsky and Landis) tree is a self-balancing
Binary Search Tree (BST) where the difference between
heights of left and right subtrees for any node cannot be
more than one.

30
 B Tree
Balanced Tree (B Tree) is used to index the data and
provides fast access to the actual data stored on the disks
It can easily handle massive amounts of data
Traditional binary search trees can become impractical due
to their poor performance and high memory usage
Large number of keys can be stored in a single node, thus,
it has larger branching factor and shallow height

32
 B+ Tree
In B Tree, Keys and records both can be stored in the internal as
well as leaf nodes. Whereas, in B+ tree, records (data) can only be
stored on the leaf nodes while internal nodes can only store the key
values.
The leaf nodes are linked together in the form of a singly linked lists
to make the search queries more efficient.
It can store large amount of data which can not be stored in the main
memory. size of main memory is always limited, the internal nodes
(keys to access records) of the B+ tree are stored in the main
memory whereas, leaf nodes are stored in the secondary memory.

33
 Abstract Data Type Binary_Tree
structure Binary_Tree(abbreviated BinTree) is

objects: a finite set of nodes either empty or consisting of a

root node, left Binary_Tree, and right Binary_Tree.

functions:

for all bt, bt1, bt2  BinTree, item  element

Bintree Create()::= creates an empty binary tree

Boolean IsEmpty(bt)::= if (bt==empty binary tree) return

TRUE else return FALSE 34
 Abstract Data Type Binary_Tree
BinTree MakeBT(bt1, item, bt2)::= return a binary tree whose
left subtree is bt1, whose right subtree is bt2, and whose root
node contains the data item

Bintree Lchild(bt)::= if (IsEmpty(bt)) return error else return

the left subtree of bt

element Data(bt)::= if (IsEmpty(bt)) return error else return the

data in the root node of bt

Bintree Rchild(bt)::= if (IsEmpty(bt)) return error else return

the right subtree of bt
35
 Samples of Trees
Complete Binary Tree

A A 1 A

B B 2 B C

C Skewed Binary Tree

3 D E F G
D

4 H I
E 5

36
 Number of Nodes in BT
The minimum number of nodes in a BT of level n
is n (Applicable for a skewed tree and assuming root is at level 1.
If root is labeled at level 0, it is n+1)
The maximum number of nodes on level i of a
binary tree is 2i-1, i>=1 (Assume root at level 1, for level 0
root, max nodes are 2i)
The maximum number of nodes in a binary tree
of depth k is 2k-1, k>=1.
k
2 = 2 −1
i −1 k

i =1

37
 Number of Leaf Nodes and Nodes of Degree 2

For any nonempty binary tree, T, if n0 is the number of leaf

nodes and n2 the number of nodes of degree 2, then
n0=n2+1
proof:
Let n and B denote the total no. of nodes and branches in T.
Let n0, n1, n2 represent the nodes with no children, single
child, and two children respectively.

n= n0+n1+n2, B+1=n,

B=n1+2n2 ==> n1+2n2+1= n,

n1+2n2+1= n0+n1+n2 ==> n0=n2+1 38

 Binary Tree Representations
If a complete binary tree with n nodes (depth =
log n + 1) is represented sequentially, then for
any node with index i, 1<=i<=n, we have:
– parent(i) is at i/2 if i!=1. If i=1, i is at the root and
has no parent.
– left_child(i) is at 2i if 2i<=n. If 2i>n, then i has no
left child.
– right_child(i) is at 2i+1 if 2i +1 <=n. If 2i +1 >n,
then i has no right child.

39
 [1] A
Sequential Representation [2] B
[3] C
(1) waste space
[4] D
(2) insertion/deletion
A [1] A [5] E
[2] B problem
[6] F
[3] -- [7]
B G
[4] C [8]
A H
[5] -- [9]
C I
[6] --
[7] -- B C
D [8] D
[9] --
. . D E F G
E
[16] E

H I 40
 Linked Representation
typedef struct node *tree_pointer;
typedef struct node {
int data;
tree_pointer left_child, right_child;
};

data

left_child data right_child

left_child right_child

41
 Binary Tree Traversals
Traversal is a process of visiting each node in a
tree data structure exactly once
Traversals are classified by the order in which the
nodes are visited
Let L, V, and R stand for moving left, visiting
the node, and moving right.
There are six possible combinations of traversal
– LVR, LRV, VLR, VRL, RVL, RLV
Adopt the convention that we traverse left before
right, only 3 traversals remain
– LVR, LRV, VLR
42
– inorder, postorder, preorder
Arithmetic Expression Using BT

+ inorder traversal
A/B*C*D+E
infix expression
* E
preorder traversal
+**/AB CDE
* D prefix expression
postorder traversal
AB/C*D*E+
/ C
postfix expression
level order traversal
A B +*E*D /CAB

43
 Inorder Traversal (recursive version)
void inorder(tree_pointer ptr)
/* inorder tree traversal */
{ A/B*C*D+E
if (ptr){
inorder(ptr->left);
printf(“%d”, ptr->data);
indorder(ptr->right);
} O(n)
}

44
 Preorder Traversal (recursive version)
void preorder(tree_pointer ptr)
/* preorder tree traversal */
{ +**/AB CDE
if (ptr) {
printf(“%d”, ptr->data);
preorder(ptr->left);
predorder(ptr->right);
} O(n)
}

45
 Postorder Traversal (recursive version)
void postorder(tree_pointer ptr)
/* postorder tree traversal */
{ AB/C*D*E+
if (ptr) {
postorder(ptr->left);
postdorder(ptr->right);
printf(“%d”, ptr->data);
} O(n)
}

46
 Iterative Inorder Traversal(using stack)
void Iterative_inOrder(struct tree_pointer* root)
{
stack<tree_pointer*> s;
tree_pointer* curr = root;
// Reach the left most Node of the curr Node
while (curr != NULL || s.empty() == false) {
while (curr != NULL) {
s.push(curr);
curr = curr->left;//Move to left child
} //End the loop on last left child

curr = s.pop();

cout << curr->data << " "; O(n)

curr = curr->right;//Now explore right child
}
} 47
Trace Operations of Inorder Traversal
Call of inorder Value in root Action Call of inorder Value in root Action
1 + 11 C
2 * 12 NULL
3 * 11 C printf
4 / 13 NULL
5 A 2 * printf
6 NULL 14 D
5 A printf 15 NULL
7 NULL 14 D printf
4 / printf 16 NULL
8 B 1 + printf
9 NULL 17 E
8 B printf 18 NULL
10 NULL 17 E printf
3 * printf 19 NULL

48
 Level Order Traversal (using queue)
void LevelOrder(struct tree_pointer* root)
{
int rear, front;
struct tree_pointer* curr = root;

while (curr) {
+*E*D /CAB
printf("%d ", curr->data);

if (curr->left) // Enqueue left child

enQueue(queue, curr->left);

if (curr->right) // Enqueue right child

enQueue(queue, curr->right);

curr = deQueue(queue);//Dequeue node

}
} 49
 Construct Binary Tree
Construct a Tree from given Inorder and Preorder
traversals
– In a Preorder sequence, the leftmost element is the root
of the tree.
– Searching that in the Inorder sequence, we can find out
all elements on the left side of that element is in the left
subtree and elements on right in the right subtree.
– Recursively follow the above steps
– Eg. Inorder (40, 20, 50, 10, 60, 30)
Preorder(10, 20, 40, 50, 30, 60)

50
 Construct Binary Tree
Construct a Tree from given Inorder and Postorder
traversals
– In a Postorder sequence, the rightmost element is the
root of the tree.
– Searching that in the Inorder sequence, we can find out
all elements on the left side of that element is in the left
subtree and elements on right in the right subtree.
– Recursively follow the above steps
– Eg. Inorder (4, 8, 2, 5, 1, 6, 3, 7),
Postorder (8, 4, 5, 2, 6, 7, 3, 1)

51
 Construct Binary Tree
Construct a Tree from given Preorder and
Postorder traversals
– Only full binary tree can be constructed
– The leftmost element in PRE is root of tree and next
right element is left child of root and that element of
root of the left subtree.
– All elements before that element in POST must be in
left subtree and after should be in right subtree
– Recursively follow the above steps
– Eg. Preorder (1, 2, 4, 8, 9, 5, 3, 6, 7)
Postorder (8, 9, 4, 5, 2, 6, 7, 3, 1)
52
 Binary Search Tree (BST)
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.
• This means everything to the left of the root is less than the
value of the root and everything to the right of the root is greater
than the value of the root. Due to this performing a binary search
is very easy.
• The left and right subtree each must also be a binary search tree.
• There must be no duplicate nodes (If duplicate values are
permitted, proper duplicate handling approach should be used)
53
 Binary Search Tree (BST)
Handling approach for Duplicate values in the Binary
Search tree:
– You can not allow the duplicated values at all.
– We must follow a consistent process throughout i.e either store
duplicate value at the left or store the duplicate value at the right
of the node, but be consistent with your approach.
– We can keep the counter with the node and if we found the
duplicate value, then we can increment the counter

54
 Insert node in BST
Insertion operation can be implemented using a recursive
function
1. Create a new BST node and assign values to it.
2. insert(node, key)
i) If (root == NULL)
return the new node to the calling function.
ii) if (root -> data < key)
call the insert function with root->right and assign the return value in
root->right.
root->right = insert(root->right, key)
iii) if (root->data > key)
call the insert function with root->left and assign the return value in
root=>left.
root->left = insert(root->left, key)
3. Finally, return the original root pointer to the calling function.

55
Insertion in BST

56
struct node {
Insert node in BST
int key;
struct node *left, *right;
};
struct node* newNode(int item) // Function to create a new BST node
{
struct node* temp = (struct node*)malloc(sizeof(struct node));
temp → key = item;
temp → left = temp → right = NULL;
return temp;
}
struct node* insert(struct node* node, int key)
{
if (node == NULL) // If the tree is empty, return a new node
return newNode(key);
if (key < node → key) { // Otherwise, recur down the tree
node → left = insert(node → left, key);
}
else if (key > node → key) {
node → right = insert(node → right, key);
}
return node; // Return the node pointer
57
}
 Searching in BST
Searching means to find or locate a specific element or node
in a data structure.
Searching a node in BST is easy because elements are
stored in a specific order.
– First, compare the element to be searched with the root of the tree.
– If root matches with the target, then return the node's location.
– If no match, check whether the item is less than the root element, if
it is smaller than the root element, then move to the left subtree.
– If it is larger than the root element, then move to the right subtree.
– Repeat the above procedure recursively until the match is found.
– If the element is not found or not present in the tree, then return
NULL.
58
 Searching in BST
Element to be searched is 20

Step 1 Step 2

Step 3

59
 Searching in BST
Search (root, item)
Step 1 - if (item = root → data) or (root = NULL)
return root
else if (item < root → data)
return Search(root → left, item)
else
return Search(root → right, item)
END if
Step 2 - END

60
 Delete node from BST
The deletion process is different for different node positions
– Node to be deleted is a leaf node
– Node to be deleted has only one child
– Node to be deleted has two children
Node to be deleted is a leaf node

61
 Delete node from BST
Node to be deleted has only one child

62
 Delete node from BST
Node to be deleted has two children
– First, find the inorder successor of the node to be deleted.
– Replace that node with the inorder successor until the target node
is placed at the leaf of tree.
– Replace the node with NULL and free up the allocated space.

63
 Complexity of operations in BST

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)

64
 AVL Tree
AVL tree is a self-balanced binary search tree
A binary tree is said to be balanced if the difference between the
heights of left and right subtrees of every node in the tree is either -1,
0, or +1
In an AVL tree, every node maintains an extra information known as
the balance factor.
The balance factor of a node is the difference between the heights of
the left and right subtrees of that node.
Balance factor = heightOfLeftSubtree - heightOfRightSubtree

Every AVL Tree is a binary search tree, but all the

Binary Search Trees need not be AVL trees.

65
 AVL Tree Rotations
In AVL tree, after performing every operation like insertion and
deletion, the balance factor of every node in the tree needs to be
checked.
If every node satisfies the balance factor condition, the operation is
concluded; otherwise, the tree should be balanced.
Rotation operations are performed to make the tree balanced
whenever the tree becomes imbalanced due to any operation.
Rotation is the process of moving the nodes to either left or right to
make the tree balanced.
There are four rotations and they are classified into two types.

66
AVL Tree Rotations
Single Left Rotation (LL Rotation)

Single Right Rotation (RR Rotation)

67
AVL Tree Rotations
Left Right Rotation (LR Rotation)

Right Left Rotation (RL Rotation)

68
AVL Tree Rotations

69
AVL Tree Rotations
Left Right Rotation (LR Rotation)

70
Insertion in AVL Tree
63, 9, 19, 27, 18, 108, 99, 81

71
 Deletion in AVL Tree
Deleting a node from an AVL tree is similar to that in a binary search
tree.
Deletion may disturb the balance factor of an AVL tree and therefore
the tree needs to be rebalanced in order to maintain the AVLness.
If the node which is to be deleted is present in the left sub-tree of the
critical node, then L rotation needs to be applied else if, the node
which is to be deleted is present in the right sub-tree of the critical
node, the R rotation will be applied.

72
 Deletion in AVL Tree
R0 rotation
A is the critical node, B is root of left subtree.
If the balance factor of B is 0, R0 rotation is to be applied which is
equivalent to RR rotation

73
Deletion in AVL Tree
R0 rotation

74
 Deletion in AVL Tree
R1 rotation
If the balance factor of B is 1, R1 rotation is to be performed, which is
equivalent to RR rotation

75
Deletion in AVL Tree
R1 rotation

76
 Deletion in AVL Tree
R-1 rotation
R-1 rotation is to be performed if the node B has balance factor -1.
This is equivalent to LR rotation
The node C, which is the right child of node B, becomes the root node
of the tree with B and A as its left and right children respectively.

77
Deletion in AVL Tree
R-1 rotation

78
 B Tree
B Tree (Balanced Tree), a versatile data structure that
handles enormous quantities of data with ease.
Due to their slow pace and large memory usage, traditional
binary search trees may become impractical for storing and
searching huge volumes of data.
B Trees stores large number of keys in a single node, which
is why they are also known as “large key” trees.
Each node in a B Tree can contain multiple keys, which
allows the tree to have a larger branching factor and, thus a
shallower height.

79
 B Tree
B Trees are well suited for storage systems with slow, bulky
data access, such as hard drives, flash memory, and CD-
ROMs
B Trees maintains balance by ensuring that each node has a
minimum number of keys, so the tree is always balanced
Since accessing values stored in a large database that is
stored on a disc takes a long time, B trees are used to index
the data and provide quick access to the actual data stored
on the disks
In the worst case, it takes O(n) running time to search a
database with n key values that are not sorted or indexed.
However, if we use B Tree to index this database, it will be
searched in O (log n) time in the worst case
80
 Properties of B Tree
• All leaves are at the same level
• B Tree is defined by the term minimum degree ‘t‘ and order ‘m’. The
degree is the lower bound on the number of children of a node, while
the order represents the upper bound on the number of children
• Every node except the root must contain at least t-1 keys. The root
may contain a minimum of 1 key
• All nodes (including root) may contain at most (2*t – 1) keys
• The number of children of a node equals the number of keys in it
plus 1
• All keys of a node are sorted in increasing order. The child between
two keys k1 and k2 contains all keys in the range from k1 and k2
• B-Tree grows and shrinks from the root, unlike Binary Search Tree.
Binary Search Trees grow downward and also shrink from downward
81
 B Tree
B-Tree of degree 3

All leaf nodes are at the same level, and all non-leafs have no empty
sub-tree and have keys one less than the number of their children.

82
 Searching in B Tree
• Searching in B Trees is similar to that in Binary search tree.
• Algorithm
• Start from the root and recursively traverse down
• For every visited non-leaf node,
• If the node has the key, we simply return the node
• Otherwise, we recur down to the appropriate child (The child which is just before the
first greater key) of the node.
• If we reach a leaf node and don’t find k in the leaf node, then return NULL.

83
 Insertion in B Tree
• Insertions are done at the leaf node level
• Algorithm
1. Traverse the B Tree in order to find the appropriate leaf node at which the node
can be inserted
2. If the leaf node contains less than m-1 keys, insert the element in the increasing
order
3. Else, if the leaf node contains m-1 keys, then follow the following steps
• Insert the new element in the increasing order of elements
• Split the node into the two nodes at the median
• Push the median element up to its parent node
• If the parent node also contains m-1 number of keys, then split it too by following
the same steps

84
 Insertion in B Tree
• Insert the node 8 into the B Tree of order 5 shown in the following

• 8 will be inserted to the right of 5, therefore insert 8

85
 Insertion in B Tree
• The node contains 5 keys which is greater than (5 -1 = 4) keys.
Therefore split the node from the median i.e. 8, and push it up to its
parent node

86
 Deletion in B Tree
• Deletion is also performed at the leaf nodes. The node which is to be
deleted can either be a leaf node or an internal node
• Algorithm
• Locate the leaf node
• If there are more than m/2 keys in the leaf node then delete the desired key from
the node
• If the leaf node doesn't contain m/2 keys, then complete the keys by taking the
element from the right or left sibling
• If the left sibling contains more than m/2 elements, then push its largest element up to its parent
and move the intervening element down to the node where the key is deleted
• If the right sibling contains more than m/2 elements, then push its smallest element up to the
parent and move the intervening element down to the node where the key is deleted
• If neither of the sibling contain more than m/2 elements then create a new leaf
node by joining two leaf nodes and the intervening element of the parent node
• If the parent is left with less than m/2 nodes, then apply the above process on the
parent too
87
 Deletion in B Tree
• Delete the node 53 from the B Tree of order 5

• 53 is present in the right child of element 49. Delete it

88
 Deletion in B Tree
• 57 is the only element which is left in the node, the minimum number
of elements that must be present in a B tree of order 5, is 2.
• The elements in its left and right sub-tree are also not sufficient
therefore, merge it with the left sibling and intervening element of
parent i.e. 49.

89
 B+ Tree
• B tree stores data pointers on each node of the tree. B+ tree eliminates
this drawback by storing data pointers only at the leaf nodes of the
tree.
• The structure of leaf nodes of a B+ tree is quite different from the
structure of internal nodes of the B tree
• Since data pointers are present only at the leaf nodes, the leaf nodes
must necessarily store all the key values along with their
corresponding data pointers to the disk file block to access them
• The leaf nodes are linked to providing ordered access to the records
• The leaf nodes, therefore, form the first level of the index, with the
internal nodes forming the other levels of a multilevel index
• Some of the key values of the leaf nodes also appear in the internal
nodes
90
B+ Tree

91
 B+ Tree
Structure of leaf node

92
 B Tree and B+ Tree
Basis of Comparison B tree B+ tree
All internal and leaf nodes have data
Pointers Only leaf nodes have data pointers
pointers

Since all keys are not available at leaf, All keys are at leaf nodes, hence
Search
search often takes more time. search is faster and more accurate.

No duplicate of keys is maintained in Duplicate of keys are maintained

Redundant Keys
the tree. and all nodes are present at the leaf.

Insertion takes more time and it is not Insertion is easier and the results are
Insertion
predictable sometimes. always the same.

Deletion of the internal node is very

Deletion of any node is easy
Deletion complex and the tree has to undergo a
because all node are found at leaf.
lot of transformations.

Leaf nodes are not stored as structural Leaf nodes are stored as structural
Leaf Nodes
linked list. linked list.

Sequential access to nodes is not Sequential access is possible just

Access
possible like linked list

93
 Heap
A max tree is a tree in which the key value in each
node is no smaller than the key values in its
children. A max heap is a complete binary tree that
is also a max tree.
A min tree is a tree in which the key value in each
node is no larger than the key values in its children.
A min heap is a complete binary tree that is also a
min tree.
Operations on heaps
– creation of an empty heap
– insertion of a new element into the heap
– deletion of the largest element from the heap 94
 Sample max heaps

[1] [1] 9 [1] 30

14

[2] 12 [3] 7 [2] 6 [3] 3 [2]

25
[4] [5] [6] [4]
10 8 6 5

Property:
The root of max heap (min heap) contains the largest (smallest)
Sample min heaps

[1] [1] 10 [1] 11

2

[2] 7 [3] 4 [2] 20 [3] 83 [2]

21
[4] [5] [6] [4]
10 8 6 50
structure MaxHeap ADT for Max Heap
objects: a complete binary tree of n > 0 elements organized so that
the value in each node is at least as large as those in its children
functions:
for all heap belong to MaxHeap, item belong to Element, n,
max_size belong to integer
MaxHeap Create(max_size)::= create an empty heap that can
hold a maximum of max_size elements
Boolean HeapFull(heap, n)::= if (n==max_size) return TRUE
else return FALSE
MaxHeap Insert(heap, item, n)::= if (!HeapFull(heap,n)) insert
item into heap and return the resulting heap
else return error
Boolean HeapEmpty(heap, n)::= if (n>0) return FALSE
else return TRUE
Element Delete(heap,n)::= if (!HeapEmpty(heap,n)) return one
instance of the largest element in the heap
and remove it from the heap
else return error 97
 Application: priority queue

unordered linked list

unordered array
sorted linked list
sorted array
heap

98
Priority queue representations

Representation Insertion Deletion

Unordered (1) (n)

array
Unordered (1) (n)
linked list
Sorted array O(n) (1)
Sorted linked O(n) (1)
list
Max heap O(log2n) O(log2n)
 Insertion to Max Heap

20 20 21

15 2 15 5 15 20

14 10 14 10 2 14 10 2

initial location of new node insert 5 into heap insert 21 into heap

100
 Deletion from Max Heap

remove
20 10 15

15 2 15 2 14 2

14 10 14 10

102
 Graphs
• A graph is an abstract data type (ADT) consisting of a set of objects
connected to each other via links. These objects are called vertices,
and the links are called edges
• Usually, a graph is represented as G = {V, E}, where G is the graph
space, V is the set of vertices, and E is the set of edges. If E is empty,
the graph is known as a forest.

105
 Directed and Undirected Graph
• In an undirected graph, edges are not associated with the directions
with them

• In a directed graph, edges form an ordered pair. Edges represent a

specific path from some vertex A to another vertex B. Node A is called
initial node while node B is called terminal node.

106
 Graph Terminology
• Vertex: Each node of the graph is represented as a vertex
• Edge: Edge represents a path between two vertices or a line between
two vertices
• Path: A path can be defined as the sequence of nodes that are
followed to reach some terminal node V from the initial node U.
• Closed Path: A path will be called as closed path if the initial node is
same as terminal node. A path will be closed path if V0=VN.
• Simple Path: If all the nodes of the graph are distinct with an
exception V0=VN, then such path P is called as closed simple path.
• Cycle: A cycle can be defined as the path which has no repeated edges
or vertices except the first and last vertices.
• Connected Graph: A connected graph is the one in which some path
exists between every two vertices (u, v) in V. There are no isolated
nodes in connected graph.
107
 Graph Terminology
• Complete Graph: A complete graph is the one in which every node is
connected with all other nodes. A complete graph contain n(n-1)/2
edges where n is the number of nodes in the graph.
• Weighted Graph: Each edge is assigned with some value such as
length or weight. The weight of an edge e can be given as w(e), which
must be a positive (+) value indicating the cost of traversing the edge.
• Digraph: A digraph is a directed graph in which each edge of the
graph is associated with some direction, and the traversing can be
done only in the specified direction.
• Loop: An edge that is associated with similar endpoints can be called
a Loop.
• Adjacent Nodes: If two nodes, u and v, are connected via an edge e,
then the nodes u and v are called as neighbors or adjacent nodes.
• Degree of the Node: A degree of a node is the number of edges that
are connected with that node. A node with degree 0 is called an
108
isolated node.
 Representation of Graphs
• A graph can be represented in memory using
• Sequential representation (or, Adjacency matrix representation)
• Linked list representation (or, Adjacency list representation)
• In sequential representation, an adjacency matrix is used to
represent the mapping between vertices and edges of the graph. It can
represent the undirected, directed, weighted directed, and weighted
undirected graph.
• adj[i][j] = w, it means that there is an edge exists from vertex i to
vertex j with weight w
• An entry Aij in the representation of an undirected graph G will be 1 if
an edge exists between Vi and Vj. If an Undirected Graph G consists
of n vertices, then the adjacency matrix for that graph is n x n, and the
matrix A = [aij] can be defined as -
aij = 1 {if there is a path exists from Vi to Vj}
aij = 0 {Otherwise} 109
 Representation of Graphs
It means that, in an adjacency matrix, 0 represents that there is no
association exists between the nodes, whereas 1 represents the
existence of a path between two edges.
If there is no self-loop present in the graph, it means that the diagonal
entries of the adjacency matrix will be 0.

110
 Representation of Graphs
Adjacency matrix for directed unweighted graphs

Adjacency matrix for directed weighted graphs

111
 Representation of Graphs
Linked list representation (or Adjacency list representation)
A linked list or adjacency list is maintained for every node of the
graph
An adjacency list is maintained for each node present in the graph,
which stores the node value and a pointer to the next adjacent node to
the respective node. If all the adjacent nodes are traversed, then store
the NULL in the pointer field of the last node of the list
The sum of the lengths of adjacency lists is equal to twice the number
of edges present in an undirected graph.

112
 Representation of Graphs
Linked list representation for directed graph

Linked list representation for weighted directed graph

113
 Adjacency Representation of Graphs
/* function to print the matrix elements */
/* Adjacency Matrix representation of an undirect
void printAdjMatrix(int arr[][V]) {
ed graph in C */
int i, j;
#include <stdio.h>
for (i = 0; i < V; i++) {
#define V 4 /* number of vertices in the graph */
printf("%d: ", i);
for ( j = 0; j < V; j++) {
/* function to initialize the matrix to zero */
printf("%d ", arr[i][ j]);
void init(int arr[][V]) {
}
int i, j;
printf("\n");
for (i = 0; i < V; i++)
}
for ( j = 0; j < V; j++)
}
arr[i][ j] = 0;
}
int main() {
/* function to add edges to the graph */
int adjMatrix[V][V];
void insertEdge(int arr[][V], int i, int j) {
arr[i][ j] = 1;
init(adjMatrix);
arr[ j][i] = 1;
insertEdge(adjMatrix, 0, 1);
}
insertEdge(adjMatrix, 0, 2);
insertEdge(adjMatrix, 1, 2);
insertEdge(adjMatrix, 2, 0);
insertEdge(adjMatrix, 2, 3);
printAdjMatrix(adjMatrix);
return 0; 114
}
 Spanning Tree
A spanning tree is a subset of an undirected graph that contains all
the vertices of the graph connected with the minimum number of
edges in the graph
The edges of the spanning tree is a subset of the edges in the original
graph.
In a graph, there may exist more than one spanning tree.
A spanning tree does not have any cycle.
Any vertex can be reached from any other vertex.

115
 Minimum Spanning Tree
A Minimum Spanning Tree (MST) is a subset of edges of a
connected weighted undirected graph that connects all vertices with
the minimum possible total edge weight.
If there are n number of vertices, the spanning tree should have 𝒏−𝟏
number of edges.

116
 Prim’s algorithm for MST
1. Determine an arbitrary vertex as the starting vertex of the MST.
2. Follow steps 3 to 5 till there are vertices that are not included in the
MST (known as fringe vertex).
3. Find edges connecting any tree vertex with the fringe vertices.
4. Find the minimum among these edges.
5. Add the chosen edge to the MST if it does not form any cycle.
6. Return the MST and exit

117
Prim’s algorithm for MST

118
Prim’s algorithm for MST

119
Prim’s algorithm for MST

120
Prim’s algorithm for MST

121
Prim’s algorithm for MST

122
Prim’s algorithm for MST

123
Prim’s algorithm for MST

124
Prim’s algorithm for MST

125
Prim’s algorithm for MST

126
Prim’s algorithm for MST

127
Prim’s algorithm for MST

128
 Kruskal’s algorithm for MST
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning
tree formed so far. If the cycle is not formed, include this edge. Else,
discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.

129
Kruskal’s algorithm for MST
Weight Source Destination

1 7 6

2 8 2

2 6 5

4 0 1

4 2 5

6 8 6

7 2 3

8 0 7

8 1 2

9 3 4

10 5 4

11 1 7

14 3 130 5
 Kruskal’s algorithm for MST
Step 1 Step 4

Step 2

Step 5

Step 3

131
 Kruskal’s algorithm for MST

Step 7
Step 6

Step 8

132
 Graph Traversal
The process of visiting or updating each vertex in a graph is known as
graph traversal.
There are two techniques to implement a graph traversal algorithm:
– Breadth-first search
– Depth-first search
Breadth-First Search or BFS
It begins at the root of the graph and investigates all nodes at the
current depth level before moving on to nodes at the next depth level.
To maintain track of the child nodes that have been encountered but
not yet inspected, generally you require a queue.

133
 Breadth-First Search
1. Enqueue the starting node A.
2. Dequeue a node N. Process it and enqueue all its neighbor
3. Repeat Step 2 until QUEUE is empty

134
 Depth-First Search
The algorithm starts at the root node and explores as far as possible
along each branch before backtracking.
 References
https://www.geeksforgeeks.org/types-of-trees-
in-data-structures/
http://cis.stvincent.edu/swd/btree/btree.html

136