Data Structures and Algorithms (CS-2001)

KALINGA INSTITUTE OF INDUSTRIAL

TECHNOLOGY

School of Computer Engineering

Strictly for internal circulation (within KIIT) and reference only. Not for outside circulation without permission

4 Credit Lecture Note

 Chapter Contents
2

Sr # Major and Detailed Coverage Area Hr

s
5 Trees 8
Introduction, Binary Trees, Binary Tree
Traversals, Threaded Binary Trees, Binary
Search Trees, AVL Trees, m-way search
Trees, B-Trees, B+ Trees, Tree Operation,
Forests

School of Computer Engineering

Introduction
3
There are many basic data structures that can be used to solve application problems. Array is a good data
structure that can be accessed randomly and is fairly easy to implement. Linked Lists on the other hand is
dynamic and is ideal for application that requires frequent operations such as add, delete, and update. One
drawback of linked list is that data access is sequential. Then there are other specialized data structures like,
stacks and queues that allows to solve complicated problems using these restricted data structures.

One of the disadvantages of using an array or linked list to store data is the time necessary to search for an
item. Since both the arrays and Linked Lists are linear structures the time required to search a “linear” list is
proportional to the size of the data set. For example, if the size of the data set is n, then the number of
comparisons needed to find (or not find) an item may be as bad as n. So imagine doing the search on a linked list
(or array) with n = 106 nodes. Even on a machine that can do million comparisons per second, searching for m
items will take roughly m seconds. This not acceptable in today’s world where speed at which we complete
operations is extremely important. Time is money. Therefore it seems that better (more efficient) data
structures are needed to store and search data.

In this chapter, we can extend the concept of linked data structure (linked list, stack, queue) to a structure that
may have multiple relations among its nodes. Such a structure is called atree. A tree is a nonlinear data
structure, compared to arrays, linked lists, stacks and queues which are linear data structures.

School of Computer Engineering

To Become Rich
4

Become Rich

Unethical Ways Ethical Ways

Force others Rob Stock Invest Avoid Depreciated Save

to be Poor Banks Fraud Value Purchase Money

Real Stock Your Retirement

Estate Market Time

School of Computer Engineering

Nature View of a Tree
5

leaves

branches
root

School of Computer Engineering

Computer View
6

root

leaves

branches
nodes

School of Computer Engineering

What is a Tree?
7

❑ A tree is a finite
nonempty set of nodes
and edges without
having any cycle.
❑ It is an abstract model
of a hierarchical
structure.
❑ Nodes represents the
parent-child relation.

Which of the following are tree?

School of Computer Engineering

Tree Terminology
8
❑ Path − Refers to sequence of nodes along the edges of a tree.
❑ Root Node − Node at the top of the tree is called root. There is only
A
one root per tree and one path from root node to any node. So
node without parent is also called root.
❑ Parent Node − Any node except root node has one edge upward to a
node. B C D
❑ Child Node − Node below a given node connected by its edge
downward.
Subtree
❑ Leaf Node - Node which does not have any child node.
❑ Internal Node – Node with at least one child E F G H
❑ Subtree − Subtree represents descendents of a node.
❑ Visiting − Refers to checking value of a node when control is on the
node.
❑ Traversing − Passing through nodes in a specific order. I J K
❑ Levels − Level of a node represents the generation of a node. If root
❑ Ancestors of a node: parent, grandparent,
node is at level 0, then its next child node is at level 1, its grandchild is
grand-grandparent, etc.
at level 2 and so on.
❑ Descendant of a node: child, grandchild,
❑ Keys − Key represents a value of a node based on which a search
grand-grandchild, etc.
operation is to be carried out for a node.
❑ Depth of a node: number of ancestors. Depth of
❑ Degree – The degree of a node is the number of its children & the
tree is 1 more than the maximum depths of the
degree of a tree is the maximum degree of any of its node.
depths of the left and right subtrees of tree
❑ Siblings – nodes share the same parent
❑ Height of a tree: maximum depth of any node

School of Computer Engineering

Class Work
9

A Sr # Property Value
1 Number of nodes of the tree
2 Height of the tree
B C 3 Root Node of the tree
4 Leaves of the tree
5 Interior nodes of the tree
6 Ancestors of H node
D E F 7 Descendants of B node
8 Siblings of E node
9 Right subtree of A node
10 Degree of the tree
G 11 Parent node of D
12 Child nodes of G
13 Level of node G
H I

School of Computer Engineering

Intuitive Representation
10

Every tree node:

❑ INFO – useful information

❑ Child – pointers to its children

Data

Data Φ Φ Φ Data Φ Data Φ Φ

Data Φ Φ Φ Data Φ Φ Φ Data Φ Φ Φ

School of Computer Engineering

Trees Application
11

Tree is a fundamentally hierarchical structure. Thus, a tree is appropriate to model any reality that
exhibits hierarchy:
❑ File system directories.
❑ Genealogical trees of all sorts: family relationships among individuals, tribes, languages etc.
❑ Classifications systems:
❑ Taxonomic classification of plants and animals.
❑ Dewey decimal (or Library of Congress) classification of books.
❑ Breakdown of a manufactured product into subassemblies, each of turn consists of
sub-subassemblies etc. down to the smallest components.
❑ Structure of a program - main routine is the root, procedures it contains are subtrees, each of
which contains nested procedure definitions etc.
❑ Information storage and retrieval situations such as symbol tables, even though hierarchy may
not be involved.
❑ Expression Tress – Compilers and Interpreters as well in symbolic mathematics program to
represent arithmetic expressions.
❑ Game Tree – Game playing

School of Computer Engineering

Binary Trees
12

A binary tree T is defined as a finite set of elements called node such that :

a. T is empty (called the empty tree or null tree) or

b. T contains a distinguished node R, called the root node of T and the remaining
nodes of T form an ordered pair of disjoint binary trees T1 and T2.

So - a binary tree is a tree data structure in which each node has at most two children
(i.e. either 0 or 1 or 2), which are referred to as the left child and the right child.

If T contains a root R, then the two trees T1 and T2 are called the left and right subtree
of R. If T1 is non empty then its root is called the left successor of R. Similarly if T2 is
not empty then its root is called the right successor of R.

T1 T2

School of Computer Engineering

Similar Trees and Tree Copies
13

Similar Tree
Trees Copies
Binary trees are said to be The trees are said to be
similar if they have the copies if they are similar
same structure or in other and if they have same
words, if they have the contents at corresponding
same shape. nodes

School of Computer Engineering

Binary Expression Trees
14

A binary expression tree is a specific kind of a binary tree used to represent

expressions. Each node of a binary tree, and hence of a binary expression tree,
has zero, one, or two children. This restricted structure simplifies the
processing of expression trees. The leaves of a binary expression tree are
operands, such as constants or variable names, and the other nodes contain
operators i.e. each internal node corresponds to operator and each leaf node
corresponds to operand.

School of Computer Engineering

Algebraic Expressions Representation
15

((3+4)*(1-2))

3 + ((5+9)*2)

School of Computer Engineering

Expression Tree Class Work
16

Draw the expression tree corresponding to the following:

❑ E = (a/(b + d)) + ((a2 – d2)/2)

❑ F = ((X +Y)^2) – ((X-4)/12)
❑ A = 10/4 + 2*(5+1)
❑ X = ((5*A+B)*(3*C+D))^3
❑ Y = (35 - 3*(3+2)) / 4

School of Computer Engineering

Full and Complete Binary Trees
17

Full Binary Complete Binary

Tree ATree
binary tree T with n levels is
A binary tree T if each
node is either a leaf or complete if all levels except
possibly the last are completely
possesses exactly two
full, and the last level has all its
child nodes.
nodes to the left side.
Class Work

Full but not Complete Complete but not Full Full and Complete Neither Full nor Complete

School of Computer Engineering

Extended Binary Trees : 2-Trees
18

The tree is said to be strictly or extended or 2-trees binary tree, if every

non-leaf made in a binary tree has non-empty left and right sub trees. A
strictly binary tree with n leaves always contains 2*n–1 nodes.

School of Computer Engineering

Extended Binary Trees cont…
19

The main application of a 2-tree is to represent and compute any algebraic

expression using binary operation. For example, consider an algebraic expression
E, where E = (a +b ) / ((c – d) * e)

School of Computer Engineering

Representing Binary Trees in Memory
20

Let T be the binary tree. There are 2 ways of representing binary tree in memory.
The first and usual way is called the link representation of T and the second
way which uses a single array called the sequential representation of T.
Sequential
Representation
Binary Trees can be represented using 1-D array in memory. The rule to store
binary tree in array are :

❑ The values of binary tree is stored in an array called as tree.

❑ The root of the tree is stored at first location i.e. at tree[0](or at 0 th index).
❑ The left child of tree is stored at 2i +1 and right child is stored at 2i+2 location.
❑ The maximum size of the array tree is given as 2h+1-1, where h is the height of the tree.
❑ An empty tree or sub-tree is specified using NULL. If tree[0] = NULL, then it means that
tree is empty.

School of Computer Engineering

Sequential Representation of Binary Tree
21

tree

Position of left and right child

School of Computer Engineering

Linked Representation of Binary Tree
22

Approach 1 - Parallel
Array
Consider a binary tree T. The linked representation uses three parallel arrays i.e.
INFO,LEFT & RIGHT & a pointer variable ROOT. Each node N of T will correspond
to a location K such that:

❑ INFO[K] contains the data at node N.

❑ LEFT[K] contains the location of left child of node N.
❑ RIGHT[K] contains the location of right child of node N.
❑ ROOT will contain location of root R of T.

If any subtree is empty, then the corresponding pointer will contain NULL values;
if the tree T itself is empty, then ROOT will contain NULL

School of Computer Engineering

Linked Representation – Parallel Arrays
23

School of Computer Engineering

Linked Representation of Binary Tree
24

Approach 2 - Nodes
Binary trees can be represented by links where each node contains the address of
the left child and the right child. If any node has its left or right child empty then
it will have in its respective link field, a null value. A leaf node has null value in
both of its links.

The structure defining a node of binary tree in C is as follows.

struct node
{
struct node *leftChild ; /* points to the left child */
int data; /* data field */
struct node *rightChild; /* points to the right child */
}

School of Computer Engineering

Linked Representation – Nodes
25

Node
Structure

Illustratio
n

School of Computer Engineering

Binary Tree Node Structure & Basic Operation
26

A tree node should look like the below structure. It has data part and references to its left and right
child nodes.

struct node
{
struct node *leftChild;
int data;
struct node *rightChild;
} *root;

Basic operations that can be performed on binary search tree data structure, are −
❑ Insert − insert a node in a tree / create a tree.
❑ Search − search an element in a tree.
❑ Delete – Delete the tree or delete a node in the tree.
❑ Preorder Traversal − traverse a tree in a preorder manner.
❑ Inorder Traversal − traverse a tree in an inorder manner.
❑ Postorder Traversal − traverse a tree in a postorder manner.

School of Computer Engineering

Binary Tree Traversal
27

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, traverse always start from the
root node and one cannot random access a node in tree. There are three ways to
traverse a tree −

❑ In-order Traversal
❑ Pre-order Traversal
❑ Post-order Traversal

School of Computer Engineering

In-order Traversal
28

In this traversal method, the left-subtree is visited first, then root and then the
right sub-tree.
Recursive Algorithm
Step 1 − Start
Step 2 − Repeat steps 3, 4 and 5 until all nodes
are traversed
Step 3 − Recursively traverse left subtree
Step 4 − Visit root node
Step 5 − Recursively traverse right subtree
Step 6 − Stop
Output
Traversal start from A, and following in-order traversal, we move to its left subtree B. B is also traversed
in-ordered and the process goes on until all the nodes are visited. The output of in-order traversal of this tree is
D→B→E→A→F→C→G

School of Computer Engineering

Pre-order Traversal
29

In this traversal method, the root node is visited first, then left subtree and finally
right sub-tree.
Recursive Algorithm
Step 1 − Start
Step 2 − Repeat steps 3, 4 and 5 until all nodes
are traversed
Step 3 − Visit root node
Step 4 − Recursively traverse left subtree
Step 5 − Recursively traverse right subtree
Step 6 − Stop
Output
Traversal 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-ordered. And the process goes on until all the nodes are visited. The
output of pre-order traversal of this tree is A → B → D → E → C → F → G

School of Computer Engineering

Post-order Traversal
30

In this traversal method, the root node is visited last, hence the name. First the
left subtree is traversed, then right subtree and finally root.
Recursive Algorithm
Step 1 − Start
Step 2 − Repeat steps 3, 4 and 5 until all nodes
are traversed
Step 3 − Recursively traverse left subtree
Step 4 − Recursively traverse right subtree
Step 5 − Visit root node
Step 6 − Stop
Output
Traversal start from A, and following pre-order traversal, we first visit left subtree B. B is also traversed
post-ordered. And the process goes on until all the nodes are visited. The output of post-order traversal
of this tree is D → E → B → F → G → C → A

School of Computer Engineering

Binary Tree C Implementation
31

School of Computer Engineering

Level-order Traversal
32

In this traversal method, visit the nodes level by level from left to right
Recursive Algorithm
Step 1 − Start
Step 2 − Visit the root node (Level 0)
Step 3 − Visit the root’s left child followed by
right child (Level 1)
Step 4 − Recursively visit the next levels from left
most child to right most child (Level 2 and
onwards) until all levels are covered
Step 5 − Stop

Output 10 → 12 → 23 → 14 → 15 → 16 → 27 →
28
School of Computer Engineering
Class Work
33
What are the In Order, Pre Order and Post Order traversal sequence of following trees?

In Order : B → D → A → G → E → C → H → F → I In Order : a → b → c → d → e → f → g → h → i → j → k
Pre Order : A → B → D → C → E → G → F → H Pre Order : f → b → a → d → c → e → i → h → g → k → j
→I
Post Order : a → c → e → d → b → g → h → j → k → i → f
Post Order : D → B → G → E → H → I → F → C
→Note
A
In Order : LPR Pre Order : PLR Post Order : LRP

P: Parent, L: Left and R: Right

School of Computer Engineering
In-Order Traversal Non-Recursive Algorithm
34

1. Create a stack.
2. Push the root into the stack and set the root = root.left and continue till it hits NULL.
3. If root is null and stack is empty then
return // we are done.
Else
pop the top node from the stack and set it as, root = popped_node.
print the root and go right, root = root.right.
Go to step 2.
4. End If

Animation
http://algorithms.tutorialhorizon.com/files/2015/12/Inorder1.gif
Class Work
❑ Design non-recursive algorithm for Pre-order Traversal
❑ Design non-recursive algorithm for Post-order Traversal
School of Computer Engineering
Class Work – Construction of Binary Tree
35

In Order : B → D → A → G → E → C → H → F → I

Is the tree different? If so – don’t worry

With one sequence, it is not possible to estimate the
left/right child of the tree. So a given In-Order
sequence, will not generate exact binary tree. Similarly
given Pre-Order or Post-order sequence will not
generate exact binary tree. So to generate the exact
binary tree, more than 2 traversal sequence is mandate.
If you are given two traversal sequences, can you construct the binary tree?
It depends on what traversals are given. If one of the traversal methods is In-order then the
tree can be constructed, otherwise not. Therefore, following combination can uniquely identify
a tree.
❑ In-order and Pre-order
❑ In-order and Post-order

School of Computer Engineering

Construction of Binary Tree from In Order and Pre Order Traversal

36

In Order : LPR and Pre Order : PLR

In Order : B → D → A → G → E → C → H → F → I
Pre Order : A → B → D → C → E → G → F → H → I
Steps to be followed
❑ First element in the Pre Order is the root of the tree,
hence it is A
❑ Now search element A in “In Order”, say you find it
at position i, once you find it, make note of elements
which are left to i (this will construct the left
subtree) and elements which are right to i ( this will
construct the right subtree).
❑ Recursively construct left subtree and link it root
left and recursively construct right subtree and link
it root right.
P: Parent, L: Left and R: Right
School of Computer Engineering
Construction of Binary Tree from In Order and Pre Order Traversal

37

In Order : {2,5,6,10,12,14,15} and Pre Order : {10,5,2,6,14,12,15}

School of Computer Engineering

Construction of Binary Tree from In Order and Post Order Traversal

38

In Order : LPR and Post Order : LRP

In Order : B → D → A → G → E → C → H → F → I
Post Order : D → B → G → E → H → I → F → C → A
Steps to be followed
❑ Last element in the Post Order is the root of the tree,
hence it is A
❑ Now search element A in “In Order”, say you find it
at position i, once you find it, make note of elements
which are left to i (this will construct the left
subtree) and elements which are right to i ( this will
construct the right subtree).
❑ Recursively construct left subtree and link it root
left and recursively construct right subtree and link
it root right.
P: Parent, L: Left and R: Right
School of Computer Engineering
Construction of Binary Tree from In Order and Post Order Traversal

39

In Order : {4, 2, 5, 1, 6, 3, 7} and Post Order : {4, 5, 2, 6, 7, 3, 1}

School of Computer Engineering

Construction of Binary Tree from Pre Order and Post Order Traversal

40

Pre Order : PLR and Post Order : LRP

Pre Order : A → B
Post Order : B → A
Conclusion
❑ One cannot create an exact binary tree from preorder and postorder only as you
would never be able to estimate the left/right child of the tree.
❑ You need the inorder traversal along with the any of the above

P: Parent, L: Left and R: Right

School of Computer Engineering
Threaded Binary Tree
41

A threaded binary tree is a binary tree in which the nodes that don’t have a
right child, have a thread to their inorder successor. The idea of threaded
binary trees is to make inorder traversal faster and do it without stack and
without recursion.

Types of threaded binary trees:

❑ Single Threaded: each node is threaded towards either the in-order
predecessor or successor (left or right) means all right null pointers will point
to inorder successor OR all left null pointers will point to inorder predecessor.
❑ Double threaded: each node is threaded towards both the in-order
predecessor and successor (left and right) means all right null pointers will
point to inorder successor AND all left null pointers will point to inorder
predecessor.

School of Computer Engineering

Single & Double Threaded Binary Tree
42 In Order :- 1, 3, 5, 6, 7,8, 9,11, 13

Single Threaded Binary Tree Double Threaded Binary Tree

Node Structure :- Node Structure :-

struct node struct node
{ {
int data; int data;
struct node *leftChild; struct node *leftChild;
struct node *rightChild; struct node *rightChild;
struct node *thread; struct node *rthread, *lthread;
}; };

School of Computer Engineering

Binary Search Tree
43

A binary search tree (BST) is a tree in which all nodes follows the below mentioned
properties −

❑ The left sub-tree of a node has data less than to its parent node's data.
❑ The right sub-tree of a node has data greater than to its parent node's data.

Thus, a BST divides all its sub-trees into two segments; left sub-tree and right sub-tree and
can be defined as - left_subtree (data) < node (data) < right_subtree (data)

Example Quick Questions?

Question - Where is the smallest & largest element in
binary search tree resides?
Answer - Leftmost & Rightmost Positions

School of Computer Engineering

BST- Insertion
44

School of Computer Engineering

BST- Insertion Algorithm
45

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

School of Computer Engineering

BST- Search
46

Node with key value 7 to be searched

School of Computer Engineering

BST– Search Algorithm
47

if the tree is empty

return NULL

else if the key value in the node(root) equals the target

return the node value

else if the key value in the node is greater than the target
return the result of searching the left subtree

else if the key value in the node is smaller than the target
return the result of searching the right subtree
School of Computer Engineering
BST– Search - C Function
48

/* return a pointer to the node that contains key. If there is no such node, return NULL */
node* search(node * root, int key)
{
if (!root)
{
return NULL;
}

if (key == root->key)
{
return root;
}

if (key < root->key)

{
return search(root->left, key);
}

return search(root->right, key);

}
School of Computer Engineering
BST – Search Minimum and Maximum Key C Function
49

Minimum Maximum
Key searchMinimum(node * root)
node* Key searchMaximum(node * root)
node*
{ {
if (!root) if (!root)
{ {
return NULL; return NULL;
} }

while (root -> left != NULL) while (root -> right != NULL)
{ {
root = root -> left; root = root -> right;
} }

return root; return root;

} }

School of Computer Engineering

BST - Deletion
50
❑ Removing a node from a BST is a bit more complex, since any “holes” should not be created in the
tree. The intention is to remove the specified item from the BST and adjusts the tree.
❑ The binary search algorithm is used to locate the target item: starting at the root, it probes down
the tree till it finds the target or reaches a leaf node.

Experimenting the
❑cases
if the tree is empty return false
❑ else attempt to locate the node containing the target using the binary search
algorithm:
❑ if the target is not found return false
❑ else the target is found, then remove its node & return true. Now while
removing the node four cases may happen
❑ Case 1 - if the node has 2 empty subtrees
❑ Case 2 - if the node has a left and a right subtree
❑ Case 3 - if the node has no left child
❑ Case 4 - if the node has no right child

School of Computer Engineering

BST – Deletion – Case 1
51

Case 1: removing a node with 2 empty subtrees

Action: replace the link in the parent with null and delete the
node
Removing 4
Parent
7 7

Z
5 9 5 9

4 6 8 10 6 8 10

Z points to the node which is to be deleted from the tree

School of Computer Engineering
BST – Deletion – Case 2
52

Case 2: removing a node with 2 subtrees

Action: - replace the node's value with the max value in the
left subtree and delete the max node in the left subtree
Removing 7
Z
7 6
5 9 5 9

4 6 8 10 4 8 10

Z points to the node which is to be deleted from the tree

School of Computer Engineering
BST – Deletion – Case 3
53

Case 3: if the node has no left child

Action: link the parent of the node to the right node of
non-empty subtree and delete the node
Removing 5
Parent Parent

Z
7 7

5 9 6 9

6 8 10 8 10

Z points to the node which is to be deleted from the tree

School of Computer Engineering
BST – Deletion – Case 4
54

Case 4: if the node has no right child

Action: link the parent of the node to the left node of
non-empty subtree and delete the node
Removing 5
Parent Parent
Z
7 7

5 9 9
4
4 8 10 8 10

Z points to the node which is to be deleted from the tree

School of Computer Engineering
BST Deletion Pseudo code
55
void delete(node *root, key) void deleteNode(node *root)
{ {
IF (root->left == NULL AND root->right == NULL) //Case - 1
IF (root == NULL) THEN
free(root) [free is the C function to release the memory allotted to the node]
exit exit
END IF ENDIF

IF (root->left != NULL) THEN //Case – 4 and Case - 2

IF (root->data>key) THEN struct node *temp=root->left;
delete(root->left, key) WHILE(temp->right!=NULL)
ELSE IF (root->data<key) THEN temp=temp->right;
delete(root->right, key) ENDWHILE
ELSE root->data=temp->data;
free(temp)
deletenode(root)
ELSE //Case 3
ENDIF struct node *temp = root->right;
} WHILE(temp->left != NULL)
temp=temp->left;
ENDWHILE
root->data = temp->data;
free(temp);
ENDIF
}

School of Computer Engineering

BST C Implementation
56

School of Computer Engineering

Balanced Binary Tree
57

❑ The disadvantage of a binary search tree is that its height can be as

large as N-1 where N is the number of nodes. This means that the
time needed to perform insertion and deletion and many other
operations can be O(N) in the worst case.
1
❑ We want a tree with small height and this can be attained if both
2 subtrees of each node have roughly the same height. So goal is to
keep the height of a binary search tree O(log N). Such trees are
3 called balanced binary trees

4
4
5
2 6
6
7 1 3 5 7
School of Computer Engineering
How to check a Binary Tree is balanced or not?
58

A binary tree is called a balanced binary tree if it satisfies following conditions -

❑ If at any given node, absolute difference of height of left sub-tree and height of right
sub-tree (called as balance factor) is not greater than 1 (i.e. should be -1 or 1 or 0)

Balance Unbalance
d d

School of Computer Engineering

AVL Tree
59
What if the input to binary search tree comes in sorted (ascending or descending) manner? It will then look like
this −

It is observed that BST's worst-case performance closes to linear search algorithms, that is Ο(n). In real time
data we cannot predict data pattern and their frequencies. So a need arises to balance out existing BST. Named
after their inventor Adelson, Velski & Landis, AVL trees are height balancing binary search tree. AVL tree
checks the height of left and right sub-trees and assures that the difference is not more than 1. This difference is
called Balance Factor. Balance Factor = height(left-subtree) − height(right-subtree)

School of Computer Engineering

AVL Rotation Technique
60

If the difference in the height of left and right sub-trees is more than 1, the
tree is balanced using rotation techniques.

To make itself balanced, an AVL tree may perform four kinds of rotations −

❑ Left rotation
❑ Right rotation
❑ Left-Right rotation
❑ Right-Left rotation

First two rotations are single rotations and next two rotations are double
rotations.

School of Computer Engineering

AVL Tree Left Rotation
61

If a tree become unbalanced, when a node is inserted into the right subtree
of right subtree, then we perform single left rotation −

In the above example, node A has become unbalanced as a node is inserted

in right subtree of A's right subtree. We perform left rotation by making A
left-subtree of B.

School of Computer Engineering

AVL Tree Right Rotation
62

AVL tree may become unbalanced if a node is inserted in the left subtree of
left subtree. The tree then needs a right rotation.

As depicted, the unbalanced node becomes right child of its left child by
performing a right rotation.

School of Computer Engineering

AVL Tree Left-Right Rotation
63

Double rotations are slightly complex version of already explained versions

of rotations. A left-right rotation is combination of left rotation followed by
right rotation.
State Action

A node has been inserted into right subtree of left

subtree. This makes C an unbalanced node. These
scenarios cause AVL tree to perform left-right
rotation.
We first perform left rotation on left subtree of C.
This makes A, left subtree of B.

School of Computer Engineering

AVL Tree Left-Right Rotation cont…
64

State Action

Node C is still unbalanced but now, it is because of

left-subtree of left-subtree.

We shall now right-rotate the tree making B new

root node of this subtree. C now becomes right
subtree of its own left subtree.

The tree is now balanced.

School of Computer Engineering

AVL Tree Right-Left Rotation
65

A right-left rotation is combination of right rotation followed by left

rotation.
State Action

A node has been inserted into left subtree of right

subtree. This makes A an unbalanced node, with
balance factor 2.

First, we perform right rotation along C node,

making C the right subtree of its own left subtree B.
Now, B becomes right subtree of A.

School of Computer Engineering

AVL Tree Left-Right Rotation cont…
66

State Action

Node A is still unbalanced because of right subtree

of its right subtree and requires a left rotation.

A left rotation is performed by making B the new

root node of the subtree. A becomes left subtree of
its right subtree B.

The tree is now balanced.

School of Computer Engineering

AVL Tree Insertion and Deletion
67

Insertio Deletio
n n
❑ After inserting a node, check each ❑ If a node is a leaf, remove it.
of the node's ancestors for ❑ If the node is not a leaf, replace it
consistency with the AVL rules. with either the largest in its left
❑ For each node checked, if the subtree (i.e. the rightmost) or the
balance factor remains 1, 0, or -1 smallest in its right subtree (i.e.
then no rotations are necessary. the leftmost), and remove that
Otherwise, it's unbalanced. node.
❑ After each insertion, at most two ❑ After deletion, retrace the path
tree rotations are needed to from parent of the replacement to
restore the entire tree. the root, adjusting the balance
factors as needed.

School of Computer Engineering

AVL Tree Insertion Example
68

School of Computer Engineering

AVL Tree Deletion Example
69

t 3 th 2
e a wi
lanc tion
ba ota
Im R
orm
f
Per

Imbalance at 5
Perform Rotation with
8
School of Computer Engineering
AVL Tree Insertion and Deletion Simulation
70

https://www.cs.usfca.edu/~galles/visualization/AVLtree.htm
l

School of Computer Engineering

AVL Tree C Implementation
71

School of Computer Engineering

Multi-way Search Tree
72
❑ A binary search tree has one value in each node and two subtrees. This notion easily generalizes
to an M-way search tree, which has (M-1) values per node and M subtrees. M is called the
degree of the tree. A binary search tree, therefore, has degree 2.
❑ In fact, it is not necessary for every node to contain exactly (M-1) values and have exactly M
subtrees. In an M-way subtree a node can have anywhere from 1 to (M-1) values and the
number of (non-empty) subtrees can range from 0 (for a leaf) to 1+(the number of values). M is
thus a fixed upper limit on how much data can be stored in a node.
❑ The values/keys in a node are stored in ascending order, K 1 < K2 < ... Kk (k <= M-1) and all the
values in K1's left subtree are less than K1 ; all the keys in Kk's subtree are greater than Kk; and
all the values in the subtree between K(i) and K(i+1) are greater than K(i) and less than K(i+1).

School of Computer Engineering

3-way Search Tree Example
73

School of Computer Engineering

Search for X in m-way search tree
74

School of Computer Engineering

Searching an m-way Search Tree
75

Searching for a key in an m-way search tree is similar to that of binary search tree

School of Computer Engineering

Insert into m-way search tree
76
❑ The algorithm for binary search tree can be generalized
❑ Follow the search path and perform one of the following
❑ Add new key or value into the last leaf
❑ Add a new leaf if the last leaf is fully occupied Add 69
Add 52

52

School of Computer Engineering

Deletion from m-way search tree
77
Let K be the key to be deleted from the m-way search tree.

K : Key K
Ai , Aj : Pointers to sub-tree Ai Aj

Deletion Cases
[1] If (Ai = Aj = NULL) then delete K
[2] If (Ai ≠ NULL, Aj = NULL ) then choose the largest of the key elements K’ in
the child node pointed to by Ai and replace K by K’.
[3] If (Ai = NULL, Aj ≠ NULL ) then choose the smallest of the key element K”
from the subtree pointed to by Aj , delete K” and replace K by K”.
[4] If (Ai ≠ NULL, Aj ≠ NULL ) then choose the largest of the key elements K’ in
the subtree pointed to by Ai or the smallest of the key element K” from the
subtree pointed to by Aj to replace K.

School of Computer Engineering

Deletion Case - 1
78

Ai = Aj = NULL
Delete 151 18 44 76 198
X X

80 92 141 262
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X

272 286 350

Action : delete K X X X X

School of Computer Engineering

Deletion Case – 1 Result
79

Ai = Aj = NULL
18 44 76 198
Post to the
X X Deletion of 151

80 92 141 262
7 12
X X X
X X

77 148 172 186

8 10
X X X X X X
X X X

272 286 350

X X X X

School of Computer Engineering

Deletion Case - 2
80

Ai = NULL, Aj ≠ NULL
Delete 262 18 44 76 198
X X

80 92 141 262
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X

Action : choose the largest of the key elements K’ 272 286 350
in the child node pointed to by Ai and replace K X X X X
by K’.
School of Computer Engineering
Deletion Case – 2 Result
81

Ai = NULL, Aj ≠ NULL
18 44 76 198
Post to the
X X Deletion of 262

80 92 141 272
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X
286 350
X X X

School of Computer Engineering

Deletion Case - 3
82

Ai ≠ NULL, Aj = NULL
Delete 12 18 44 76 198
X X

80 92 141 262
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X

Action : choose the smallest of the key element K” 272 286 350
from the subtree pointed to by Aj , delete K” and X X X X
replace K by K”
School of Computer Engineering
Deletion Case – 3 Result
83

Ai ≠ NULL, Aj = NULL
18 44 76 198
Post to the
X X Deletion of 12

80 92 141 262
7 10
X X X
X X

77 148 151 172 186

8
X X X X X X X
X X
272 286 350
X X X X

School of Computer Engineering

Deletion Case - 4
84

Ai ≠ NULL, Aj ≠ NULL
Delete 198 18 44 76 198
X X

80 92 141 262
7 12
X X X
X X

77 148 151 172 186

8 10
X X X X X X X
X X X
Action : choose the largest of the key elements K’ in the 272 286 350
subtree pointed to by Ai or the smallest of the key X X X X
element K” from the subtree pointed to by Aj to
replace K.
School of Computer Engineering
Deletion Case – 4 Result
85

Ai ≠ NULL, Aj ≠ NULL
18 44 76 262
Post to the
X X Deletion of 198

80 92 141 272 286 350

7 10
X X X X X X
X X

77 148 151 172 186

8
X X X X X X X
X X

School of Computer Engineering

Forest
86

A Forest F defined to be an ordered collection of zero or more distinct general trees.

Example – E
B G

C D F H I

A forest can be converted to a general tree (or simply tree i.e. number of subtrees
for any node is not required to be 0, 1, or 2) by adding a single node to serve as the
root node of the tree in which each of the original trees are sub-tree. Example –

B E G

C D F H I
School of Computer Engineering
Forest cont…
87

Conversely, deleting the root from a tree leaves behind a forest consisting of its
subtrees. (Obviously, this is how we got our forest from our original tree.)

B E G

C D F H I

Can we provide or say, nodes with 1000 pointer fields in order to be able to represent
general trees where nodes might have up to 1000 children? In any given case, most of
the fields of all the node records will be unused, so a great deal of memory is required -
and wasted. And what if we want to introduce a node with 1001 children? We have to
reconfigure the implementation to accommodate this one "anomalous" node. Surely,
this is not satisfactory. Remarkably, a forest can be represented by a binary tree. Note
that the resulting tree is a binary tree but not a binary search tree. Obviously, an
empty forest can be represented by the empty binary tree.

School of Computer Engineering

Conversion of General Tree to Binary Tree
88

1. Root node of general tree becomes root node of Binary Tree.

2. Now consider N1, N2, N3 ... Nn are child nodes of the root node in general tree. The left
most child (N1) of the root node in general tree becomes left most child of root node
in the binary tree. Now Node N2 becomes right child of Node N1, Node N3 becomes
right child of Node N2 and so on in binary tree.
3. The same procedure of step 2 is repeated for each leftmost node in the general tree.

Exampl Step 1: Root Node of General tree becomes the Root node
e of binary tree.

Step 2: Now Root Node (A) has three child Nodes (B, H, E)
in general tree. The leftmost node (B) of the root node (A)
in the general tree becomes the left most node of the root
node (A) in binary tree.

School of Computer Engineering

Conversion of General Tree to Binary Tree Example
89

Step 3: Now Node H becomes the right node of B and Node E becomes the right node of
H.

Step 4: Now Node B has only one left child node, which is C in general tree. So Node C
becomes left child of Node B in binary tree.

School of Computer Engineering

Conversion of General Tree to Binary Tree Example
90

Step 5: Now Node E has two child nodes (F, G). The leftmost node (F) of the node (E) in
the general tree becomes the left most node of the node E in the binary tree.

School of Computer Engineering

Conversion of General Tree to Binary Tree Example
91

Step 6: Now Node G becomes right node of Node F in binary tree.

School of Computer Engineering

Class Work
92

Convert the following general tree to Binary Tree

School of Computer Engineering

B-Tree
93

M-way binary search trees have the advantage of having a node storing multiple values.
However it is essential that the height of the tree be kept as low as possible and
therefore their arises the need to maintain balanced m-way search trees. Such a balanced
m-way search tree is called B-tree.

A B-tree of order m, if non empty is an m-way search tree in which

❑ The root has at least two child nodes and at most m child nodes
❑ Internal nodes except the root have at least ⎡m/2⎤ child nodes and at most m child
nodes
❑ The number of keys in each internal node is one less than the number of child nodes
and these keys partition the keys in the subtrees of nodes in a manner similar to that
of m-way search trees
❑ All leaf nodes are on the same level

School of Computer Engineering

Example - B-Tree of order 5
94

48

56 64 85
31 45

46 47
X X X 87 88 100 112
10 18 21
X X X X X
X X X X
58 62
X X X 49 51 52
36 40 42 X X X X
X X X X 67 75
X X X

School of Computer Engineering

B-Tree Search
95

Searching for a key in a B-tree is similar to the one on an m-way search key. The number
of accesses depends on the height h of the B-Tree.
Class Work
Draw the path to search for the key:
❑ 9
❑ 20
❑ 53
❑ 21

School of Computer Engineering

B-Tree Insertion
96

1. B-tree starts with a single root node (which is also a leaf node) at level 0.
2. Once the root node is full with m – 1 search key values and when attempt is made to
insert another entry in the tree, the root node splits into two nodes at level 1.
3. Only the middle value is kept in the root node, and the rest of the values are split
evenly between the other two nodes. i.e. the first (m-1)/2 values goes to left, the last
(m-1)/2 values goes to right.
4. When a non-root node is full and a new entry is inserted into it, that node is split into
two nodes at the same level, and the middle entry is moved to the parent node along
with two pointers to the new split nodes.
5. If the parent node is full, it is also split.
6. Splitting can propagate all the way to the root node, creating a new level if the root is
split.

School of Computer Engineering

B-Tree Insertion Example
97

B-Tree where m =5

Insert 17

Add it to the middle leaf. No overflow, so we're done.

School of Computer Engineering

B-Tree Insertion Example
98

Insert 6
Add it to the leftmost leaf. That overflows, so we split it: Left = [ 2 3 ], Middle = 5, Right = [ 6 7 ]
Left and Right become nodes; Middle is added to the node above with Left and Right as its children. The
node above (the root in this small example) does not overflow, so we are done.

School of Computer Engineering

B-Tree Insertion Example
99

Insert 21
Add it to the middle leaf. That overflows, so we split it: Left = [ 17 21 ], Middle = 22, Right = [ 44 45 ]
Left and Right become nodes; Middle is added to the node above with Left and Right as its children. The
node above (the root node in this small example) does not overflow, so we are done.

School of Computer Engineering

B-Tree Insertion Example
100

Insert 67
Add it to the rightmost tree. That overflows, so we split it: Left = [ 55 66 ], Middle = 67, Right = [ 68 70 ]
Left and Right become nodes; Middle is added to the node above with Left and Right as its children.

School of Computer Engineering

B-Tree Insertion Example
101

But now the node above does overflow. So it is split in exactly the same manner: so we split it:
Left = [ 5 10 ], Middle = 22, Right = [ 50 67 ]
Left and Right become nodes; , the children of Middle. If this were not the root, Middle would be added to
the node above and the process repeated. If there is no node above, as in this example, a new root is created
with Middle as its only value.

School of Computer Engineering

B-Tree Deletion
102

Case # Instance Action

1 Delete a leaf key with no underflow Delete

2 Delete a non-leaf key with no underflow Delete and promote
3 Delete a leaf key with underflow and Delete and borrow
rich sibling
4 Delete a leaf key with underflow and Merge
poor sibling

School of Computer Engineering

Deletion of leaf key with no overflow
103

48

56 64 85
31 45
X X X X
X X X

Delete 85

48

56 64
31 45
X X X
X X X

School of Computer Engineering

Deletion of non-leaf key with no overflow
104

31 45 31 42

46 47 46 47

Delete 45
X X X 10 18 21 X X X
10 18 21
X X X X
X X X X

36 40 42
36 40
X X X X
X X X

Delete and Promote

❑ Pick the largest key i.e. 42 from the left subtree of the key 45
❑ Delete the key 45 from the root node
❑ Promote 42 to the parent node of 45
School of Computer Engineering
Deletion of leaf key with overflow and rich sibling
105
Rich– Giving a key without underflowing
31 45
31 42

46

Delete 46
10 18 21 X X 45
10 18 21
X X X X X X
X X X X
36 40
Rich sibling for the 36 40 42
node with key 46 X X42 X
X X X X

Delete and Borrow

❑ Delete key 46
❑ Borrow the largest key i.e. 42 from the rich sibling through parent and replace the
appropriate keys.
School of Computer Engineering
Deletion of leaf key with overflow and poor sibling
106
Poor – Giving a key with underflowing
31 45
31

46

Delete 46
10 18 21 X X
10 18 21 42 45
X X X X
X X X X X X42 X

Poor sibling for the 42

node with key 46
X X

Delete and Merge

❑ Delete key 46
❑ Merge by pulling the key from parent with the poor sibling

School of Computer Engineering

B-Tree C Implementation
107

School of Computer Engineering

B+ Tree
108

In a B+ tree, the internal nodes have no data – only the leaves do!
❑ Each internal node still has up-to M-1 keys
❑ Subtree between two keys x and y contain leaves with values v such that x ≤ v < y
❑ Leaf nodes have up-to L (i.e. data items in leaf) sorted keys
❑ From the root to the leaf all paths should be of same length
Properties:
❑ Root (Special Case)
❑ Has between 2 and M children
❑ Internal Nodes
❑ Store up-to M-1 keys
❑ Have between ⎡M/2⎤ and M children
❑ Leaf Nodes Red arrow represents data elements
Green rectangle represents the node with key
❑ Where data is stored and data elements

❑ All at the same depth

❑ Contain between ⎡L/2⎤ and L data items

School of Computer Engineering

B+ Tree Example
109

School of Computer Engineering

Assignments
110

❑ A binary tree has 9 nodes. The inorder and preorder traversal of T yields the
following sequence of node:
Inorder: E, A, C, K, F, H, D,B,G and Preorder: F, A, E, K, C, D, H, G, B
Draw the tree T
❑ Suppose T is a binary tree. Write a recursive & non-recursive algorithm to
find the number of leaf nodes, number of nodes and depth in T. Depth of T is
1 more than the maximum depths of the depths of the left and right subtrees
of T.
❑ Suppose T is a binary tree. Write a recursive & non-recursive algorithm to
find the height of T.
❑ Insert the following keys in the order to form the binary search tree
J, R, D, G, T, E, M, H, P, A, F, Q
❑ Insert the following keys in the order to form the binary search tree
50, 33, 44, 22, 77, 35, 60, 40
❑ Suppose a binary tree T is in memory. Write the pseudo code to delete all
terminals or leaf nodes in T
School of Computer Engineering
Assignments cont…
111

❑ Write a C function to copy the binary tree T to T’

❑ Suppose ROOTA points to a binary tree T1. Write the pseudo code which
makes a copy T2 of the tree T1 using ROOTB as pointer
❑ Write algorithm to insert and delete the nodes in B tree.
❑ Write a program to check whether the binary tree is a binary search tree
❑ Write the non-recursive function for inorder traversal, preorder traversal,
and postorder traversal of a binary tree.
❑ Write a function to display all the paths from root to leaf nodes in a binary
tree.
❑ Write a programme to insert a node into BST both in recursive and
non-recursive manner.
❑ Write a programme to display the nodes of a tree in level wise(first we need
to display 0th level node, then 1th level nodes and so on).
❑ Write a program to check whether a binary tree is an AVL tree.

School of Computer Engineering

112

School of Computer Engineering

Home Work
113

❑ Find out the inorder, preorder and postorder traversal of the following tree.

❑ Draw the internal memory representation using sequential and linked

representation
❑ The inorder and postorder traversals of a binary tree T yield the following
sequence of nodes: Inorder : ABCDEFGHI and Postorder: ACEDBHIGF. Find
out its Pre-order traversal sequence of the binary tree drawn.
❑ Design a linked data structure to represent the node of an m-way search
tree. Write functions SEARCH_MWAY, INSERT_MWAY, DELETE_MWAY to
perform search, insert and delete operations on an m-way search tree.
❑ Implement the function DELETE_AVL which delete a given element ITEM
from the AVL Search tree T.
School of Computer Engineering
Home Work cont…
114

❑ Draw a complete binary tree with exactly six nodes. Put a different value in
each node. Then draw an array with six components and show where each of
the six node values would be placed in the array (using the usual array
representation of a complete binary tree).
❑ Draw a binary taxonomy tree that can be used for these four animals: Rabbit,
Horse, Whale, Snake. A binary taxonomy tree is also called as binary decision
tree that allows to going down the tree with simple test.

Are you a mammal?

Ye No
s
Are you bigger than a cat Do you live underwater?

Ye No Ye No
s s
Kangaroo Mouse Trout Robin

School of Computer Engineering

Home Work cont…
115

❑ Draw the binary tree for expression: A *B – (C + D) * (P/Q)

❑ For the following sequence, draw a B-tree of order 3 by inserting the data
91, 24, 6, 7, 11, 8, 21, 4, 5, 16, 19, 20, 76
❑ How many different trees are possible with n nodes?
❑ Draw a full binary tree with at least 6 nodes.
❑ Suppose that a binary search tree contains the number 42 at a node with two
children. Write two or three clear sentences to describe the process required
to delete the 42 from the tree.
❑ Suppose that we want to create a binary search tree where each node
contains information of some data type. What additional factor is required
for the data type?
❑ The maximum number of nodes on level i of a binary tree is ?
❑ The maximum number of nodes in a binary tree of depth d is ?
❑ Write a C function swapTree that takes a binary tree root node and swaps
the left and right children of every node.

School of Computer Engineering

Home Work cont…
116

❑ Write a function that traverses a threaded binary tree in postorder. What are
the time and space requirement of your method?
❑ Write a function that traverses a threaded binary tree in preorder. What are
the time and space requirement of your method?
❑ Write pseudo code to delete the node with key k from a binary search tree.
❑ Assume that a binary search tree is represented as a threaded binary search
tree. Write functions to search, insert and delete
❑ Write an algorithm to construct the binary tree with given preorder and
inorder.
❑ Write the pseudo code to construct the binary tree with given postorder and
inorder.
❑ Prove that every binary tree is uniquely by its preorder and inorder
sequences.
❑ Please provide constructive suggestions to this course in terms of lectures,
home works, or any other aspects

School of Computer Engineering

Supplementary Reading
117

❑ http://www.geeksforgeeks.org/binary-tree-data-structure/
❑ http://www.geeksforgeeks.org/binary-search-tree-data-structure/
❑ https://www.tutorialspoint.com/data_structures_algorithms/tree_data_structure.htm
❑ http://btechsmartclass.com/DS/U3_T1.html
❑ http://btechsmartclass.com/DS/U3_T3.html
❑ https://www.hackerrank.com/domains/data-structures/trees
❑ https://www.youtube.com/watch?v=qH6yxkw0u78
❑ http://nptel.ac.in/courses/106102064/6

School of Computer Engineering

 FAQ
118

Describe Trees with an example.

Tree is a structure that is similar to linked list. A tree will have two nodes that point to the left part of
the tree and the right part of the tree. These two nodes must be of the similar type.
The following code snippet describes the declaration of trees. The advantage of trees is that the data
is placed in nodes in sorted order.
struct TreeNode
{
int item; // The data in this node.
TreeNode *left; // Pointer to the left subtree.
TreeNode *right; // Pointer to the right subtree.
}

What is binary tree?

A binary tree is a tree structure, in which each node has only two child nodes. The first node is
known as root node. The parent has two nodes namely left child and right child.
Uses of binary tree:
❑ To create sorting routine.
❑ Persisting data items for the purpose of fast lookup later.
❑ For inserting a new item faster

School of Computer Engineering

FAQ cont…
119

What is a B tree?
A B-tree of order m (the maximum number of children for each node) is a tree which
satisfies the following properties :

1. Every node has <= m children.

2. Every node (except root and leaves) has >= m/2 children.
3. The root has at least 2 children.
4. All leaves appear in the same level, and carry no information.
5. A non-leaf node with k children contains k – 1 keys

What are threaded binary trees?

In a threaded binary tree, if a node 'A' has a right child 'B' then B's left pointer must be
either a child, or a thread back to A.
In the case of a left child, that left child must also have a left child or a thread back to A,
and so we can follow B's left children until we find a thread, pointing back to A.
This data structure is useful when stack memory is less and using this tree the treversal
around the tree becomes faster.

School of Computer Engineering

 FAQ
120

What are Infix, prefix, Postfix notations?

❑ Infix notation: X + Y – Operators are written in-between their operands. This is the
usual way we write expressions. An expression such as A * ( B + C ) / D
❑ Postfix notation (also known as “Reverse Polish notation”): X Y + Operators are
written after their operands. The infix expression given above is equivalent to A B C + *
D/
❑ Prefix notation (also known as “Polish notation”): + X Y Operators are written before
their operands. The expressions given above are equivalent to / * A + B C D

What is a B+ tree?
It is a dynamic, multilevel index, with maximum and minimum bounds on the number of
keys in each index segment. all records are stored at the lowest level of the tree; only keys
are stored in interior blocks.

School of Computer Engineering

 Data Structures and Algorithms (CS-2001)

KALINGA INSTITUTE OF INDUSTRIAL

TECHNOLOGY

School of Computer Engineering

Strictly for internal circulation (within KIIT) and reference only. Not for outside circulation without permission

4 Credit Lecture Note

 Chapter Contents
2

Sr # Major and Detailed Coverage Area Hrs

3 Stacks and Queues 8

Stacks, Stacks using Dynamic Arrays and
Linked Lists, Queues, Queue using Linked List,
Circular Queues using Dynamic Arrays,
Evaluation of Expressions, Priority Queue,
Dequeue

School of Computer Engineering

Introduction
3

The linear lists and linear arrays allowed one to

insert and delete elements at any place in the list – at
the beginning, at the end or in the middle. There are
certain frequent situations when one wants to
restrict insertions and deletions so that they can take
place only at the beginning or the end of the list, not
in the middle. Two of the data structures that are
useful in such situations are stacks and queues.

School of Computer Engineering

Stack
4

 A stack is a data structure that

works on the principle of Last In
First Out (LIFO).
 Last item put on the stack is the
first item that can be taken off.
 New elements are added to and
removed from the top called the
top of the stack.

Stack operations may involve initializing the stack, using it and then de-initializing it.
Apart from these basic stuffs, a stack is used for the following two primary operations −
 push − pushing (storing) an element on the stack.
 pop − removing (deleting) an element from the stack.

School of Computer Engineering

Stack Application
5

 Parsing
 Recursive Function
 Function Call
 Expression Evaluation Expression Representation
 Expression Conversion Sr# Expression Meaning
 Infix to Postfix 1 Infix Characterized by the placement of operators
 Infix to Prefix between operands. E.g. plus sign in "2 + 2"

 Postfix to Infix 2 Prefix Characterized by the placement of operators

before operands. E.g. plus sign in “+ 2 2"
 Prefix to Infix
3 Postfix Characterized by the placement of operators
 Towers of Hanoi after operands. E.g. plus sign in “ 2 2 +"

School of Computer Engineering

Stack Representation
6

Stack can be represented using −

 Arrays − Storing the items contiguously

 Fixed size (Called as Static Stack)
 Dynamic size (Called as Dynamic Stack)

 Linked List − Storing items non-contiguously

 Dynamic size (Called as Dynamic Stack)

School of Computer Engineering

Stack - Static Array Representation
7

Static Array Declaration & Definition:

DEFINE N NUM [NUM represents whole number e.g. In C, equivalent statement is #define N 100]
INTEGER STACK[N]
INTEGER TOP = 0
Pictorial Representation

1 5 4
Position 1 2 3 4 5 6 7 8

TOP 3
TOP = 0 indicates that the stack is empty and TOP = N indicates that the stack is full

School of Computer Engineering

Stack Operation using Static Array
8

PUSH(STACK, TOP, N, ITEM) POP(STACK, TOP, ITEM)

1. Start 1. Start
2. IF TOP = N THEN 2. IF TOP = 0 THEN
DISPLAY Overflow DISPLAY Underflow
EXIT EXIT
END IF END IF
3. TOP = TOP + 1 3. SET ITEM = STACK[TOP] [Call by reference]
4. STACK[TOP] = ITEM [Insert Item into new TOP Position] 4. TOP = TOP -1
5. Stop 5. Stop

PEEK(STACK, TOP, ITEM) Operation Description

1. Start  push − pushing (storing) an element on the
2. IF TOP = 0 THEN stack.
DISPLAY Underflow
 pop − removing (deleting) an element from the
EXIT
stack
END IF
 Peek - get the top data element of the stack,
3. SET ITEM = STACK[TOP] [Call by reference]
4. Stop without removing it.

School of Computer Engineering

Class Work
9

1. Design a Push algorithm using dynamic array

2. Design a Pop algorithm using dynamic array
3. Design an algorithm to realize two stacks in single static array
4. Design an recursive algorithm to reverse the stack

School of Computer Engineering

Stack - Linked List Representation
10

Since all the action happens at the top of the stack, a single linked list is a fine way to
represent the stack wherein the header/start always points to the top of the stack.

CC BB AA X
Represents Top
 Pushing is inserting an element at the front of the list
 Popping is removing an element from the front of the list
Push Before Push

CC BB AA X
After Push

DD CC BB AA X
School of Computer Engineering
Stack - Linked List Representation
11

Pop Before Pop

DD CC BB AA X
After Pop

CC BB AA X
Stack Node Representation

struct node
{
int info;
struct node *next; N represents NULL

}*top;

School of Computer Engineering

Push Function
12

void push()
{
int data; Top
scanf(“%d”, &data); Top
if (top == NULL)
{
top =(struct node *)malloc(*sizeof(struct node));
C
top->next = NULL; B
top->info = data; C B
} A X PUSH
else
{ X represents NULL A X

struct node * temp =(struct node *)malloc(*sizeof(struct node));

temp->next = top;
temp->info = data;
top = temp;
}

School of Computer Engineering

Pop Function
13

void pop()
{
struct node *tempTop = top;
Top
if (tempTop == NULL) Top
{
printf("\n Error "); C
return;
B
} B POP
else
tempTop = tempTop ->next; A X
A X

printf("\n Popped value : %d", top->info); X represents NULL

free(top);
top = tempTop;

School of Computer Engineering

Arithmetic Expression : Polish Notation
14
The way to write arithmetic expression is known as a notation. Polish Notation
is a way of expressing arithmetic expressions that avoids the use of brackets
to define priorities for evaluation of operators. Polish Notation was devised by
the Polish philosopher and mathematician Jan Łukasiewicz (1878-1956) for use
in symbolic logic.
 Evaluate the following parenthesis-free arithmetic expression
2 î 3 + 5 * 2 î 2 – 12 / 6
= 8 + 5 * 4 – 12 / 6 = 8 + 20 – 2 = 26
An arithmetic expression can be written in three different but equivalent
notations, i.e., without changing the essence or output of an expression. These
notations are −
 Infix Notation  Postfix Notation
 Prefix Notation

School of Computer Engineering

Expression Representation
15

 Infix Notation - We write expression in infix notation, e.g. a - b + c, where

operators are used in-between operands. It is easy for us humans to read,
write, and speak in infix notation but the same does not go well with
computing devices. An algorithm to process infix notation could be
difficult and costly in terms of time and space consumption.
 Prefix Notation - In this notation, operator is prefixed to operands, i.e.
operator is written ahead of operands. For example, +ab. This is
equivalent to its infix notation a + b. Prefix notation is also known as
Polish Notation.
 Postfix Notation - This notation style is known as Reversed Polish
Notation. In this notation style, the operator is postfixed to the operands
i.e., the operator is written after the operands. For example, ab+. This is
equivalent to its infix notation a + b.
School of Computer Engineering
Difference in 3 Notation
16

Example

Sr# Infix Prefix Postfix

1 a+b +ab ab+
2 (a + b) ∗ c ∗+abc ab+c∗
3 a ∗ (b + c) ∗a+bc abc+∗
4 a/b+c/d +/ab/cd ab/cd/+
5 (a + b) ∗ (c + d) ∗+ab+cd ab+cd+∗
6 ((a + b) ∗ c) - d -∗+abcd ab+c∗d-

School of Computer Engineering

Parsing Expression
17

Parsing is the process of analyzing a collection of symbols, either in natural language or in

computer languages, conforming to the rules of a formal grammar.
It is not a very efficient way to design an algorithm or program to parse infix notations.
Instead, these infix notations are first converted into either postfix or prefix notations
and then computed. To parse any arithmetic expression, we need to take care of operator
precedence and associativity also.
Precedence :- When an operand is in between two different operators, which operator
will take the operand first, is decided by the precedence of an operator over others. For
example − a + b *c  a + (b * c)
Associativity :- It describes the rule where operators with the same precedence appear
in an expression. For example, in expression a + b − c, both + and – have the same
precedence, then which part of the expression will be evaluated first, is determined by
associativity of those operators. Here, both + and − are left associative, so the expression
will be evaluated as (a + b) − c.

School of Computer Engineering

Parsing Expression cont…
18

Precedence and associativity determines the order of evaluation of an expression.

Following is an operator precedence and associativity table (highest to lowest) −

Sr# Operator Precedence Associativity

1 Exponentiation (^ or î) Highest Right Associative
2 Multiplication ( ∗ ), Division ( / ) and Second Highest Left Associative
Modular Division ( % )
3 Addition ( + ) & Subtraction ( − ) Lowest Left Associative

The above table shows the default behavior of operators. At any point of time in
expression evaluation, the order can be altered by using parenthesis.
For example − In a + b*c, the expression part b*c will be evaluated first, with
multiplication as precedence over addition. We here use parenthesis for a + b to be
evaluated first, like (a + b)*c.

School of Computer Engineering

Arithmetic Expression Conversion
19

Infix expression to Prefix notation

(A+B)*C = [+AB]*C = *+ABC where [ ] indicates a partial translation
A+(B*C) = A+[*BC] = +A*BC
(A+B)/(C-D) = [+AB]/[-CD] = /+AB-CD
Infix expression to Postfix notation
(A+B)*C = [AB+]*C = AB+C* where [ ] indicates a partial translation
A+(B*C) = A+[BC*] = ABC*+
(A+B)/(C-D) = [AB+]/[CD-] = AB+CD-/
Note
Order in which the operations are to be performed is completely determined by the
positions of the operators and operand in the expression. Accordingly, one never
needs parenthesis when writing expression in Polish notations

School of Computer Engineering

Why Postfix and Prefix?
20

Postfix:
Computer usually evaluates an arithmetic expression written in infix notation in
two steps:
 1st Step - Converts the infix notation to Postfix notation
 2nd Step - Evaluates the Postfix expression.
In each step, stack is the main tool used to accomplish the given task.

Prefix:
 Has seen wide application in Lisp (programming language) s-expressions
 Data Compression with Prefix Encoding
 Standard scientific prefixes are used to denote powers of 10 e.g. kilo = 1e3
 mega = 1e6  tera = 1e12  exa = 1e18
 giga = 1e9  peta = 1e15

School of Computer Engineering

Evaluation of a Postfix Expression
21

1. Start
2. Validate the Postfix expression for correctness
a) ‘(‘ and ‘)’ are in pairs
b) Operator is after the operands [Binary operators are considered only]
3. Add a right parenthesis ‘)” at the end of P. [This act as delimiter]
4. Scan P from left to right and repeat steps 5 and 6 for each element of P until the
delimiter “)” is encountered
5. If an operand is encountered, put it on STACK
6. If an operator is encountered, then
(a) Remove the two top elements of STACK, where A is the top element and B is the
next-to-top element
(b) Evaluate B A
(c ) Place the result of step (b) on STACK
7. Set value of the postfix expression equal to the top element of STACK
8. Stop
School of Computer Engineering
Example
22

 P = 5, 6, 2, + , *, 12, 4, /, - [Postfix]
Note – Commas are used to separate the elements of P so that 5,6,2 is not interpreted as 562.

P: (after adding a sentinel right parenthesis at the end of P)

5 6 2 + * 12 4 / - )
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10)
Symbol Scanned STACK Symbol Scanned STACK
(1) 5 5 (7) 4 40 12 4
(2) 6 5 6 (8) / 40 3
(3) 2 5 6 2 (9) - 37
(4) + 5 8 (10) )
(5) * 40
(6) 12 40 12

Q = 5 * ( 6 + 2) – 12 / 4 is the equivalant Infix expression

School of Computer Engineering
Class Work
23

Consider the following arithmetic expression P, written in postfix notation:

P =12, 7 , 3, - , / , 2, 1, 5, +, *, +

1. Evaluate the above postfix expression

2. By inspection, translate P into its equivalent infix expression
3. Evaluate the converted infix expression

Q = 12 / (7-3) + 2 * (1+5) = 15

School of Computer Engineering

Evaluation of a Prefix Expression
24

1. Start
2. Validate the Prefix Expression for correctness
a) ‘(‘ and ‘)’ are in pairs
b) Operator is before the operands [Binary operators are considered only]
3. Scan P from right to left and repeat steps 5 and 6 for each element of P until it ends.
4. If an operand is encountered, put it on STACK
5. If an operator is encountered, then
(a) Remove the two top elements of STACK, where A is the top element and B is the
next-to-top element
(b) Evaluate A B
(c ) Place the result of step (b) on STACK
6. Set value of the prefix expression equal to the top element of STACK
7. Stop

School of Computer Engineering

Example
25

P = -, *, +, 4, 3, 2, 5 [Prefix]
Note – Commas are used to separate the elements of P
- * + 4 3 2 5
(7) (6) (5) (4) (3) (2) (1)

Symbol scanned STACK

(1) 5 5
(2) 2 5 2
(3) 3 5 2 3
(4) 4 5 2 3 4
(5) + 5 2 7
(6) * 5 14
(7) - 9

School of Computer Engineering

Infix to Postfix Conversion
26
Q is an arithmetic expression written in infix notation. This algorithm InfixToPostfix (Q, P) finds the equivalent
postfix notation where P is the equivalent postfix notation –
1. Start
2. Validate the Infix expression for correctness
a) ‘(‘ and ‘)’ are in pairs
b) Operator is between the operands [Binary operators are considered only]
3. Push “(“ onto STACK and “)” to the end of Q
4. Scan Q from Left to Right and Repeat Steps 5 to 8 for each element of Q until the STACK is empty
5. If an operand is encountered, add it to P
6. If a left parenthesis is encountered, push it onto STACK
7. If an operator is encountered, then:
(a) Repeatedly pop from STACK and add to P each operator which has same precedence or higher precedence
than .
(b) Add to STACK.
8. If a right parenthesis is encountered, then
(a) Repeatedly pop from the STACK and add to P each operator until a left parenthesis is encountered.
(b) Remove the left parenthesis. [Do not add it to P]
9. Stop

School of Computer Engineering

Example
27

Q:A+(B*C–(D/E îF)*G)*H
So first, we push “(“ onto stack, and then add “)” to the end of the Q to obtain:

A + ( B * C - ( D / E î F ) * G ) * H )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Symbol Scanned STACK Expression P

1 A ( A
2 + (+ A
3 ( (+( A
4 B (+( AB
5 * (+(* AB
6 C (+(* ABC
7 - (+(- ABC*

School of Computer Engineering

Example cont…
28

A + ( B * C - ( D / E î F ) * G ) * H )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Symbol Scanned STACK Expression P

8 ( (+(-( ABC*
9 D (+(-( ABC*D
10 / (+(-(/ ABC*D
11 E (+(-(/ ABC*DE
12 î (+(-(/î ABC*DE
13 F (+(-(/î ABC*DEF
14 ) (+(- ABC*DEFî/
15 * (+(-* ABC*DEFî/
16 G (+(-* A B C * D E F î /G
17 ) (+ ABC*DEFî/G*-
18 * (+* ABC*DEFî/G*-
19 H (+* ABC*DEFî/G*-H
20 ) ABC*DEFî/G*-H*+

School of Computer Engineering

Class Work
29

Consider the infix expression Q: ((A + B) * D) î (E-F). Translate Q into its equivalent
postfix expression P
Symbol Scanned STACK Expression P
1 ( ((
2 ( (((
3 A ((( A
4 + (((+ A
5 B (((+ AB
6 ) (( AB +
7 * ((* AB +
8 D ((* AB +D
9 ) ( AB +D*
10 î (î AB +D*
11 ( (î( AB+D*
12 E (î( AB+D*E
13 - (î(- AB+D*E F
14 F (î(- AB+D*E F
15 ) (î AB+D*E F–
16 AB+D*E F–î

School of Computer Engineering

Infix to Prefix Conversion
30
Q is an arithmetic expression written in infix notation. This algorithm InfixToPrefix(Q, P) finds the
equivalent postfix notation where P is the equivalent prefix notation –
1. Start
2. Validate the Infix expression for correctness
a) ‘(‘ and ‘)’ are in pairs
b) Operator is between the operands [Binary operators are considered only]
3. Reverse the expression
4. CALL InfixToPostfix (Q, P)
5. Reverse the expression
6. Stop

Example: Infix notation: A+B*C

Step 1 – Infix expression is correct
Step 2 – Reversing the expression resulting to C*B+A
Step 3 – Postfix expression produced in step 2 is CB*A+
Step 4 – Reversing the expression produced in step 3 is + A * B C
Result: + A * B C

School of Computer Engineering

Example cont…
31

Q : (A+B î C)*D+E î F
Step 1 – Infix expression is correct
Step 2 –
a) Reversing the expression produce F î E + D * ) C î B + A (
b) Reverse the bracket, so making every '(' as ')' and every ')' as '(‘
revised expression is F î E + D * ( C î B + A )
Step 3 – Postfix expression of step 2 produce F E î D C B î A + * +
Step 4 – Reversing the expression produced in step 3 becomes
+ *+AîBCDî E5
Result: + * + A î B C D î E 5

School of Computer Engineering

Home Work
32

Read the following at your own pace:

 Postfix to Infix conversion –
http://scanftree.com/Data_Structure/postfix-to-infix

 Prefix to Infix conversion –

http://scanftree.com/Data_Structure/prefix-to-infix

 Postfix to Prefix conversion –

http://see-programming.blogspot.in/2013/05/postfix-to-prefix-conversion.html

 Postfix to Prefix conversion –

http://www.manojagarwal.co.in/conversion-from-prefix-to-postfix/

School of Computer Engineering

Queue
33

 A queue is a data structure that models/enforces the first-come first-serve order, or

equivalently the first-in first-out (FIFO) order.
 The element that is inserted first into the queue will be the element that will
deleted first, and the element that is inserted last is deleted last.
 Items are inserted one end (rear end) and deleted from the other end(front end).

Queue basic operations are −

 enqueue− insert element at rear
 dequeue− Remove element from front
 peek − Examine the element at front without removing it from queue

School of Computer Engineering

Queue Application
34

Operating System
 queue of print jobs to send to the printer
 queue of programs / processes to be run
 queue of network data packets to send

Programming
 modeling a line of customers or clients
 storing a queue of computations to be performed in order

Real World
 people on an escalator or waiting in a line
 cars at a gas station (or on an assembly line)

School of Computer Engineering

Queue Representation
35

Queue can be represented using −

 Static Arrays − Storing the items contiguously

 Static Queue due to fixed size
 Space is wasted if we use less elements
 cannot insert more elements than the array can hold

 Dynamic Arrays − Storing the items contiguously

 Dynamic Queue

 Linked List− Storing items non-contiguously

 Dynamic Queue

School of Computer Engineering

Queue - Static Array Representation
36

Static Array Declaration & Definition:

DEFINE N NUM [NUM represents whole number e.g. In C, equivalent statement is #define N 100]
INTEGER QUEUE[N]
INTEGER REAR = 0
INTEGER FRONT = 0
Pictorial Representation 1 FRONT 3 REAR

4 8 6
Position 1 2 3 4 5 6 7 8
Keeps track of the number of items in the queue and the position of the front element
(at the front of the queue), the rear element (at the rear). The position of the front
element is stored in the front member variable. The next item is after the first one and
so on until the rear of the queue that occurs at the index stored in a member variable
called rear.
FRONT = 0 and REAR = 0 indicates that the queue is empty and REAR = N indicates that the
queue is full
School of Computer Engineering
Enqueue Operation
37

1 2 3 4 5 6 ... FRONT
0
0 REAR

Let’s an element enters the queue…

1 2 3 4 5 6 ...
1 FRONT
7 1 REAR
After a series of insertion, the state of the queue is
1 2 3 4 5 6 ...
1 FRONT
7 2 10 12 4 REAR

School of Computer Engineering

Enqueue Algorithm
38

SQINSERT(QUEUE, N, FRONT, REAR, ITEM)

1. Start
2. IF (REAR = N) THEN
DISPLAY “OVERFLOW”
EXIT
END IF
3. IF (FRONT = 0 AND REAR = 0) THEN [Queue initially empty]
FRONT = 1
REAR = 1
ELSE
REAR = REAR + 1
END IF
4. QUEUE[REAR] = ITEM [This inserts new element]
5. Stop

School of Computer Engineering

Dequeue Operation
39

1 2 3 4 5 6 ...
1 FRONT
4 8 6
3 REAR
Let’s an element leaves the queue
1 2 3 4 5 6 ...
2 FRONT
4 8 6
3 REAR

After a series of deletion , the state of the queue is

1 2 3 4 5 6
3 FRONT
6
3 REAR

School of Computer Engineering

Dequeue Algorithm
40

ITEM SQDELETE(QUEUE, FRONT, REAR)

1. Start
2. IF FRONT = 0 THEN
DISPLAY “UNDERFLOW“
EXIT
END IF
3. ITEM = QUEUE[FRONT]
4. IF (FRONT == REAR) THEN [Check if only one element is left]
FRONT = 1
REAR = 1
ELSE
FRONT = FRONT + 1 [Increment FRONT by 1]
END IF
5. RETURN ITEM
6. Stop
School of Computer Engineering
Queue Linked Representation
41

Nodes connected in a chain by links

Node Representation
struct node
{
char info[50];
struct node *next;
}*front, *rear;
School of Computer Engineering
Enqueue Operation
42

Post Insertion

School of Computer Engineering

Enqueue Algorithm
43

LLQINSERT(struct node * FRONT, struct node * REAR, ITEM)

BEGIN
struct list* node= (struct node*)malloc(sizeof(struct node));
node->info = ITEM;
node -> next = NULL;
IF (FRONT ==NULL) THEN
FRONT = node
REAR = node
ELSE
REAR ->next = node
REAR = node
END IF
END
School of Computer Engineering
Dequeue Operation
44

Post Deletion

School of Computer Engineering

Dequeue Algorithm
45

ITEM LLQDELETE(struct node * FRONT)

BEGIN
IF (FRONT = NULL) THEN
DISPLAY “Queue Underflow"
EXIT
END IF
struct * node temp = FRONT
ITEM = temp->info
FRONT = FRONT->next
FREE(temp)
RETURN ITEM
END
School of Computer Engineering
Class Work
46

1. Design a Deque algorithm using dynamic array

2. Design an Enqueue algorithm using dynamic array

School of Computer Engineering

Linear Queue Drawback
47

Once the linear queue is full, even though few elements from the front are deleted & some
occupied space is relieved, it is not possible to add anymore new elements, as the rear has
already reached the queue’s rear most position.

Delete 3 elements

This situation also says that queue is full and we can not insert the new
element because, 'rear' is still at last position. In above situation, even
though we have empty positions in the queue we can not make use of them
to insert new element. This is the major problem in normal queue data
structure. To overcome this problem we use circular queue data structure.

School of Computer Engineering

Circular Queue
48

Circular Queue is a linear data structure in which the operations are performed based on
FIFO (First In First Out) principle and the last position is connected back to the first
position to make a circle and the graphical representation of a circular queue is as
follows...

In circular queue, once the Queue is full the "First" element

of the Queue becomes the "Rear" most element, if and only
if the "Front" has moved forward. otherwise it will again be
a "Queue overflow" state.

School of Computer Engineering

Circular Queue Enqueue Algorithm
49

CQINSERT(QUEUE, N, FRONT, REAR, ITEM)

1. Start
2. IF (FRONT = 0 AND REAR = 0) THEN
FRONT = 1
GOTO STEP 5
END IF
3. IF (FRONT =1 AND REAR = N) OR (FRONT = REAR + 1) THEN
DISPLAY “Circular Queue Overflow”
EXIT
END IF
4. IF (REAR = N) THEN
REAR = 1
GOTO STEP 6
END IF
5. REAR = REAR + 1
6. QUEUE [REAR] = ITEM
7. Stop
School of Computer Engineering
Circular Queue Dequeue Algorithm
50

ITEM CQDELETE(QUEUE, N, FRONT, REAR)

1. Start
2. IF (FRONT = 0) THEN [Continuation of algorithm]
DISPLAY “Circular Queue Underflow” 5. IF (FRONT = REAR) THEN
EXIT FRONT = 0
END IF REAR = 0
3. ITEM = QUEUE[FRONT] RETURN ITEM
4. IF FRONT = N THEN END IF
FRONT = 1 6. FRONT = FRONT + 1
RETRUN ITEM 7. RETURN ITEM
END IF 8. Stop

School of Computer Engineering

Circular Queue Example
51

1. Initially, Rear = 0, Front = 0. 3. Insert 50, Rear = 2, Front = 1.

Front Rear

2. Insert 10, Rear = 1, Front = 1. 4. Insert 20, Rear = 3, Front = 0.

Rear Front
Front

Rear

School of Computer Engineering

Circular Queue Example cont…
52

5. Insert 70, Rear = 4, Front = 1. 7. Insert 100, Rear = 5, Front = 2.

Front
Front

Rear
Rear

6. Delete front, Rear = 4, Front = 2. 8. Insert 40, Rear = 1, Front = 2.

Front
Rear Front

Rear

School of Computer Engineering

Class Work - Circular Queue
53

1. Design an Enqueue algorithm using dynamic array

2. Design a Dequeue algorithm using dynamic array
3. Design an Enqueue algorithm using Linked List
4. Design a Dequeue algorithm using Linked List

School of Computer Engineering

Deques
54

 A deque is a double-ended queue

 Insertions and deletions can occur at either
end, but not in the middle
 Implementation is similar to that for queues
 Deques are not heavily used
 You should know what a deque is, but we
won’t explore them much further
 There are 2 types of deque as explain below -

Input-restricted Deque Output-restricted Deque

 Elements can be inserted only at one  Elements can be removed only at one
end. end.
 Elements can be removed from both  Elements can be inserted from both the
the ends ends.

School of Computer Engineering

Deques Construction
55

The Dequeue can be constructed in two ways and are:

1) Using Array 2) Using Linked List
Static Arrays: FRONT is initialized to 0, REAR is initialized to N where N
represents array length
ENQUE_FRONT(QUEUE, FRONT, REAR, ITEM) ENQUE_REAR(QUEUE, FRONT, REAR, ITEM)

1. Start 1. Start
2. IF (FRONT = REAR) [QUEUE is Full] 2. IF (REAR = FRONT) [QUEUE is Full]
Display “Over flow” Display “Over flow”
EXIT EXIT
END IF END IF
3. FRONT = FRONT + 1 3. QUEUE[REAR] = ITEM
4. QUEUE[FRONT] = ITEM 4. REAR = REAR - 1
5. Stop 5. Stop

School of Computer Engineering

Deques Construction cont…
56

ITEM DEQUE_FRONT(QUEUE, FRONT, REAR) ITEM DEQUE_REAR(QUEUE, N, FRONT, REAR)

1. Start 1. Start
2. IF (FRONT = 0) [QUEUE is Empty] 2. IF (REAR = N) [QUEUE is Empty]
DISPLAY “Under flow” DISPLAY“Under flow”
EXIT EXIT
END IF END IF
3. ITEM = QUEUE[FRONT] 4. ITEM = QUEUE[REAR]
4. FRONT = FRONT - 1 5. REAR = REAR + 1
5. RETURN ITEM 6. RETURN ITEM
6. Stop 7. Stop

School of Computer Engineering

Class Work - Deques
57

1. Design an Enqueue algorithm using dynamic array

2. Design a Dequeue algorithm using dynamic array
3. Design an Enqueue algorithm for using Linked List
4. Design a Dequeue algorithm using Linked List

School of Computer Engineering

Priority Queues
58

A priority queue is a collection of elements such that each element has been
assigned a priority and such that the order in which elements are deleted and
processed comes from the following rules –

 An element of higher priority is processed before any element of lower

priority
 Two elements with the priority are processed according to the order in which
they were added to the queue.

Maintaining priority queues are –

 One-Way List
 Array

School of Computer Engineering

Priority Queue - One-Way List Representation
59

 Each node in the list will contain three items of information: an information
field INFO, a priority number PRN and a link number LINK.

 A node X precedes a node Y in the list when:

 X has higher priority than Y or
 When both have the same priority but X was added to the list before Y.

Systematic diagram

Head
A1 B2 C2 D3

School of Computer Engineering

Priority Queue - One-Way List Representation
60

Node Representation Deletion

struct node 1. Start
{ 2. Visit to the second last node in the chain
int info;
3. Make the second last node next field to NULL
int prn;
struct node *next; 4. Free the last node
}*top; 6. Stop
Insertion with Priority N and ITEM
1. Start
2. Traverse the list until finding a node X whose priority number exceeds the
priority N.
3. If node found then Insert ITEM in front of node X
4. If no such node is found, insert ITEM as the last item of the list
5. Stop
School of Computer Engineering
Priority Queue - Array Representation
61
 Another way to maintain a priority queue in memory is to use a separate queue for each priority
number.
 Each such queue will appear in its own circular array and must have its own pair of pointers,
FRONT and REAR
 If each queue is allocated the same amount of space, a two–dimensional array QUEUE can be
used instead of the linear array
 FRONT[K] and REAR[K] contains the front and rear elements of row K of queue, the row that
maintains the queue of elements with priority number K
Systematic diagram
Priority
FRONT REAR
1 2 3 4 5
1 2 2
1 A
2 1 3
2 B C G
3 0 0
3
4 E D 4 5 1
5 F 5 4 4
School of Computer Engineering
Priority Queue – Array Representation cont…
62

Deletion

1. Start
2. Find the smallest K such that FRONT[K] <> NULL
3. Delete and Process the front element in row K of Queue
4. Stop

Insertion
1. Start
2. Insert ITEM as the rear element in row M of queue
3. Stop

School of Computer Engineering

Assignments
63

Assignment 1 Assignment 2

Write an algorithm to convert an infix Write pseudo code to check whether a given
expression into it equivalent postfix expression. postfix expression is correctly parenthesized
Explain the execution of algorithm using the
following expression. Assignment 3

Evaluate the following postfix expression:

(A+B) * C – (D * E) î (F + G + (H * M)) 5 3 2 * + 7 9 /4 * 2 / - 6 + 2 -

Assignment 4 Assignment 5

Write C functions for insertion, deletion, Write an algorithm to copy the data elements of
traversal operation for circular queues one stack to other without changing the order
and without using any other data structure
Assignment 6 Assignment 7

Write C functions for insertion, deletion, Write C functions for insertion, deletion,
traversal operation for input restricted deques traversal operation for priority queues

School of Computer Engineering

Assignments
64

Assignment 8 Assignment 9

Write an algorithm to check for balanced Write pseudo code for recursive function to
parentheses (, ), {, }, [ and ] in an expression display the string in reverse order.
Assignment 10 Assignment 11

Write an algorithm to convert postfix expression Write an algorithm to convert prefix expression
to infix expression. to infix expression.
Assignment 12 Assignment 13

Write an algorithm to convert postfix expression Write an algorithm to convert prefix expression
to prefix expression. to postfix expression.
Assignment 14

Write an algorithm for Tower of Hanoi (iteratively and recursively).

Assignment 15
We are given stack data structure, the task is to implement queue using only given queue
data structure.
School of Computer Engineering
65

School of Computer Engineering

Home Work (HW)
66

1. You are given 2 queues where each queue contains timestamp pair price. You have to
print < price 1 price 2 > for all those timestamps where abs(ts1 – ts2) <= 1 second
where ts1 and price 1 from 1st queue and ts2 and price 2 from 2nd queue.
2. Given an array, print the Next Greater Element (NGE) for every element. The Next
greater Element for an element x is the first greater element on the right side of x in
array. Elements for which no greater element exist, consider next greater element as
-1. Examples:
a) For any array, rightmost element always has next greater element as -1.
b) For an array which is sorted in decreasing order, all elements have next greater
element as -1.
c) For the input array [4, 5, 2, 25}, the next greater elements for each element are as
follows.
Element NGE
4 5
5 25
2 25
25 -1

School of Computer Engineering

Home Work (HW)
67

3. Implement a stack using queues

4. Implement a queue using stacks
5. In a party of N people, only one person is known to everyone. Such a person may be
present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask
questions like “does A know B? “. Find the stranger (celebrity) in minimum number
of questions.
6. Find the largest rectangular area possible in a given histogram where the largest
rectangle can be made of a number of contiguous bars. For simplicity, assume that all
bars have same width and the width is 1 unit. For example, consider the following
histogram with 7 bars of heights {6, 2, 5, 4, 5, 1, 6}. The largest possible rectangle
possible is 12 (see the below figure, the max area rectangle is highlighted in red)

School of Computer Engineering

Home Work (HW)
68

7. Suppose there is a circle. There are n petrol pumps on that circle. You are given two
sets of data.

1. The amount of petrol that every petrol pump has.

2. Distance from that petrol pump to the next petrol pump.

Calculate the first point from where a truck will be able to complete the circle (The
truck will stop at each petrol pump and it has infinite capacity). Expected time
complexity is O(n). Assume for 1 litre petrol, the truck can go 1 unit of distance.

For example, let there be 4 petrol pumps with amount of petrol and distance to next
petrol pump value pairs as {4, 6}, {6, 5}, {7, 3} and {4, 5}. The first point from where
truck can make a circular tour is 2nd petrol pump. Output should be “start = 1”
(index of 2nd petrol pump).

School of Computer Engineering

Home Work (HW)
69

8. Given an array of non-negative integers. Find the largest multiple of 3 that can be
formed from array elements. For example, if the input array is {8, 1, 9}, the output
should be “9 8 1”, and if the input array is {8, 1, 7, 6, 0}, output should be “8 7 6 0”.

9. Given an array and an integer k, find the maximum for each and every contiguous
subarray of size k.
Examples:

Input :
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, k = 3
Output :
3345556

Input :
arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, k = 4
Output :
10 10 10 15 15 90 90

School of Computer Engineering

Home Work (HW)
70

10. We are given queue data structure, the task is to implement stack using only given
queue data structure.
11. Given a matrix of dimension m*n where each cell in the matrix can have values 0, 1
or 2 which has the following meaning:

0: Empty cell, 1: Cells have fresh oranges, 2: Cells have rotten oranges .

So we have to determine what is the minimum time required so that all the oranges
become rotten. A rotten orange at index [i,j] can rot other fresh orange at indexes [i-
1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right). If it is impossible to rot every
orange then simply return -1.

Examples:
Input: arr[][C] = { {2, 1, 0, 2, 1},
{1, 0, 1, 2, 1},
{1, 0, 0, 2, 1}};
Output:
All oranges can become rotten in 2 time frames.
School of Computer Engineering
Supplementary Reading
71

 http://www.geeksforgeeks.org/stack-data-structure/
 http://www.geeksforgeeks.org/queue-data-structure/
 https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm
 https://www.tutorialspoint.com/data_structures_algorithms/dsa_queue.htm
 http://www.geeksforgeeks.org/implement-stack-using-queue/
 http://www.geeksforgeeks.org/queue-using-stacks/
 http://nptel.ac.in/courses/106102064/2
 http://nptel.ac.in/courses/106102064/3
 http://freevideolectures.com/Course/2279/Data-Structures-And-Algorithms/2
 http://freevideolectures.com/Course/2279/Data-Structures-And-Algorithms/3

School of Computer Engineering

FAQ
72

What is Stack?
Stacks are data structures that allow us to insert and remove items. The operate
like a stack of papers or books on our desk - we add new things to the top of the
stack to make the stack bigger, and remove items from the top as well to make
the stack smaller. This makes stacks a LIFO (Last In First Out) data structure –
the data we have put in last is what we will get out first.

Before we consider the implementation to a data structure it is helpful to

consider the operations. We then program against the specified operations.
Based on the description above, we require the following functions:

bool stack_empty(stack S); /* O(1), check if stack empty */

stack stack_new(); /* O(1), create new empty stack */
void push(stack S, elem e); /* O(1), add item on top of stack */
elem pop(stack S) /* O(1), remove item from top */

School of Computer Engineering

FAQ cont…
73

What is Queue?
A queue is a data structure where we add elements at the back and remove
elements from the front. In that way a queue is like “waiting in line”: the first
one to be added to the queue will be the first one to be removed from the queue.
This is also called a FIFO (First In First Out) data structure.

Before we consider the implementation to a data structure it is helpful to

consider the operations. We then program against the specified operations.
Based on the description above, we require the following functions:

bool queue_empty(queue Q); /* O(1), check if queue is empty */

queue queue_new(); /* O(1), create new empty queue */
void enq(queue Q, elem s); /* O(1), add item at back */
elem deq(queue Q); /* O(1), remove item from front */

School of Computer Engineering

FAQ cont…
74

Implement Stack using Queue: We are given a stack data structure with push
and pop operations, the task is to implement a queue using instances of stack
data structure and operations on them.

Solution: http://www.geeksforgeeks.org/queue-using-stacks/

School of Computer Engineering

FAQ cont…
75

Implement Queue using Stack: We are given a queue data structure with
enqueue and deque operations, the task is to implement a stack using instances
of queue data structure and operations on them.

Solution: http://www.geeksforgeeks.org/implement-stack-using-queue/

School of Computer Engineering