Data Structures & Algorithms

Introduction to Graphs

By Ms. Sabah
Week
1) Introduction
A graph G can be defined as an ordered set G(V, E) where V(G) represents the set of vertices and
E(G)
represents the set of edges which are used to connect these vertices.
A Graph G(V, E) with 5 vertices (A, B, C, D, E) and six edges ((A,B), (B,C), (C,E), (E,D), (D,B),
(D,A)) is shown in the figure.

An undirected graph, edges are not associated with the directions with
them.
1) Introduction
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.
A directed graph is shown in the figure.
Example
Suppose that a network is made up of data centers and communication links
between computers. We can represent the location of each data center by a
point and each communications link by a line segment,
3) Graph representation
Two common ways to represent graphs for
algorithms:
a) Adjacency matrix.
b) Adjacency lists.
a) Adjacency matrix
�In sequential representation, we use adjacency matrix to store the mapping
represented by vertices and edges.
� In adjacency matrix, the rows and columns are represented by the graph vertices.
� A graph having n vertices, will have a dimension n x n.
�An entry Mij in the adjacency matrix representation of an undirected graph G will be 1 if
there exists an edge between Vi and Vj.
a) Adjacency matrix
For an undirected graph and its adjacency matrix
representation
Example
a) Adjacency matrix
For directed graph and its adjacency matrix
representation
Example
a) Adjacency matrix
For weighted graph and its adjacency matrix
representation
Example
b) Adjacency lists
In the linked representation, an adjacency list is used to store the Graph into the
computer's memory.
The undirected graph shown in the figure
b) Adjacency lists
�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 last node of the list.
�The sum of the lengths of adjacency lists is equal to the twice
of the number of edges present in an undirected graph.
b) Adjacency lists
In a directed graph, the sum of lengths of all the adjacency lists is equal to the number
of edges present in the graph
Example
b) Adjacency lists
In the case of weighted directed graph, each node contains an extra field that is
called the weight of the node.
Example
Class Example
4) Graph traversals
� Graph traversal means visiting every vertex and edge exactly once in a well-defined
order.
� While using certain graph algorithms, you must ensure that each vertex of the graph is
visited exactly once.
� The order in which the vertices are visited are important and may depend upon the
algorithm
or question that you are solving.
� During a traversal, it is important that you track which vertices have been visited.
� The most common way of tracking vertices is to mark them.
� There are two approaches to traverse graphs
� Breadth First Search
� Depth First Search
Queue & Stack
a) Breadth-First Search � BFS
BFS is a traversing algorithm where you should start traversing from a selected node
(source or starting node) and traverse the graph layer-wise thus exploring the neighbor
nodes.
As the name BFS suggests, you are required to traverse the graph breadthwise as
follows:
◦ First move horizontally and visit all the nodes of the current layer
◦ Move to the next layer

Queue Data structure (first in first out) is used in BFS Algorithm

◦ In BFS, one vertex is selected at a time when it is visited and marked then its adjacent are
visited and stored in the queue.
 BFS Algorithm
A standard BFS implementation puts each vertex of the graph into one
of two categories:
◦ Visited
◦ Not Visited

The purpose of the algorithm is to mark each vertex as visited while

avoiding cycles.
The algorithm works as follows:
◦ Start by putting any one of the graph's vertices at the back of a queue.
◦ Take the front item of the queue and add it to the visited list.
◦ Create a list of that vertex's adjacent nodes. Add the ones which aren't in the
visited list to the back of the queue.
◦ Keep repeating steps 2 and 3 until the queue is empty.
◦ The graph might have two different disconnected parts so to make sure that we
cover every vertex, we can also run the BFS algorithm on every node
Example

Suppose we consider node 0 as a root node.

Therefore, the
traversing would be started from node 0.

Once node 0 is removed from the Queue, it gets printed

and marked as a visited node.
Once node 0 gets removed from the Queue, then the
adjacent
nodes of node 0 would be inserted in a Queue
Example
�Now the node 1 will be removed from the Queue; it gets
printed and marked as a visited node
�Once node 1 gets removed from the Queue, then all the
adjacent nodes of a node 1 will be added in a Queue.
� The adjacent nodes of node 1 are 0, 3, 2, 6, and 5.
� But we have to insert only unvisited nodes in a Queue.
�Since nodes 3, 2, 6, and 5 are unvisited; therefore, these
nodes will be added in a Queue
Example
�The next node is 3 in a Queue. So, node 3 will be removed
from the Queue, it gets printed and marked as visited
�Once node 3 gets removed from the Queue, then all the
adjacent nodes of node 3 except the visited nodes will be
added in a Queue.
� The adjacent nodes of node 3 are 0, 1, 2, and 4.
� Since nodes 0, 1 are already visited, and node 2 is present
in a
Queue; therefore, we need to insert only node 4 in a Queue.
Example
Now, the next node in the Queue is 2. So, 2 would be
deleted
from the Queue. It gets printed and marked as visited
Once node 2 gets removed from the Queue, then all the
adjacent nodes of node 2 except the visited nodes will be
added in a Queue.
The adjacent nodes of node 2 are 1, 3, 5, 6, and 4.
Since the nodes 1 and 3 have already been visited, and 4,
5, 6 are already added in the Queue; therefore, we do not
need to insert any node in the Queue.
Example

�The next element is 5. So, 5 would be deleted from the

Queue. It gets printed and marked as visited
�Once node 5 gets removed from the Queue, then all the
adjacent nodes of node 5 except the visited nodes will be
added in the Queue.
� The adjacent nodes of node 5 are 1 and 2.
�Since both the nodes have already been visited; therefore,
there is no vertex to be inserted in a Queue.
 Example
�The next node is 6. So, 6 would be deleted from the Queue. It gets printed and marked as
visited
�Once the node 6 gets removed from the Queue, then all the adjacent nodes of node 6 except the
visited nodes will be added in the Queue.

Result:
� The adjacent nodes of node 6 are 1 and 4.
0,1,3,2,5,6,4 �Since the node 1 has already been visited and node 4 is
already added in the Queue; therefore, there is not vertex
to be inserted in the Queue.
� The next element in the Queue is 4. So, 4 would be
deleted
from the Queue. It gets printed and marked as visited.
�(Since all the adjacent nodes have already been
visited; so, there is no vertex to be inserted in the
Queue.)
Example
The next element in the Queue is 4. So, 4 would be deleted from the Queue. It gets
printed and marked as visited.
Example
Example
b) Depth-First Search � DFS
Depth First Search will follow a path from the starting node to an ending node, then
another path from start to end until all the nodes are visited.
DFS starts the traversal from the root node and visits nodes as far as possible from
the root node.
This method is implemented using a stack data structure and generally requires less
memory
than BFS.
Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses
a stack to remember to get the next vertex to start a search, when a dead end occurs in
any iteration.
Depth First Search Algorithm
A standard DFS implementation puts each vertex of the graph into one of two
categories:
◦ Visited
◦ Not Visited
The purpose of the algorithm is to mark each vertex as visited while avoiding
cycles. The DFS algorithm works as follows:
◦ Start by putting any one of the graph's vertices on top of a stack.
◦ Take the top item of the stack and add it to the visited list.
◦ Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to
the top of the stack.
◦ Keep repeating steps 2 and 3 until the stack is empty.
EXAMPLE
 EXAMPLE
• We start from vertex 0, the DFS algorithm starts by putting it in the
Visited list and putting all its adjacent vertices in the stack.
EXAMPLE
Next, we visit the element at the top of stack i.e. 1 and go to its adjacent nodes.
Since 0 has already been visited, we visit 2 instead.
EXAMPLE
Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and
visit it.
EXAMPLE
Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and
visit it.
EXAMPLE
After we visit the last element 3, it doesn't have any unvisited adjacent nodes, so
we have completed the Depth First Traversal of the graph.
EXAMPLE

Answer: A B S C D E H G F
EXAMPLE
Difference between Depth First Search and
Breadth First Search
When to use BFS vs DFS
BFS is optimal for finding the shortest distance, and is more suitable for searching
vertices which are closer to the given source.
DFS is more suitable when there are solutions away from source.
◦ DFS is more suitable for game or puzzle problems.
◦ We make a decision, then explore all paths through this decision.
◦ And if this decision leads to win situation, we stop.
Applications of Graph
• In Computer science graphs are used to represent the flow of computation.
• Google maps uses graphs for building transportation systems, where intersection of two(or more) roads
are considered to be a vertex and the road connecting two vertices is considered to be an edge, thus
their navigation system is based on the algorithm to calculate the shortest path between two vertices.
• In Facebook, users are considered to be the vertices and if they are friends then there is an edge
running between them. Facebook's Friend suggestion algorithm uses graph theory. Facebook is an
example of undirected graph.
• In World Wide Web, web pages are considered to be the vertices. This is an example of Directed
graph. It was the basic idea behind Google Page Ranking Algorithm.
• In Operating System, we come across the Resource Allocation Graph where each process and
resources are considered to be vertices. Edges are drawn from resources to the allocated process, or
from requesting process to the requested resource. If this leads to any formation of a cycle then a
deadlock will occur.
THANK YOU
 Data Structures & Algorithms

Introduction to Trees

Week
By Ms. Sabah
10
Introduction
� A tree is a nonlinear hierarchical data structure that consists of nodes connected by
edges.
� A tree in which a parent has no more than two children is called a binary tree.
� A tree is an acyclic graph or graph having no cycles.
� An undirected graph is a tree if and only if there is a unique simple path between any
two of
its vertices.
 Rooted
Trees
A rooted tree is a tree in which one vertex has been designated as the root and every edge is
directed away from the root.
 Properties
� The important properties of tree data structure are-
� There is one and only one path between every pair of vertices in
a tree.
� A tree with n vertices has exactly (n-1) edges.
� A graph is a tree if and only if it is minimally connected.
� Any connected graph with n vertices and (n-1) edges is a tree
Tree Terminologies
Root
The first node from where the tree originates is called as a root
node. In any tree, there must be only one root node.
We can never have multiple root nodes in a tree data structure.
Tree Terminologies
Edge
The connecting link between any two nodes is called as an edge.
It is the link between any two nodes.
In a tree with n number of nodes, there are exactly (n-1) number of
edges.
Tree Terminologies
Parent-
The node which has a branch from it to any other node is called as a parent
node. In other words, the node which has one or more children is called as
a parent node. In a tree, a parent node can have any number of child nodes.
Tree Terminologies
Child
The node which is a descendant of some node is called as a
child node. All the nodes except root node are child nodes.
Tree Terminologies
Siblings-
Nodes which belong to the same parent are called as
siblings. In other words, nodes with the same parent are
sibling nodes.
Tree Terminologies
Degree-
Degree of a node is the total number of children of that node.
Degree of a tree is the highest degree of a node among all the nodes in
the tree.
 Tree Terminologies
Internal Node-
The node which has at least one child is called as an internal
node.
Internal nodes are also called as non-terminal nodes.
Every non-leaf node is an internal node.

Each node with a parent and a child is called the inner node
or internal node of the tree.
Tree Terminologies
Leaf Node-
The node which does not have any child is called as a leaf
node.
Leaf nodes are also called as external nodes or terminal
nodes.
Tree Terminologies
Level-
In a tree, each step from top to bottom is called as level of a
tree.
The level count starts with 0 and increments by 1 at each level or
step.
Tree Terminologies
Subtree-
In a tree, each child from a node forms a subtree
recursively. Every child node forms a subtree on its
parent node.
Tree Traversal
Traversal is a process to visit all the nodes of a tree and may print their values too.
Because, all nodes are connected via edges (links) we always start from the root
(head) node.
◦ That is, we cannot randomly access a node in a tree.
Tree Traversal
There are three ways which we use to traverse a
tree − In-order Traversal (Left, Node(root), Right)
Pre-order Traversal (Node(root), Left, Right)
Post-order Traversal (Left, Right, Node(root))
a) In-order Traversal
In this traversal method, the left sub-tree is visited first, then the root and later the
right sub- tree
If a binary tree is traversed in-order, the output will produce sorted key values in an
ascending order.

D→B→E→A→F→C→G
Pre-order Traversal
In this traversal method, the root node is visited first, then the left sub-tree and finally
the right sub-tree.

A→B→D→E→C→F→G
Post-order Traversal
In this traversal method, the root node is visited last, hence the name. First we traverse
the left sub-tree, then the right sub-tree and finally the root node.

D→E→B→F→G→C→A
Exercise

Preorder
Traversal

ABDCEGFH
I.

Post-order
Traversal

DBGEHIFCA

In-order

Traversal B D A

G E C H F I.
Exercise

Preorder Traversal-

100 , 20 , 10 , 30 , 200 , 150 , 300

In-order Traversal-

10 , 20 , 30 , 100 , 150 , 200 , 300

Post-order Traversal-

10 , 30 , 20 , 150 , 300 , 200 , 100

Exercise
Height of a Tree
• The height of a binary tree is defined as:
• The number of edges on the longest path from the root to a leaf node
(sometimes people count nodes instead of edges → then it's "number of nodes on the longest
path").
Method to Calculate Height

1. If the tree is empty (NULL) → height = -1 (when counting edges) or 0 (when counting nodes).
2. If the tree has only one node (root only) → height = 0 (edges) or 1 (nodes).
3. Otherwise:
4. Height(Tree)=1+max⁡(Height(Left Subtree),Height(Right Subtree))
 A
/ \
B C
/\ /\
D EF G
•Height of D, E, F, G = 0 (leaf nodes).
•Height of B = 1 + max(height(D), height(E)) = 1 + max(0, 0) = 1
•Height of C = 1 + max(height(F), height(G)) = 1 + max(0, 0) = 1
•Height of A = 1 + max(height(B), height(C)) = 1 + max(1, 1) = 2

Height of the tree = 2 (in edges)

(or 3 if counting nodes).
Binary Trees and its Memory Representation
What is a Binary Tree
• A binary tree is a a collection of nodes that consists of the root
and other subsets to the root points, which are called the left and
right subtrees.

• Every parent node on a binary tree can have up to two child

nodes (roots of the two subtrees); any more children and it
becomes a general tree.

• A node that has no children is called a leaf node.

A Few Terms Regarding Binary Trees
A

B C
A is the root
B and C are A’s children
D E F A is B’s parent
B & C are the root of two
subtrees
D, E, and G are leaves
G
This is NOT A Binary Tree

B C

D E F G H

This is a general tree because C has three child nodes

This is NOT A Binary Tree
This is a graph
because A, B, E, H, F and C
A form a circuit

B C

D E F G

H
Basic Implementation of a Binary Tree
• We can implement a binary in essentially the same way as a linked
list, except that there are two nodes that comes next:
public class Node {
private int data;
private Node left;
private Node right;
public int getData() {
return data;
}

public Node getLeft() {

return left;
}

public Node getRight() {

return right;
}

public void setData(int x) {

data = x;
public void setLeft(Node p) {
left = p;
}

public void setRight(Node p) {

right = p;
}
Binary Tree Representation

There are two primary ways to represent binary trees:

1. Linked Node Representation
2. Array Representation
1. Linked Node Representation
• This is the simplest way to represent a binary tree. Each node contains data and pointers to
its left and right children.
• This representation is mostly used to represent binary tree with multiple advantages. The most
common advantages are given below.
2. Array Representation

• Array Representation is another way to represent binary trees, especially useful when the tree
is complete (all levels are fully filled except possibly the last, which is filled from left to right). In
this method:
• The tree is stored in an array.
• For any node at index i:
• Left Child: Located at 2 * i + 1
• Right Child: Located at 2 * i + 2
• Root Node: Stored at index 0
THANK YOU
 Data Structures & Algorithms

Data Structures & Algorithms

Week
By Ms. Sabah
9
b)
Stacks
b) Stacks
A Stack is a data structure following the LIFO (Last In, First Out) principle.
◦ A stack is a linear list in which all additions and deletions are restricted
to one end, called the top.
◦ In programming terms, putting an item on top of the stack is called push and removing an item
is
called pop
Implementing a Stack
There are two ways we can implement a
stack:
◦ Using an array
◦ Using a linked list
Implementing a Stack
Implementing a stack using an array is fairly
easy.
◦ The bottom of the stack is at data[0]
◦ The top of the stack is at data[numItems-1]
◦ push onto the stack at data[numItems]
◦ pop off of the stack at data[numItems-1]
Implementing a Stack
Implementing a stack using a linked list isn’t that
bad either…
◦ Store the items in the stack in a linked list
◦ The top of the stack is the head node, the bottom of
the stack is the end of the list
◦ push by adding to the front of the list
◦ pop by removing from the front of the list
Basic Operations of Stack
There aresome basic operations that allow us to perform different actions
on a
stack.
Push: Add an element to the top of a stack
Pop: Remove an element from the top of a stack
IsEmpty: Check if the stack is empty
IsFull: Check if the stack is full
Peek: Get the value of the top element without removing it
Push (Item Type newItem)
Algorithm
• Check if the top is equal to the size of the
array. If true, print "Stack is Full" and return.
• If false, increment the top by one.
• Assign an item to the top of the stack.
Pop (ItemType& item)
• Check if the top is equal to -1. If true, then print
"Stack is Empty" and return.
• If false, then store the top item in a variable.
• Decrement the top.
• Return the stored item through the variable.
isEmpty()
• Check if the top is equal to -1. If True,
returns True.
• Else return false.
isFull()
• Check if the top is equal to the size of
the array, i.e., n, then return True.
• Otherwise, return False.
Peek()
• This operation is used to see the top element of
the stack. The Peek function will return the top
element without removing it. It will work only
when the stack is not empty.

• Check if the stack top is equal to -1. If true, then

print "Stack is Empty" and return.
• If false, store the top of the stack item in a
variable.
• Return that variable.
Stack Overflow & Stack Underflow

• Stack overflow
• The condition resulting from trying to push an element onto a full stack.
• if(![Link]()) [Link](item);
• Stack underflow
• The condition resulting from trying to pop an empty stack.
• if(![Link]()) [Link](item);
Applications of Stacks
Although stack is a simple data structure to implement, it is
very powerful. The most common uses of a stack are:
◦ To reverse a word - Put all the letters in a stack and pop them out.
Because of the LIFO order of stack, you will get the letters in reverse
order.
◦ In compilers - Compilers use the stack to calculate the value of
expressions like 2 + 4 / 5 * (7 - 9) by converting the expression to
prefix or postfix form.
◦ In browsers - The back button in a browser saves all the URLs you
have visited previously in a stack. Each time you visit a new page, it is
added on top of the stack. When you press the back button, the current
URL is removed from the stack, and the previous URL is accessed.
d)
Queue
 What is a queue?
It is an ordered group of homogeneous items of
elements. Queues have two ends:
◦ Elements are added at one end.
◦ Elements are removed from the other end.
◦ In programming terms, putting items in the queue is called enqueue, and removing items from the queue is called
dequeue.

The element added first is also removed first (FIFO: First In,
First Out).
Working of Queue
Queue operations work as
follows: Two pointers FRONT
and REAR
FRONT track the first element of the
queue REAR track the last element of
the queue Initially, set value of FRONT
and REAR to -1
Basic Operations of Queue
A queue is an object (an abstract data structure - ADT) that
allows the following operations:
Enqueue: Add an element to the end of the queue
Dequeue: Remove an element from the front of the queue
IsEmpty: Check if the queue is empty
IsFull: Check if the queue is full
Peek: Get the value of the front of the queue without removing
it
Basic Operations of Queue
Enqueue Operation
check if the queue is full
for the first element, set the value of FRONT
to 0 increase the REAR index by 1
add the new element in the position pointed to by REAR
Dequeue Operation
check if the queue is empty
return the value pointed by FRONT
increase the FRONT index by 1
for the last element, reset the values of FRONT and
REAR to -1
peek()
• This function helps to see the data at
the front of the queue. The algorithm of
peek() function is as follows:
isfull()
• As we are using single dimension array to
implement queue, we just check for the rear
pointer to reach at MAXSIZE to determine that
the queue is full.
• In case we maintain the queue in a circular
linked-list, the algorithm will differ.
• Algorithm of isfull() function
isempty()
Applications of Queue
Queue, as the name suggests is used whenever we need to manage
any group of objects in an order in which the first one coming in, also
gets out first while the others wait for their turn, like in the following
scenarios:

• Serving requests on a single shared resource, like a

printer, CPU task scheduling etc.
• In real life scenario, Call Center phone systems uses
Queues to hold people calling them in an order, until a
service representative is free.
• Handling of interrupts in real-time systems. The
interrupts are handled in the same order as they arrive
i.e First come first served.
THANK YOU
 Data Structures & Algorithms

Data Structures & Algorithms

Week
By Ms. Sabah
6
Week 1
Objectives
1. Understand fundamental terminology related to data structures.
2. Identify types of data structures and their operations.
3. Define algorithms and discuss the time-space tradeoff.
4. Recognize the importance of efficient data organization in computing.
Introduction
Arithmetic Expressions
Arithmetic Expression:
◦ An arithmetic expression is defined as several operands or data items combined using several
operators.
◦ For example; a+b*(c-d) is an expression.

Operands:
◦ Operands represent the data in an expression used for the computation.
◦ We can also say that operand or operands are the items on which operation is performed.
◦ In the above example of arithmetic expression, a, b, c, and d are the operands.
Operators:
◦ Operators are the special symbols used to compute the arithmetic operation.
◦ It tells the compiler or interpreter to perform a specific task or computation between two or more
operands.
◦ In the above example of arithmetic expression, +, *, and – are the operators.
◦ The way to write arithmetic expression is known as a notation.
Arithmetic Expressions
There are three different and equivalent
notations to represent an algebraic expression.
◦ Infix Notations
◦ Prefix Notations� Polish Notations
◦ Postfix notations� Reverse Polish Notations
1. Infix Notations
� The operators are written in between the operands in Infix notation.
� It is the simplest and most commonly used notation to represent an
expression.
� It is called infix because of the operator’s place in the expression.
� Is exactly the fully parenthesized notation
� For example, a+b+c here, the operator '+' is placed between a and b and
b and c.
� We always find it simple to evaluate the expression written in infix notation.
� Conversion of infix to postfix notation is done by using a stack.
2. Prefix Notation/ Polish Notation
� Prefix notation is also known as the Polish Notation.
� It is called a prefix because of the operator's place in the expression.
� The operators are written before the operands in prefix notation.
� For example, +ab here, the ‘+’ operator is written before a and b operands.
�If the operator has a defined fixed number of operands, the syntax does not require
brackets or parenthesis to lessen ambiguity
3. Postfix Notation/ Reverse Polish
Notation
� In a postfix expression
� An operator is written after its operands.
� The infix expression 2+3 is 23+ in postfix notation.
� For postfix expressions, operations are performed in the order in which they are written
(left to
right).
� No parentheses are necessary.
� The infix expression 2+3*4 is 234*+ in postfix notation
� The infix expression 3*4+2*5 translates to 34*25*+ in postfix notation.
� The infix expression 3*(4+2)*5 translates to 342+*5*
Infix to prefix conversion (MANUALLY )
�Apply appropriate brackets/paranthesis to expressions by
following operator precedence & associativity rules.
�Start by converting inner most sub expressions to prefix & name it
with temporary placeholder.
�Repeat step 2 on other larger sub expressions till the full expression
is solved. Re-substitute the
• temporary placholders with their original values
� Order of Operations / Operator Precedence –
� Parentheses - {}, (1, 0)
� Exponents(Right to Left) – A^B, 2^3^4
� Multiplication & Division(Left to Right) - A*B/C
� Addition & Subtraction Left to Right) - A+B-C Associativity –
�Associativity 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.
Examples
a-b+c � +-abc
a+b*c-d/e � -+a*bc/de
(a+b^c)*d+e �
+*+A^BCD
Infix to postfix conversion (MANUALLY )
• Apply appropriate brackets/paranthesis to expressions by
following operator precedence & associativity rules.
• Start by converting inner most sub expressions to prefix & name it
with temporary placeholder. Repeat step 2 on other larger sub
expressions till the full expression is solved. Re-substitute the
• temporary placholders with their original values
◦ Order of Operations / Operator Precedence –
◦ Parentheses - {}, (1, 0)
◦ Exponents(Right to Left) – A^B, 2^3^4
◦ Multiplication & Division(Left to Right) - A*B/C
◦ Addition & Subtraction Left to Right) - A+B-C Associativity –
◦ Associativity 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.
Examples
b. +c
◦ ab-c+
a+b*c-d/e
◦ ABC*+DE/-
(A+B * (C-
D))/E
◦ ABCD -*+E/
Examples
Conversions using
STACK DS
 Rules for Infix to postfix using stack
Scan Expression from Left to
Right Print OPERANDs as the
arrive Operator:
◦ If OPERATOR arrives & Stack is empty, push this operator onto the stack
◦ IF incoming OPERATOR has HIGHER precedence than the TOP of the Stack, push it on stack
◦ IF incoming OPERATOR has LOWER precedence than the TOP of the Stack, then POP and print
the TOP. Then
test the incoming operator against the NEW TOP of stack.
◦ IF incoming OPERATOR has EQUAL precendence with TOP of Stack, use ASSOCIATIVITY Rules.

For ASSOCIATIVITY of LEFT to RIGHT

◦ - POP and print the TOP of stack, then PUSH the incoming OPERATOR

For ASSOCIATIVITY of RIGHT to LEFT –

◦ PUSH incoming OPERATOR on stack.

At the end of Expression, POP & print all,

 • If OPERATOR arrives & Stack is empty, push this
operator
onto the stack
• IF incoming OPERATOR has HIGHER precedence
than the TOP of the Stack, push it on stack

Exampl • IF incoming OPERATOR has LOWER precedence

than the TOP of the Stack, then POP and print the
TOP. Then test the incoming operator against the
NEW TOP of stack.

e • IF incoming OPERATOR has EQUAL precedence with

TOP of
Stack, use ASSOCIATIVITY Rules.
Infix to prefix
Rules for the conversion of infix to prefix expression
◦ First, reverse the infix expression given in the problem.
◦ Scan the expression from left to right.
◦ Whenever the operands arrive, print them.
◦ If the operator arrives and the stack is found to be empty, then simply push the operator into the
stack.
Infix to prefix
Infix to prefix
Expression = (A+B^C)*D+E^5

Step 1. Reverse the infix expression.

5^E+D*)C^B+A(
Step 2. Make Every '(' as ')' and every ')'
as '('
5^E+D*(C^B+A)
Step 3. Convert expression to postfix
form.
Infix to prefix
Step 4. Reverse the
expression.
+*+A^BCD^E5
Example 2
Infix Expression: (A+B)+C-(D-E)^F
Step 1. First reverse the given infix
expression
◦ After Reversing: F^)E-D(-C+)B+A(
Step 2. Make Every '(' as ')' and every ')'
as '(‘
◦ F^(E-D)-C+(B+A)
Step 3. Convert expression to postfix
form.
F^(E-D)-
C+(B+A)
Example 2
Reverse the expression to get prefix expression ++AB-C^-
DEF (A+B)+C-(D-E)^F � ++AB-C^-DEF
Evaluation with Example
� Consider this Expression : / * + 5 6 3 11.
� While evaluating the expression we take decision for two
cases:
� When the Character is an Operand or When the Character is an
Operator.
� We will use a Stack for this evaluation.
�We scan the Expression from right to left, if the current
character is an Operand we push it into the stack.
/ * + 5 6 3 11

• We scan the Expression from right to left, if the

current
character is an Operand we push it into the stack.
• So from 11 to 5 we push the elements into the
stack.

• As soon as we get an operator we will

perform operation on its previous two
elements, so continuing traversing
from right to left we first get ‘+’ operator
so we pop two elements from stack (5
& 6) compute their result with the
operator i.e. 5+6 = 11, and push the
result back into the stack for future
evaluation.
• The Stack now is:
The next Operator is ‘*’ Operator
(Multiply), so we again pop the two
elements from stack and repeating the
process of Step 2.
So we compute the result from their
operation (11 * 3 =33) and push it back
to the stack again.
The stacks now look like:

Finally, we have the ‘/’ operator so we pop

33 and 11 compute the result push it back
to the stack.
Now we have reached the leftmost or start
index of the expression so at this point
our stack will contains only one value
which will be our Resultant Evaluated
Prefix Expression.
THANK YOU
 Data Structures & Algorithms

Hashing

Week
By Ms. Sabah
15
Hashing
• Hashing is a technique to convert a range of key values into
a range of indexes of an array
• It is done for faster access to elements.
• The efficiency of mapping depends on the efficiency of the
hash function used.
Hash Tables.
• Hash Table is a data structure which stores data in an associative
manner.
• In a hash table, data is stored in an array format, where each data
value has its own unique index value.
• Access of data becomes very fast if we know the index of the desired
data.
• Thus, it becomes a data structure in which insertion and search
operations are very fast irrespective of the size of the data.
• Hash Table uses an array as a storage medium and uses hash
technique to generate an index where an element is to be inserted or
is to be located from.
Hashing Functions.
• if we want to store employee records, and each employee is
uniquely identified using an employee number.
• We can use the employee number as the key and assign
the employee data as the value.

• The above approach will require extra free space of the order
of (m *n2) where the variable m is the size of the array, and
the variable n is the number of digits for the employee
number.
• This approach introduces a storage space problem.
 Continue
…
• A hash function solves the above problem by
getting the employee number and using it to
generate a hash integer value, fixed digits, and
optimizing storage space.
• The purpose of a hash function is to create a
key that will be used to reference the value that
we want to store.
• The function accepts the value to be saved
then uses an algorithm to calculate the value of
the key.
� The following is an example of a simple hash function
� h(k) = k1 % m
� HERE,
� h(k) is the hash function that accepts a parameter k.
The parameter k is the value that we want to
calculate the key for.
� k1 % m is the algorithm for our hash function where
k1 is the value we want to store, and m is the size of
the list. We use the modulus operator to calculate the
key.
 Example:

� Let’s assume that we have a list with a fixed

size of 3 and the following values
� [1,2,3]
� We can use the above formula to calculate the
positions that each value should occupy.
� The following image shows the available
indexes in our hash table.
� Step 1)
� Calculate the position that will be occupied by the first value like so
� h(1) = 1 % 3
� =1
� The value 1 will occupy the space on index 1.
� Step 2)
� Calculate the position that will be occupied by the second value
� h(2) = 2 % 3
� =2
� The value 2 will occupy the space on index 2
� Step 3)
� Calculate the position that will be occupied
by the third value.
� h(3) = 3 % 3
� =0
� The value 3 will occupy the space on index 0
� Final Result
� Our filled in hash table will now be as follows.
� Final Result
� Our filled in hash table will now be as
follows.
 Linear Probing

• As we can see, it may happen that the hashing

technique is used to create an already used index of
the array.
• In such a case, we can search the next empty location
in the array by looking into the next cell until we find an
empty cell.
• This technique is called linear probing.
 Hash table operations:
� Here, are the Operations supported by Hash tables:
� Insertion – this Operation is used to add an element
to the hash table
� Searching – this Operation is used to search for
elements in the hash table using the key
� Deleting – this Operation is used to delete elements
from the hash table
Insert Operation:
• Whenever an element is to be inserted,
compute the hash code of the key
passed and locate the index using that
hash code as an index in the array.
• Use linear probing for empty location, if
an element is found at the computed
hash code.
i)insert 24
ii)insert 8
iii)insert 14
 Search Operation:

• Whenever an element is to be searched, compute the

hash code of the key passed and locate the element
using that hash code as index in the array.
• Use linear probing to get the element ahead if the
element is not found at the computed hash code.
i)search 8
ii)search 19
 Delete Operation:
• Whenever an element is to be deleted,
compute the hash code of the key passed and
locate the index using that hash code as an
index in the array.
• Use linear probing to get the element ahead if
an element is not found at the computed hash
code.
• When found, store a dummy item there to keep
the performance of the hash table intact.
Delete: 24
 Collision:
� A collision occurs when the algorithm generates the same hash for
more than one value.
� Let’s look at an example.
� Suppose we have the following list of values
� [3,2,9,11,7]
� Let’s assume that the size of the hash table is 7, and we will
use the formula (k1 % m) where m is the size of the hash
table.
� The following table shows the hash values that will be generated.
� As we can see from the above results, the values 2 and 9 have the
same hash value, and we cannot store more than one value at
each position.
� To resolve these collisions, we have some techniques known as
collision techniques.
� The following are the collision techniques:
� Open Hashing: It is also known as closed addressing.
� Closed Hashing: It is also known as open addressing.
 1. Separate chaining (Open Hashing)
• Separate chaining is one of the most commonly used
collision resolution techniques.
• It is usually implemented using linked lists. In separate
chaining, each element of the hash table is a linked list.
• To store an element in the hash table you must insert it into a
specific linked list.
• If there is any collision (i.e. two different elements have
same hash value) then store both the elements in the same
linked list.
• Example: Let us consider a simple hash
function as “key mod 7” and a sequence of
keys as 50, 700, 76, 85, 92, 73, 101
2.(Open addressing or closed hashing)
� In Closed hashing, three techniques are used to
resolve the collision:
� Linear probing
� Quadratic probing
� Double Hashing technique
� Probing:
� The other technique that is used to resolve collision is
probing. When using the probing method, if a collision
occurs, we can simply move on and find an empty slot
to store our value.
Linear probing:
� In linear probing, collision is resolved by
checking the next slot.
� h(k, i) = (h′(k) + i) mod m
� where
� i = {0, 1, ….}
� h'(k) is a new hash function
� If a collision occurs at h(k, 0), then h(k, 1) is
checked. In this way, the value of i is
incremented linearly.
• Let us consider a simple hash function as “key
mod 7” and a sequence of keys as 50, 700, 76,
85, 92, 73, 101,
• which means hash(key)= key% S, here S=size
of the table =7,indexed from 0 to [Link] can
define the hash function as per our choice if we
want to create a hash table, although it is fixed
internally with a pre-defined formula.
• Let us consider a simple hash function as “key
mod 5” and a sequence of keys that are to be
inserted are 50, 70, 76, 93.

• Step1: First draw the empty hash table which

will have a possible range of hash values from
0 to 4 according to the hash function provided.
• Step 2: Now insert all the keys in the hash
table one by one. The first key is 50. It will map
to slot number 0 because 50%5=0. So insert it
into slot number 0.
• Step 3: The next key is 70. It will map to slot
number 0 because 70%5=0 but 50 is already at
slot number 0 so, search for the next empty slot
and insert it.
• Step 4: The next key is 76. It will map to slot
number 1 because 76%5=1 but 70 is already at
slot number 1 so, search for the next empty slot
and insert it.
• Step 5: The next key is 93 It will map to slot
number 3 because 93%5=3, So insert it into
slot number 3.
 Quadratic Probing:
� It works similar to linear probing but the spacing between the
slots is increased (greater than one) by using the following
relation.

� h(k, i) = (h′(k) + i2) mod m

� where,

� i = {0, 1, … . }
• Let us consider table Size = 7, hash function
as Hash(x) = x % 7 and collision resolution
strategy to be f(i) = i2 . Insert = 22, 30, and 50.

• Step 1: Create a table of size 7.

• Step 2 – Insert 22 and 30
• Hash(22) = 22 % 7 = 1, Since the cell at index 1 is
empty, we can easily insert 22 at slot 1.
• Hash(30) = 30 % 7 = 2, Since the cell at index 2 is
empty, we can easily insert 30 at slot 2.
• Step 3: Inserting 50
• Hash(50) = 50 % 7 = 1
• In our hash table slot 1 is already occupied. So, we will
search for slot 1+12, i.e. 1+1 = 2,
• Again slot 2 is found occupied, so we will search for cell
1+22, i.e.1+4 = 5,
• Now, cell 5 is not occupied so we will place 50 in slot 5.
 Double Hashing technique:
� Double hashing is an open addressing technique which is used to
avoid the collisions.
� When the collision occurs then this technique uses the secondary hash
of the key.
� It uses one hash value as an index to move forward until the empty
location is found.
� In double hashing, two hash functions are used. Suppose h1(k) is one
of the hash functions used to calculate the locations whereas h2(k) is
another hash function.
• Insert the keys 27, 43, 692, 72 into the Hash
Table of size 7. where first hash-function
is h1​(k) = k mod 7 and second hash-function
is h2(k) = 1 + (k mod 5)

• Step 1: Insert 27
• 27 % 7 = 6, location 6 is empty so insert 27 into 6
slot.
• Step 2: Insert 43
• 43 % 7 = 1, location 1 is empty so insert 43 into 1
slot.
•Step 3: Insert 692
•692 % 7 = 6, but location 6 is already being occupied and this is a collision
•So we need to resolve this collision using double hashing.
hnew = [h1(692) + i * (h2(692)] % 7
= [6 + 1 * (1 + 692 % 5)] % 7
= 9% 7
=2
Now, as 2 is an empty slot,
so we can insert 692 into 2nd slot.
•Step 4: Insert 72
•72 % 7 = 2, but location 2 is already being occupied and this is a collision.
•So we need to resolve this collision using double hashing.
hnew = [h1(72) + i * (h2(72)] % 7
= [2 + 1 * (1 + 72 % 5)] % 7
=5%7
= 5,
Now, as 5 is an empty slot,
so we can insert 72 into 5th slot.
Applications of Hash Table:
Hash tables are implemented where
� constant time lookup and insertion is required

� cryptographic applications

� indexing data is required

� Real-world Applications:
In the real-world, hash tables are used to store
data for
� Databases

� Associative arrays

� Sets

� Memory cache
 Advantages of hash tables:
Here, are pros/benefits of using hash tables:
� Hash tables have high performance when looking up
data, inserting, and deleting existing values.
� The time complexity for hash tables is constant
regardless of the
number of items in the table.
� They perform very well even when working with large
datasets.
 Disadvantages of hash tables:

Here, are cons of using hash tables:

� You cannot use a null value as a key.
� Collisions cannot be avoided when generating keys using. hash
functions.
� Collisions occur when a key that is already in use is generated.
� If the hashing function has many collisions, this can lead to
performance decrease.
THANK YOU
 Data Structures & Algorithms

Binary Search Tree

Week
By Ms. Sabah
11
Topics
• Binary Search Trees (Searching, Inserting and Deleting in Binary Tree)
• Concept of balanced tree, complete tree, full tree and perfect tree
• AVL (Searching, Inserting and Deleting in AVL Tree)
Binary Search Trees
• A binary tree with the property such that all the nodes of the left
sub-tree of a particular node will have values less than the value of
the parent node.
• All the nodes of the right sub-tree will have values greater than the
value of the parent node.
N
• Left children < Parent < Right children
• For some trees no duplicates are allowed: adding a duplicate node
results in an error condition.
Left Right
sub- sub-
tree < tree >
n n
Example Of A Binary Search Tree
17

5 20

2 12

1 3 15
Operations Binary search trees
• Binary search trees support three main operations:
• Searching,
• Inserting and
• Deleting
Insertion

• Insertion in binary search tree includes adding a new node in a way that maintains the BST
property: for any node, all values in its left subtree are smaller, and all values in its right
subtree are greater.
• Algorithm:
• Start at the root node.
• Compare the value to be inserted with the current node's value.
• If the value is smaller, move to the left child.
• If the value is greater, move to the right child.
• Repeat steps 2-4 until you find an empty spot.
• Insert the new node at the empty spot.
Step-by-Step Insertion:
Insert the value 8 into the following BST

• Start at the root (10).

• 8 is less than 10, move to the left child (5).
• 8 is greater than 5, move to the right child (7).
• 8 is greater than 7, move to the right child of 7 (which is empty).
• Insert 8 as the right child of 7.
Delete

• Binary search tree node deletion involves removing a node and reorganizing the tree to
maintain the BST property.
• There are three cases to handle:
• Node with no children (leaf node)
• Node with one child
• Node with two children
• Algorithm:
• No Child (Leaf Node): Simply remove the node.
• One Child: Remove the node and replace it with its child.
• Two Children: Find the in-order predecessor (largest value in the left subtree) or in-order
successor (smallest value in the right subtree), replace the node's value with the
predecessor/successor, and delete the predecessor/successor.
Step-by-Step Deletion:
Delete the value 5 from the following BST:
• Start at the root (10).
• 5 is less than 10, move to the left child (5).
• Node 5 has two children. Find the in-order successor (smallest value in the right subtree of 5),
which is 7.
• Replace 5 with 7.
• Delete node 7.
Searching

• Searching in a binary search tree involves finding a node with a given value by leveraging the
BST property to reduce the number of comparisons.
• Algorithm:
• Start at the root node.
• Compare the target value with the current node's value.
• If the value is equal, the search is successful.
• If the value is smaller, move to the left child.
• If the value is greater, move to the right child.
• Repeat steps 2-5 until you find the value or reach an empty spot (unsuccessful search).
Example:
Step-by-Step Searching:
Search for the value 8 in the following BST:
• Start at the root (10).
• 8 is less than 10, move to the left child (5).
• 8 is greater than 5, move to the right child (7).
• 8 is greater than 7, move to the right child (8).
• 8 is equal to 8, search is successful.
Types of Binary Trees

• Binary trees come in various forms, each with specific properties that make them suitable for
different computational scenarios.
Full Binary Tree
• A Full Binary Tree is a type of binary tree where every node has either zero or two children. In
other words, no node has only one child.
complete binary
• In a complete binary tree, all levels are completely filled with nodes, except possibly for the last
level. On the last level, nodes are filled from left to right.
Balanced binary tree
• A balanced binary tree (or height-balanced binary tree) is a binary tree where the height of the
left and right subtrees of any node differs by at most one.
• In the image below, the height of the left side from the root node is two, and the height of the
right side is one, so the tree is balanced as the heights don't differ by more than one.
• If we added another node on the left side, the tree would become imbalanced as the height of
the left side, looking from the root node, would become three, and the height of the right side
would still be one.
Perfect binary
A perfect binary tree is a special case in which it is both a full and complete binary tree. It's the most
symmetrical type of binary tree, where all internal nodes have two children, and all leaf nodes are at the
same level (depth).
THANK YOU