Data Structures and Algorithms

Dr Mohammad Gouse Galety

Associate Professor,
Department of IT,
Samarkand International University of Technology
• Variables • Data Structures
• Variables are the names or placeholders used to hold the • Data Structures are the programmatic way of storing and
data. organizing the data so that data can be used efficiently.
• Ex: x + y = 2, x & y are the variables/placeholders for data • Ex: Arrays, files, stacks, Queues, trees, graphs, etc.,
representation.
• Classification of Data structures
• Datatypes
1. Linear Data structures
• Datatypes are defining sets of data with predefined values.
2. Non-Linear Data structures
• Ex: int a=10; float b=3.14; string a=“cue”;
• Types of Datatypes • Linear DS’s
1. System Defined Datatypes
• Sequential access to elements.
2. User-Defined Datatypes • It is not necessary to store sequentially.
• Ex: linked list, stack, queue.
• System Defined Datatypes (Primitive)
• These datatypes are defined by a system, also called • Non-Linear DS’s
primitive datatypes. • Elements are stored and accessed randomly.
• Different languages can have different sizes of primitive • Ex: Trees, Graphs.
datatypes.
• The number of bits allocated for each primitive datatype
depends on the OS, compiler, and programming language, • Abstract Datatypes (ADT’s)
for example, 2 bytes for the int type. • When the data structure/s are merged with the
• Ex: int, float, char, double, bool, etc., operation, they are called abstract datatypes.
• User Defined Datatypes (Non-Primitive) • ADT=DS + Operation
• These datatypes are defined by a user, also called non- • ADT Parts
primitive datatypes. 1. Data declaration
• Helps in providing more flexibility and comfort. 2. Operation declaration
• Ex: Student s = new Student(); • Ex: x = stack + insert 2
• Algorithm • Rate of growth
• It is a step-by-step procedure for solving a • It is defined as the rate at which running time
problem. increases as a function of input.
• All the instructions need to be • Ex: let the cost of a function ‘f’ are n5, n4, n2
unambiguous/clear. • Then the highest value, n5, is the rate of
• Ex: growth and ignoring the lower value.
1. Read the first number (a)
2. Read the second number (b)
3. Sum=a+b • Types of Analysis
4. Print sum 1. Worst case
• Judge an algorithm 2. Best case
• Is the algorithm providing a solution in a finite 3. Average case
number of steps?
• How much resources (Space & Time) are • Worst case – the algorithm takes the maximum
consumed by the algorithm in finding the time to find the solution. The algorithm has the
solution?
slowest execution (more time).
• How to compare algorithms? • Best case – the algorithm takes minimum time
• The best way to compare various algorithms is to find the solution. There is the fastest
by expressing the algorithm’s running time as a execution(less time) of the algorithm.
function of input size ‘n’ and comparing these • The average case will be between the worst
different functions corresponding to the running and best case. 3
times.
• Asymptotic Notation • Omega (Ω) Notation (Best-Case) – measures the
• Asymptotic Notation, a fascinating best-case time complexity or the best amount of
time an algorithm can take to complete.
mathematical tool, is the representation of an
algorithm's time complexity. • Theta (θ) Notation (average-case) – expresses
the lower and upper bound of an algorithm’s
• Using asymptotic analysis, we can very well
running time.
conclude an algorithm’s best-case, average-
case, and worst-case scenario.
• There are 3 types of Asymptotic Notations: • Rules for determining algorithm running
1. Big-O Notation (O) time
2. Omega Notation (Ω) • Loops – running time of the statements inside
3. Theta Notation (θ) the loop multiplied by several iterations.
• Big-O Notation (worst-case) is used to Ex: for(int i=1;i<=n;i++) //no of iterations n
measure how your program’s running time or {
space requirements grow as input size grows. Print (“Hello”); //constant time c (maybe 1sec, 2sec, etc)
• Ex: array[100];size(arr)0.22 milliseconds of }
running time.
• Ex: array[1000];size(arr)2.30 milliseconds of • Total time= no. of iterations * statement running
running time. time
• As Size grows, time also grows. • Total time= n * c
• The time complexity of the program is O(n). • Total time = cn
Where O is order. • Total time = O(n) 4
• Nested Loops – running time = product of size of all loops. • If-then-else statements – test time of
Ex: for(int i=1;i<=n;i++) //no of iterations n
{ if condition + (then part or else part
for(int i=1;i<=n;i++) //no of iterations n higher value chosen).
{
Print (“Hello”); //constant time c (maybe 1sec, 2sec, etc) • Ex: if(i==4) //constant c0
} • {
}
• Total time= c * n * n
• Return false;//constant c1 C2n
• Total time= cn2 • }
• Total time=O(n2) • Else
• {
• Consecutive Statements – in this we add complexity of
each statement. • For (int j=1;j<=n;j++)//loop,no of
• Ex: i=i+2; //statement, constant time c0 iterations n
• For(int j=1;j<=n;j++)//loop, no.of iterations n C1n
• { (Rule1)
• {
• Print(“hello”);//statement, constant time c1 • K=k+1;//constant c2
• For(int k=1;k<=n;k++)//loop, no.of iterations n
• {
• }
C2n2
• For(int l=1;l<=n;l++)//loop, no.of iterations n (Rule2) • }
• {
• Print(“CUE”); //statement, constant time c2
• Total time = c0+c1+c2n (in this case
• } c2n is higher value)
• }
• Total=c0+c1n+c2n2 • Total time = c0+c2n = O(n)
• Total=O(n2) 5
• Recursion • Backtracking
• A recursive function is one which calls • It is an algorithmic technique for
itself. solving recursively by trying to build a
• During each recursion a given problem is solution incrementally, one piece at a
broken into smaller problems. time, removing those solutions that fail
• Ex: to satisfy the constraints of the
• function x() problem at any point of time.
• { • Solutions of backtracking:
• call function x() • Shortest path in a maze.
• } • Partition an array into 2 equal sum arrays.
• public class RecursionExample {
• static int count=0;
• Knapsack problem.
• static void p(){ • N-Queen problem.
• count++;
• if(count<=5){
• System.out.println("hello "+count);
• p();
• }
• }
• public static void main(String[] args) {
• p();
• } 6
• Arrays 1. class Testarray{
• arrays store multiple elements of the same type under one 2. public static void main(String args[]){
name. 3. int a[]=new int[5];//declaration and instantiation
• An index accesses elements. 4. a[0]=10;//initialization
• Array elements are stored in sequential memory. 5. a[1]=20;
6. a[2]=70;
7. a[3]=40;
8. a[4]=50;
• Arrays can be declared in various ways in different 9. //traversing array
languages. 10.for(int i=0;i<a.length;i++)//length is the property of array
• There are two types of arrays: 11.System.out.println(a[i]);
1. Single-Dimensional Array 12.}
2. Two/Multidimensional Array
• Operations on arrays: 13.}
• Traversal
• Search
• Insert 14. class Testarray1{
• Delete 15. public static void main(String args[]){
• Sort 16. int a[]={33,3,4,5};//
• merge declaration, instantiation and initialization
17. //printing array
• Syntax to Declare an Array in Java 18. for(int i=0;i<a.length;i++)//
1. dataType[] arr; (or) length is the property of array
2. dataType []arr; (or) 19. System.out.println(a[i]);
3. dataType arr[];
20. }} 7
4. arrayRefVar=new datatype[size];
1. //Java Program to print the array elements using for-each loop 1. //Java Program to illustrate the use of multidimensional array
2. class Testarray1{ 2. class Testarray3{
3. public static void main(String args[]){ 3. public static void main(String args[]){
4. int arr[]={33,3,4,5}; 4. //declaring and initializing 2D array
5. //printing array using for-each loop 5. int arr[][]={{1,2,3},{2,4,5},{4,4,5}};
6. for(int i:arr) 6. //printing 2D array
7. System.out.println(i); 7. for(int i=0;i<3;i++){
8. } } 8. for(int j=0;j<3;j++){
• In multidimensional array the data is stored in row and column based index (also 9. System.out.print(arr[i][j]+" ");
known as matrix form). 10. }
• Syntax to Declare Multidimensional Array in Java 11. System.out.println();
1. dataType[][] arrayRefVar; (or) 12. } } }
2. dataType [][]arrayRefVar; (or)
3. dataType arrayRefVar[][]; (or) • Basic Operations in Linear array
4. dataType []arrayRefVar[]; (or) • Traversal
5. int[][] arr=new int[3][3];//3 row and 3 column • Insert
arr[0][0]=1; • Delete
arr[0][1]=2; • Algorithm
Traversing Linear Array – visiting each and every element.
arr[0][2]=3; 1. public class test { 1. Initialize the counter i=lb
arr[1][0]=4; 2. public static void main(String args[]) { 2. Loop (while i<= ub)
arr[1][1]=5; 3. //Creating an array 3. Apply s to la[i]
arr[1][2]=6; 4. // int myArray[] = new int[7]; //or 4. i=i+1
arr[2][0]=7; 5. int myArray[] = {10,20,30,40,50}; 5. End loop
arr[2][1]=8; 6. //Printing Contents using for loop
6. Exit
arr[2][2]=9; 7.
La-linear arry,
System.out.println("Contents of the array: ");
Lb-lowerbound
8. for(int i=0; i<myArray.length; i++) {
Ub-upperbound
9. System.out.println(myArray[i]);
S-search element 8
10. }}}
• Iterative Approach to find the public class Max {
static int arr[] = { 10, 324, 45, 90, 9808 };
largest element of Array // Method to find maximum in arr[]
• Algorithm static int largest()
{
• Create a local variable max and initiate int i;

it to arr[0] to store the maximum // Initialize maximum element

int max = arr[0];
among the list
• Iterate over the array // Traverse array elements from second and
// compare every element with current max
• Compare arr[i] with max. for (i = 1; i < arr.length; i++)
if (arr[i] > max)
• If arr[i] > max, update max = arr[i]. max = arr[i];
• Increment i once.
return max;
• After the iteration is over, return max }
as the required answer. // Driver code
public static void main(String[] args)
{
System.out.println("Largest in given array is "
+ largest());
}
}

9
• Find 2nd Largest Number in Array • Ask students to develop this
• Pseudo Code
• if(a[0]>a[1])
program
• {
• Max1=a[0]
• Max2=a[1]
• }
• else
• {
• Max2=a[0]
• Max1=a[1]
• }
• for(i=2 to len(a))
• {
• if(a[i]>max1)
• {
• Max2=max1
• Max1=a[i]
• }
• elseif(a[i]>max2)
• {
• Max2=a[i]
• }
• }
10
• Two Sum Problem in Data Structure • Ask students to develop this
• The data must be in the order program
• Pseudo Code
1. target=15(its your choice)
2. while(left<right)
3. {
1. cur_sum=a[left]+a[right]
2. if(cur_sum==target)
1. {
2. print(left,right)
3. }
3. else if(cur_sum<target)
1. {
2. left+ +
3. }
4. else
1. {
2. right- -
3. }
4. }
11
• Maximum sum of Sub Array • Ask students to develop this program
• max=Double.NEGATIVE_INFINITY;

12
• Maximum sum of Sub Array using • Ask students to develop this
sliding window technique. program
• Pseudo code
1. int current=0;
2. for(int i=0;i<w;i++)
3. {
1. current=current+arr[i];
4. }
5. int max=current;
6. for(int i=1;i<=n-w;i++)
7. {
1. current=current-arr[i-1]+arr[i+w-1];
2. if(current>max)
3. {
1. max=current;
4. }
8. }
9. return max;
13
• Remove Duplicate Elements in • Ask students to develop this program
Sorted Array
• Pseudo Code
1. na[0]=a[0];
2. int x=0;
3. for(int i=1;i<len(a);i++)
4. {
1. if(na[x]!=a[i])
2. {
1. x=x+1;
2. na[x]=a[i];
3. }
5. }
6. return na[0..x]

14
• Insertion in an array
import java.util.Arrays;
import java.util.Scanner;
public class ArrayInsertion {
public static void main(String args[]) {
int a[] = new int[6];
int loc=0;
int val=0;
int max=5;//max index
Scanner sc = new Scanner(System.in);
System.out.println("\nEnter 5 values in an array:");
for (int i=0;i<max;i++){
a[i]=sc.nextInt();
}
• Pseudo Code System.out.println("\nEnter the location where you
want to insert a new value:");
1. Loc=2 loc=sc.nextInt();
System.out.println("\nEnter the new values that you
2. Val=100 want to insert in an array");
val=sc.nextInt();
3. For(i=max;i>loc;i--) for (int i=max;i>loc;i--){
a[i]=a[i-1];
4. { }
a[loc]=val;
1. A[i]=a[i-1] System.out.println("\nValues in an array after
5. } inserting a new value"+val+"at the location"+loc+"are:");
for (int i=0;i<=max;i++){
6. A[loc]=val; System.out.println(a[i]);
}
7. Return array elements }
} 15
• Deletion from Array • Two Dimensional Arrays
• Algorithm • Like matrix with rows and columns.
1. Set item = la[k]
• Ex: int a[5][2]
2. Loop for i=k to n-1
3. Set la[i]=la[i+1] • In this example there are 5 rows and 2
4. End loop columns.
5. N=n-1 • Initialization of 2D Array
6. Exit • Int a[2][2] = {(1,2),(4,3)}
7. import java.util.Arrays;
8. public class test {
9. public static void main(String args[]) {
• Example of 2D Array
10.
11.
int la[] = new int[15];
la[0]=10;
1. public class 2DArray {
12. la[1]=20; 2. public static void main(String[] args) {
13. la[2]=30;
14. la[3]=40; 3. // Create 2-dimensional array.
15. la[4]=50;
16. la[5]=60; 4. int[][] twoD = new int[4][4];
17. la[6]=70;
18. int k=2; 5. // Assign three elements
class 2DArray1 { in it.
19. int n=5; public static void main(String[] args)
20. int item = la[k]; 6. twoD[0][0]{ = 1;
21.
22.
for(int i=k;i<=n-1;i++)
{
7. twoD[1][1]int[][]
= 2;arr = { { 1, 2 }, { 3, 4 } };
for (int i = 0; i < 2; i++) {
23.
24.
la[i]=la[i+1];
}
8. twoD[3][2]for=(int
3;j = 0; j < 2; j++) {
System.out.print(arr[i][j] + " ");
25.
26.
n=n-1;
System.out.println("Original Array : "+Arrays.toString(la));
9. System.out.print(twoD[0][0]
} + " ");
System.out.println();
27. System.out.println("Size of the array : "+n); 10. } }
28. }
16
29. } 11. } }
• What’s wrong with an array? • Linear Search / Sequential Search
• We must know in advance that how many elements are to be • This is the simplest method for searching.
stored in array.
• In this technique of searching, the element to be found in
• Array is static structure. It means that array is of fixed size. The
memory which is allocated to array can not be increased or
sequentially in the list.
reduced. • This method can be performed on a sorted or an unsorted
• Since array is of fixed size, if we allocate more memory than list (usually arrays).
requirement then the memory space will be wasted. And if we • In case of a sorted list searching starts from 0th (zero)
allocate less memory than requirement, then it will create element and continues until the element is found from the
problem. list or the element whose value is greater than (assuming
• The elements of array are stored in consecutive memory locations. the list is sorted in ascending order), the value being
So insertions and deletions are very difficult and time consuming. searched is reached.
• Note: To overcome the above problems , we are going to use
Linked List DS
• As against this, searching in case of unsorted list also
begins from the 0th (zero) element and continues until the
• Searching Techniques element or the end of the list is reached.
• The process of identifying or finding a particular record is called • The list given below is the list of elements in an unsorted
Searching.
array. The array contains ten elements.
• You often spend time in searching for any desired item.
• If the data is kept properly in sorted order, then searching becomes
very easy and efficient.
• What is searching?
• Searching is an operation or a technique that helps finds the place
of a given element or value in the list. • Suppose the element to be searched is '46', so 46 is
• Any search is said to be successful or unsuccessful depending upon compared with all the elements starting from the 0th
whether the element that is being searched is found or not. element, and the searching process ends where 46 is
• Some of the standard searching technique that is being followed in found, or the list ends.
the data structure is listed below: • The performance of the linear search can be measured by
• Linear Search or Sequential Search
counting the comparisons done to find out an element.
• Binary Search 17
• The number of comparison is 0(n).
• Algorithm • Binary Search
• Step 1: i=0, n=a.length, x=searching element • Binary search is a fast search algorithm with time complexity of O(log
• Step 2: if a[i]==x n).
• Step 3: print element x is found at I • This search algorithm works on the principle of divide and conquer.
• Step 4: i=i+1 • For this algorithm to work properly, the data collection should be in the
• Step 5: exit sorted form.(limitation of this search)
• Binary search looks for a particular item by comparing the middle most
• Ex: in this example I have to find the location of the item 16. item of the collection.
1. public class LinearSearch { • If a match occurs, then the index of item is returned.
2. public static void main(String[] args) { • If the middle item is greater than the item, then the item is searched in
3. // TODO Auto-generated method stub the sub-array to the left of the middle item.
4. int a[]= {4,5,10,12,16,24,33,42}; • Otherwise, the item is searched for in the sub-array to the right of the
5. int i=0; middle item.
6. int se=16;
7. int n=a.length;
8. for(i=0;i<n;i++)
9. {
10.if(a[i]==se) 4 5 10 12 16 24 33 42
11.{
12.System.out.println("Element Found!!!!"+i+"index
position");
13.}
14.}
15.}
16.}

18
Algorithm 16. else if(a[mi]<search)
1. Initialize low=0, high=size-1 17. {
2. Mid=(low+high)/2 18. li=mi+1;//new li value
3. Se=x 19. }
4. While(low<=high)
5. If se=mid 20. else
6. Return mid 21. {
7. If se>mid 22. hi=mi-1; //new hi value
8. Low=mid+1 23. }
9. Else
10. High=mid-1 24. mi=(li+hi)/2;
11. Return nil 25. }
26. if(li>hi)
12. public class BinarySearch { 27. {
13. public static void main(String[] args) { 28. System.out.println("Element not found");
14. // TODO Auto-generated method stub
29. }
15. int[] a= {2,5,7,9,12,14,16,17,19,20,24,28};//created an array and
the elements should be in sorted order 30. }
16. int search=16;//this is the searching element 31. }
17. int li=0; //lowerindex
18. int hi=a.length-1;//higher index
19. int mi=(li+hi)/2;
20. while(li<=hi)
21. {
22. if(a[mi]==search)
23. {
24. System.out.println("Element is at " + mi + " index position");
25. break;
19
26. }
• Stacks • Push operation algorithm
• It is a Abstract Data Type (ADT). 1. Stack overflow?
• Operations: push, pop the elements. i. If top=max_stack then write overflow
• It supports the LIFO (Last In First Out) feature. and exit.
• In stack you have only one entry and one exit 2. Read item
point .
• We can implement stacks by using an arrays
3. Set top=top+1
and linked lists. 4. Set stack[top]=item
• If the stack is full and you will try to insert an 5. Exit
element then it will be overflow.
• If the stack is an empty and you will try to
delete an element then it will be underflow, at • Pop operation algorithm
that time the top=-1.
1. Stack underflow?
• If you add/push one element to the stack the
top value will be increased like top=top+1. i. If top=-1 then write underflow and exit.
• If you delete/pop one element from the stack 2. Repeat steps 3 to 5 until top>0
the top value will be decreased like top=top-1. 3. Set item=stack[top]
4. Set top=top-1
5. Write deleted item
6. Exit 20
1. import java.util.*; //importing the stack 20. // returning the number at the top of the stack
class and removing it

2. public class hello { 21. System.out.println("pop => " + even.pop());

3. public static void main(String[] args) { 22. System.out.println("pop => " + even.pop());

4. // TODO Auto-generated method stub 23. System.out.println("pop => " + even.pop());

5. // Creating a Stack 24. //printing the stack

25. System.out.println("Print Stack after pop:");
6. Stack<Integer> even = new Stack<>();
26. System.out.println(even);
7. // pushing values in stack
27. // accessing the number at the top of the
8. even.push(0); stack but not removing it
9. even.push(2); 28. System.out.println("Number on top of the
10. even.push(4); stack is => " + even.peek());

11. even.push(6); 29. // checking if the stack is empty or not

12. even.push(8); 30. System.out.println("Is stack empty? Ans:" +

even.empty());
13. even.push(10); 31. // checking the position of 8 in the
14. even.push(12); stack

15. even.push(14); 32. System.out.println("Position of 8 from the

top is " + even.search(8));
16. even.push(16);
33. // check if 20 exists in the stack
17. //printing the stack
34. System.out.println("Position of 20 from the
18. System.out.println("Print Stack before top is " + even.search(20));
pop:"); 35. } 21
19. System.out.println(even); 36. }
1. public class Stack1 { 26. // Utility function to pop a top element from the
stack
2. private int arr[];
27. public int pop()
3. private int top; 28. {
4. private int capacity; 29. // check for stack underflow
5. 30. if (isEmpty())
6. // Constructor to initialize the stack 31. {
7. Stack1(int size) 32. System.out.println("Underflow\
nProgram Terminated");
8. {
33. System.exit(1);
9. arr = new int[size]; 34. }
10. capacity = size; 35.
11. top = -1; 36. System.out.println("Removing " + peek());
12. } 37.
13. 38. // decrease stack size by 1 and
(optionally) return the popped element
14. // Utility function to add an element `x` to 39. return arr[top--];
the stack
40. }
15. public void push(int x) 41. // Utility function to return the top
16. { element of the stack
17. if (isFull()) 42. public int peek()
18. { 43. {
44. if (!isEmpty()) {
19. System.out.println("Overflow\
45. return arr[top];
nProgram Terminated\n");
46. }
20. System.exit(1);
47. else {
21. } 48. System.exit(1);
22. 49. }
23. System.out.println("Inserting " + x); 50.
24. arr[++top] = x; 51. return -1;
25. } 52. } 22
53. // Utility function to return the size of the stack 67. public static void main(String[] args) {
54. public int size() { 68. // TODO Auto-generated method stub
55. return top + 1; 69. Stack1 stack = new Stack1(3);
56. } 70. stack.push(1); // inserting 1 in the stack
57. // Utility function to check if the stack is empty 71. stack.push(2); // inserting 2 in the stack
or not
72. stack.pop(); // removing the top element (2)
58. public Boolean isEmpty()
73. stack.pop(); // removing the top element (1)
59. {
60. return top == -1; // or return size() 74. stack.push(3); // inserting 3 in the stack
== 0;
75. System.out.println("The top element is " +
61. } stack.peek());
62. // Utility function to check if the stack is full or not 76. System.out.println("The stack size is " +
stack.size());
63. public Boolean isFull() {
77. if (stack.isEmpty()) {
64. return top == capacity - 1; // or return size()
== capacity; 78. System.out.println("The stack is empty");
65. } 79. }
80. else {
81. System.out.println("The stack is not empty");
82. }
83. }
84. }

23
• Applications of stacks • Expression Evaluation
• Following is the various Applications of • A stack is a very effective data structure
Stack in Data Structure: for evaluating arithmetic expressions in
1. Expression Evaluation programming languages.
2. Expression Conversion • An arithmetic expression consists of
a) Infix to Postfix operands and operators.
b) Infix to Prefix
• In addition to operands and operators,
c) Postfix to Infix
the arithmetic expression may also
d) Prefix to Infix
include parenthesis like "left
3. Backtracking
parenthesis" and "right parenthesis".
4. Memory Management
• Ex: A + (B - C)
5. Delimiter Checking
6. Reverse a Data
7. Processing Function Calls

24
• Precedence and Associativity of Operators • Associativity can be either:
• To evaluate the expressions, one needs to be • Left to Right ()
aware of the standard precedence rules for • Right to Left ()
arithmetic expression. • If associativity is Left to Right (10/2)*5=25
• Precedence of the operators come into picture • If associativity is Right to Left 10/(2*5)=1
when in an expression we need to decide • In the above case the 25 is the correct answer
which operator will be evaluating first.
because the associativity from left to right.
• Suppose if you have multiple operators in an Category Operators Associativity
Postfix
expression, then which operator will be Parenthesis/Brackets (),[],->,++,-- LR Operators

evaluated first? Unary !,~,++,--,+,-,*,& RL

• Operator with higher precedence will be Multiplicative *,/,% LR

Prefix
evaluated first. Additive +,- LR Operators
Bitwise Shift <<, >> LR
• Ex: 2+3*5 (Which one is correct?)
Relational <,<=,>,>= LR
Equality ==,!= LR
Bitwise AND & LR
Bitwise XOR ^ LR
Bitwise OR |
• Associativity of operators Logical AND &&
LR
LR
• When precedence of operators are same, and Logical OR || LR
we need to decide which operator will be Conditional ?: RL
evaluated first. Assignment =,+=,-=,*=,/=,%=,&=,^=,|=,<<=,>>= RL
• Ex: 10/2*5 Comm , LR 25
• () – parenthesis in function calls. • Evaluation of Arithmetic Expression requires two
• Ex: int x=fun(); steps:
• First, convert the given expression into special
• In the above case, “fun” operand will notation.
go to whom? X claims fun belongs to • Evaluate the expression in this new notation.
him, and () also claims fun belongs to • Notations for Arithmetic Expression
him. • There are three (3) notations to represent an
arithmetic expression:
• Note: = (assignment) operator is • Infix Notation
having less precedence as compared • Prefix Notation or Polish Notation
to (). Therefore, () belongs to fun • Postfix Notation or Reverse Polish Notation
• Infix Notation
operand and fun will be treated as a • The operator lies between the operands.
function. • Syntax: <operand> <operator><operand>
• Ex: A+B, A*B, A/B, etc.,
• In the above case as per the • In the above examples A & B are the operands and +, *, /
precedence the parenthesis will be are the operators.

evaluated first, and assignment will be • Prefix Notation/Polish Notation

• The operator comes first followed by the operands.
performed next. • Syntax:<operator><operand><operand>
• ++, -- - postfix increment/decrement • Ex: +AB, *AB, -AB, etc.,
• Postfix Notation/Reverse Polish Notation.
operator is greater than prefix • The operands comes first followed by the operator.
increment/decrement. • Syntax:<operand><operand><operator>
26
• Ex: AB+,AB*,AB/, etc.,
• Infix to Postfix conversion
• Rules
• Know the precedence of the operators
• ^ (exponential) has the highest precedence
• * & / Next precedence
• + & - has the nest precedence
• ( - has the lowest precedence
• No 2 operators with the same priority can stay together in stack.
• Lowest priority can not be placed before highest priority.
• If any operator is in between parenthesis, just pop that operator.
• Algorithm
1. Scan the infix expression from left to right.
2. If the scanned character is an operand, put it in the
postfix expression.
3. Otherwise, do the following
3. If the precedence of the current scanned operator is
higher than the precedence of the operator on top of
the stack, or if the stack is empty, or if the stack
contains a ‘(‘, then push the current operator onto
the stack.
4. Else, pop all operators from the stack that have
precedence higher than or equal to that of the
current operator. After that push the current operator
onto the stack.
4. If the scanned character is a ‘(‘, push it to the stack.
5. If the scanned character is a ‘)’, pop the stack and
output it until a ‘(‘ is encountered, and discard both
the parenthesis.
6. Repeat steps 2-5 until the infix expression is scanned.
7. Once the scanning is over, Pop the stack and add the
operators in the postfix expression until it is not empty.
8. Finally, print the postfix expression.
27
28
29
• Ex: convert the given infix expression 1. import java.util.Scanner;
(A+B)/(C*D) to postfix expression.
Input Character Stack Postfix
2. import java.util.Stack;
( ( 3. public class Infix2Postfix
A --- A
+ + A 4. {
5. public static void main(String[] args)
B + AB
) --- AB+
/
(
/
/
AB+
AB+
6. {
C
*
/
/*
AB+C
AB+C
7. Scanner scanner = new
D /* AB+CD Scanner(System.in);
) ) AB+CD*/ (postfix expression)
8. System.out.print("Enter infix expression:
");
9. String infix = scanner.nextLine();
10. String postfix = infixToPostfix(infix);
• Ex: A+B, 3*3/(4-1)+6*2  33*41-/62*+, 11. System.out.println("Postfix expression: " + postfix);
A + (B - C), (A+B)/C, (A*B) + (D-C)
12. }
30
13. public static String infixToPostfix(String infix) 34. }
14. {
35. else
15. Stack<Character> stack = new Stack<>();
16. StringBuilder postfix = new StringBuilder(); 36. {
17. for (char c : infix.toCharArray()) 37. // Operator
18. { 38. while (!stack.isEmpty() && precedence(c) <=
19. if (Character.isLetterOrDigit(c)) precedence(stack.peek()))
20. { 39. {
21. postfix.append(c);
22. }
40. postfix.append(stack.pop());
23. else if (c == '(‘) 41. }
24. { 42. stack.push(c);
25. stack.push(c);
43. }
26. }
27. else if (c == ')’) 44. }
28. { 45. while (!stack.isEmpty()) {
29. while (!stack.isEmpty() && stack.peek() != '(‘) 46. postfix.append(stack.pop());
30. {
47. }
31. postfix.append(stack.pop());
32. } 48. return postfix.toString();
33. stack.pop(); // Pop the '(' 49. } 31
1. public static int precedence(char ch)
2. {
3. switch (ch)
4. {
5. case '+':
6. case '-':
7. return 1;
8. case '*':
9. case '/':
10. return 2;
11. case '^':
12. return 3;
13. }
14. return -1;
15. }
16. } 32
• Infix to Prefix Conversion
• Algorithm
• Step 1: reverse the infix string
• Step 2: apply postfix conversion
algorithm
• Step 3: reverse the output
• Ex: a+b, (a*b)+c, a+(b*c-(d/e^f)*g
1. import java.util.*;
2. class Stack
3. {
4. int top=-1;
5. int size=0;
6. char[] arr;
7. public Stack(int size)
8. {
9. arr= new char[size];
10. this.size=size;
11. }
12. public void push(char num)
13. {
14. arr[++top]=num;
15. }
16.
17. public char pop()
18. {
19. return arr[top--];
20. }
21.
22. public char peek()
23. {
24. return arr[top];
25. }
26.
27. public char peekn(int i)
28. {
29. return arr[i];
30. }
31. public int size()
32. {
33. return top+1;
34. }
35. public boolean isEmpty()
36. {
37. return top==-1;
38. } 33
39. }
40. public class infix2pre { 79. private void getParen(char charAt) {
41. //creating 2 string and stack variable 80. while(!s.isEmpty())
42. String output=""; 81. {
43. String input=""; 82. char chx=s.pop();
44. Stack s; 83. if(chx=='(')
45. //create a function to convert infix to postfix 84. {
46. public void convert() { 85. break;
47. System.out.println("Enter Infix Expression:"); 86. }
48. //taking values from the user at the time of runtime using the scanner
87. else
class and use import java.util.Scanner;.
49. Scanner input1= new Scanner(System.in);
88. {
50. input=input1.nextLine(); 89. output=output+chx;
51. s=new Stack(input.length()); 90. }
52. for(int i=input.length()-1;i>=0;i--) 91. }
53. { 92. }
54. switch(input.charAt(i)) 93. private void getOp(char charAt,int prec) {
55. { 94. while(!s.isEmpty())
56. case '(': 95. {
57. s.push(input.charAt(i)); 96. char temp= s.pop();
58. break; 97. if(temp=='(')
59. case '+': 98. s.push(temp);
60. case '-': 99. else
61. getOp(input.charAt(i),1);//if you get any error on getOp function, at 100. {
the left click on Bulb symbol and click on create, so the getOp method
will be created 101. int prec2;
62. break; 102. if(temp=='+'|| temp=='-')
63. case '*': 103. prec2=1;
64. case '/': 104. else
65. getOp(input.charAt(i),2); 105. prec2=2;
66. break; 106. if(prec2<prec)
67. case ')': 107. s.push(temp);
68. getParen(input.charAt(i)); 108. else
69. break; 109. output=output+temp;
70. default: 110. }
71. output = output+input.charAt(i); 111. }
72. } 112. s.push(charAt);
73. } 113. }
74. while(!s.isEmpty()) { 114. public static void main(String[] args) {
75. output=s.pop()+output; 115. infix2pre i = new infix2pre();
76. } 116. i.convert();
77. System.out.println(output); 117. } 34
78. }
118. }
• Evaluation of postfix expression /
postfix to infix expression.
• Algorithm
1. Read the given expression from left to
right until the stack is empty and
repeat the steps from 2 to 3.
2. If an operand is found, push it on stack.
3. If an operator is found, then
1. Pop two top elements from stack.
2. Evaluate the expression formed by two
operands and operator.
3. Push the result back to stack.
4. Set result equal to top element of the
stack.
5. Exit.
• Ex: AB+C*D/, where A=2, B=3, C=4 and
D=5
• Ex: abc-+de-fg-h+/*
35
 • Evaluation of Prefix Expression
1. import java.util.*;
2. import java.util.Stack;
3. public class evaluations {
4.
5.
public int postfixEvaluation(String s) {
Stack<Integer> st=new Stack<Integer>();
• In this we traverse the characters of
6.
7.
int x=0,y=0;
char ch[]=s.toCharArray();//converting postfix expression to the expression from right to left.
character array
8.
9.
for(char c: ch) {
if(c>='0' && c<='9') {
• Ex: -*9+23/273
10. st.push((int) (c-'0'));//while pushing the character into the stack,
you need to convert as integer by using this code
11. }
12. else
13. {
14. y=st.pop();
15. x=st.pop();
16. switch(c) {
17. case '+':
18. st.push(x+y);
19. break;
20. case '-':
21. st.push(x-y);
22. break;
23. case '*':
24. st.push(x*y);
25. break;
26. case '/':
27. st.push(x/y);
28. break;
29. }
30. }
31. }
32. return st.pop();
33. }
34. public static void main(String[] args) {
35. evaluations a= new evaluations();
36. System.out.println(a.postfixEvaluation("23+4*5/"));
37. }
36
38. }
 • Queue
1. import java.util.*;
2. import java.util.Stack;
3. public class evaluations1 {
4.
5.
public int prefixEvaluation(String s) {
Stack<Integer> st=new Stack<Integer>(); • Q is similar to the Stack (LIFO), but
the concept is FIFO (First In First
6. int x=0,y=0;
7. //converting prefix expression to character array

Out).
8. for(int i=s.length()-1;i>=0;i--)
9. {
10. char ch=s.charAt(i);
11.
12.
if(ch>='0' && ch<='9') {
st.push((int) (ch-'0'));//while pushing the character into the stack, • We can implement Q’s using
Arrays or Linked Lists.
you need to convert as integer by using this code
13. }
14. else
15.
16.
{
y=st.pop();
• In Q’s we have 2 open ends, one
17.
18.
x=st.pop();
switch(ch) { for entry , another one for exit.
19. case '+':
20.
21.
st.push(x+y);
break;
• You need to insert an element
22.
23.
case '-':
st.push(x-y);
inside the Q from rear side only.
24. break;
25. case '*':
26. st.push(x*y);
27. break;
28. case '/':
29. st.push(x/y);
30. break;
31. }
32. }
33. }
34. return st.pop();
35. }
36. public static void main(String[] args) {
37. evaluations1 a= new evaluations1();
38. System.out.println(a.prefixEvaluation("+23"));
39. }
40. } 37
• Application of Queue Data Structure
• Queues are used for any situation where you
want to maintain a First-in-first-out order on
some entities efficiently.
• In a multitasking operating system, the CPU
cannot run all jobs simultaneously, so jobs
must be batched up and scheduled according
to some policy. Again, a queue might be a
suitable option in this case.
• Operation on a queue
• Insert an element in a queue. (enqueue)
• Delete an element from the queue. (dequeue)

• Insertion of an element
• Algorithm
1. Initialize F=-1, R=-1
2. if queue is full(R=Max. Size)
3. return overflow
4. endif
5. rear ← rear + 1
6. queue[rear] ← data
7. return true
8. Exit

38
• Deletion of an element
• Algorithm
1. if queue is empty (F<0 or F==R)
2. return underflow
3. end if
4. data = queue[front]
5. front ← front + 1
6. return true
7. Exit

39
1. public class Queue {
40. // delete element from the queue
2. int SIZE = 5;
3. int items[] = new int[SIZE]; 41. int deQueue() {
4. int front, rear;
42. int element;
5. Queue() { 43. // if queue is empty
6.
7.
front = -1;
rear = -1;
44. if (isEmpty()) {
8. } 45. System.out.println("Queue is
empty");
9. // check if the queue is full
10. boolean isFull() { 46. return (-1);
11. if (front == 0 && rear == SIZE - 1) { 47. }
12. return true;
13. } 48. else {
14.
15. }
return false;
49. // remove element from the front of
queue
16. // check if the queue is empty 50. element = items[front];
17. boolean isEmpty() {
18. if (front == -1) 51. // if the queue has only one
19. return true; element
20. else
21. return false;
52. if (front >= rear) {
22. } 53. front = -1;
23. // insert elements to the queue
54. rear = -1;
24. void enQueue(int element) { 55. }
25. // if queue is full
26. if (isFull()) { 56. else {
27. System.out.println("Queue is full"); 57. // mark next element as the
28. }
29. else {
front
30. if (front == -1) { 58. front++;
31. // mark front denote first element of queue
32. front = 0;
59. }
33. } 60. System.out.println( element + "
34. rear++;
Deleted");
35. // insert element at the rear
36. items[rear] = element; 61. return (element);
37.
38. }
System.out.println("Insert " + element);
62. } 40
39. } 63. }
64. // display element of the queue 81. public static void main(String[]
args) {
65. void display() {
82. // create an object of Queue class
66. int i; 83. Queue q = new Queue();
67. if (isEmpty()) { 84. // try to delete element from the
queue
68. System.out.println("Empty Queue");
85. // currently queue is empty
69. } 86. // so deletion is not possible
70. else { 87. q.deQueue();
71. // display the front of the queue 88. // insert elements to the queue
89. for(int i = 1; i < 6; i ++) {
72. System.out.println("\nFront index-> 90. q.enQueue(i);
" + front);
91. }
73. // display element of the queue 92. // 6th element can't be added to queue because queue
is full
74. System.out.println("Items -> "); 93. q.enQueue(6);
75. for (i = front; i <= rear; i++) 94. q.display();
95. //deQueue removes element enteredfirsti.e. 1
76. System.out.print(items[i] + " ");
96. q.deQueue();
77. // display the rear of the queue 97. // Now we have just 4 elements
78. System.out.println("\nRear index-> " 98. q.display();
+ rear); 99. }
79. } 100.}
80. }
41
• Circular Queue • Applications of Circular Queue
• There was one limitation in the array implementation of
Queue. • The circular Queue can be used in the
• If the rear reaches to the end position of the Queue, then following scenarios:
there might be possibility that some vacant spaces are left
in the beginning which cannot be utilized. • Memory management: The circular
• So, to overcome such limitations, the concept of the queue provides memory management. As
circular queue was introduced. we have already seen that in linear queue,
the memory is not managed very
efficiently. But in case of a circular queue,
the memory is managed efficiently by
placing the elements in a location which is
unused.
• CPU Scheduling: The operating system
also uses the circular queue to insert the
processes and then execute them.
• Traffic system: In a computer-control
traffic system, traffic light is one of the
best examples of the circular queue. Each
light of traffic light gets ON one by one
after every ‘j’ interval of time. Like red
light gets ON for one minute then yellow
light for one minute and then green light.
42
After green light, the red light gets ON.
1. public class cQueue { 36. for(int i=0;i<size; i++)
2. //creating following variables 37. {
3. int queue[] = new int[5]; // creating an array called queue with 38. System.out.print(queue[(front+i)%5]+ " ");
size 5
39. }
4. int size; //default value of size,front,rear will be 0 like
size=0,front=0,rear=0 40. System.out.println();
5. int front; 41. //to show the elements of the array
6. int rear;
7. //creating a enqueue() method to insert an element inside the 42. for (int n: queue)
queue 43. {
8. public void enqueue(int data) 44. System.out.print(n + " ");
9. { 45. }
10. if(!isfull())
46. System.out.println();
11. {
47. }
12. //in empty Q, whenever you insert the 1st element, it will be the
front, and rear (front=0, rear=0) 48. public int getsize()
13. queue[rear]=data; 49. {
14. //in the above case after adding an element we should move rear 50. return size;
value to next location using below 51. }
15. rear=(rear+1)%5;//with this you can perform circular Q insertion 52. public boolean isempty()
16. //after adding an element the size value also to be increased 53. {
17. size=size+1;
54. return size==0;
18. }
55. }
19. else
56. public boolean isfull()
20. System.out.println("Q is Full");
21. } 57. {
22. public int dequeue() 58. return size==5;
23. { 59. }
24. int data=queue[front];//here i am assigning the front value to 60. }
data variable 61. public class Runner
25. //now we are moving front value to the next value like below 62. {
26. if (!isempty()) 63. public static void main(String[] args)
27. { 64. {
28. front = (front + 1)%5;//with this you can perform circular Q
deletion
65. cQueue q = new cQueue();
29. //after deleting an element from the Q, the size also should to be 66. q.enqueue(5);
reduced. 67. q.enqueue(10);
30. size = size -1; 68. q.enqueue(15);
31. } 69. q.enqueue(20);
32. else 70. q.enqueue(25);
33. System.out.println("Q is Empty"); 71. q.dequeue();
34. return data; 72. q.enqueue(30);
35. }
73. q.dequeue();
36. public void show()
74. q.enqueue(35);
37. {
38. //to show all the elements available inside the Q use the
75. q.show(); 43
following way 76. }
77. }
• Double Ended Queue (DEQueue) • Priority Queue
• In this type of ‘Q’ insertion and • Each element is inserted
deletion can be performed at or deleted based on
both ends. their priority.
• Front also can be used for • Higher priority element
is greater than lower
insertion and rear pointer can be
priority element.
used for deletion.
• If two elements have
same priority in this case
apply First Come First
Service (FCFS) basis.
• Types of priority queues
• Ascending order priority
queue
• Types of DEQueues • In this lower priority
element will be given
• Input restricted Queue higher priority.
• Deletion can be performed at both • Descending order
ends.
priority queue
• Insertion at one end (rear) • In this higher priority
• Output restricted Queue element will be given
• Deletion at one end (front) higher priority.
• Insertion can be performed at both
ends.
44
• Ask the students to write a program • Understanding Call Stack /
to generate 4,3,2 numbers using the Processing function call/runtime
recursion and loop (for) and to stack.
know the difference between them.
• Tail(x) • P(x)
•{ • {
• int i;
• if(x<=1)
• return x • for(i=x;i>1;i--)
• else •{
• print(i)
•{
• print(x) •}
• Tail(x-1) •}
•}
•}
• Note: Space Complexity is high in
recursion. 45
• Linked lists
• A linked list is a sequence of data structures connected via links.
• A Linked List is a sequence of links containing items. Each link contains a connection
to another link. Linked lists are the second most-used data structure after arrays.
• Following are the important terms to understand the concept of Linked List.
• Link − Each link of a linked list can store data, which is called an element.
• Next − Each link of a linked list contains a link to the next link called Next.
• LinkedList − A Linked List contains the connection link to the first link, First.
• Linked List Representation
• A linked list can be visualized as a chain of nodes, where every node points to the
next node.

• As per the above illustration, the following are the important points to be considered.
• Linked List contains a link element called first.
• Each link carries a data field(s) and a link field called next.
• Each link is linked with its next link using its next link.
• The last link carries a null link to mark the list’s end. 46
• Types of Linked List • Simple way to create a linked list
• Following are the various types of linked using “import java.util.LinkedList;”
lists. 1. import java.util.LinkedList;
• Simple Linked List − Item navigation is 2. public class Linky {
forward only. 3. public static void main(String[] args) {
• Doubly Linked List − Items can be navigated 4. LinkedList linky = new LinkedList();
forward and backward. 5. linky.add("A");
• Circular Linked List − The last item links to 6. linky.add("B");
the first element as the next, and the first 7. linky.add("C");
element has a link to the last element as the 8. System.out.println(linky);
previous. 9. }
10. }
• Basic Operations
• Following are the basic operations 11. import java.util.LinkedList;
12. public class Linky {
supported by a list. 13. public static void main(String[] args) {
• Insertion − Adds an element at the beginning 14. LinkedList linky = new LinkedList();
of the list. 15. linky.add("A");
• Deletion − Deletes an element at the 16. linky.add("B");
beginning of the list. 17. linky.add("C");
• Display − Displays the complete list. 18. System.out.println(linky);
• Search − Searches an element using the given 19. linky.remove();//it removes from font
key. 20. System.out.println(linky);
• Delete − Deletes an element using the given 21. } 47
22. }
1.
2.
import java.util.LinkedList;
public class Linky {
• Other way to create a simple linked list
1. public class LLIntroduction {
3. public static void main(String[] args) {
2. Node head;//head of list
4. LinkedList linky = new LinkedList(); 3. //linked list node
5. linky.add("A"); 4. static class Node{
6. linky.add("B"); 5. int data;
7. linky.add("C"); 6. Node next;
8. System.out.println(linky); 7. //constructor to create a new node
9. linky.remove();//it removes from font 8. Node(int d){
10. System.out.println(linky); 9. data=d;
10. next=null;
11. linky.clear();//it removes all the nodes
11. }
12. System.out.println(linky);
12. }
13. } 13. public static void main(String[] args) {
14. } 14. // TODO Auto-generated method stub
15. //empty linked list
15. import java.util.LinkedList; 16. LLIntroduction emptyList = new LLIntroduction();
16. public class Linky { 17. //creating nodes
17. public static void main(String[] args) { 18. emptyList.head=new Node(10);
19. Node secondNode= new Node(16);
18. // TODO Auto-generated method stub
20. Node thirdNode=new Node(21);
19. LinkedList linky = new LinkedList();
21. //linking the created nodes with empty linkedlist
20. linky.add("A");
22. emptyList.head.next=secondNode;
21. linky.add("B"); 23. secondNode.next=thirdNode;
22. linky.add("C"); 24. emptyList.printLinkedList();
23. System.out.println(linky); 25. }
24. //linky.remove();//it removes from font 26. //method for printing the linked list items
25. //System.out.println(linky); 27. private void printLinkedList() {
26. //linky.clear();//it removes all the nodes 28. Node tempNode=head;
29. while(tempNode!=null) {
27. //System.out.println(linky);
30. System.out.println(tempNode.data+" ");
28. System.out.println(linky.getFirst());
31. tempNode=tempNode.next;
29. System.out.println(linky.getLast());
32. }
30. } 33. } 48
31. } 34. }
• Linked List-Insert Node (At Front, At Center, At End) • How to delete an element from linked list-
• Add the below ”insertAtFront()” method code after the ”printLinkedList()” method
• //method for inserting a node at front
• Whenever you are trying to delete an element from a linked
• private void insertAtFront(int datavalue) { list you suppose to use index value.
• //create a new node
• Node newNode = new Node(datavalue); • Create a method like deleteAt(int index).
•
•
newNode.next=head;//connecting new node to the existing head node
head=newNode;//now newnode became head
public void deleteAt(int index)
• }
{
• Add the below code in “main()” method and run. //in case if you want to delete 1st node/element (which is head
• emptyList.insertAtFront(5); element) use the following code
• emptyList.printLinkedList();
if(index==0)
• Add the below “insertAt()” method code after the
“insertAtFront()” method
{
• private void insertAt(int index, int datavalue) { head=head.next;
• Node n=head;
• Node newNode = new Node(datavalue); }
else // if you want to delete other elements use the following
• for(int i=0;i<index-1;i++) {
• n=n.next;
• } logic. (you need to traverse up to that element)
• newNode.next=n.next;
• n.next=newNode; {
•
• }
Add the below code in “main()” method and run
Node n= head;// creating new node 'n' and assigning the 'head'
• emptyList.insertAt(1, 12); to 'n'
• emptyList.printLinkedList();
Node n1=null;
• Add the below “insertAtEnd()” method code after the “insertAt()” method for(int i=0;i<index-1;i++)// this loop is used to traverse before
• private void insertAtEnd(int datavalue) {
• //create a new node the given location index value
•
•
Node newNode = new Node(datavalue);
Node end = head;
{
•
•
while(end.next!=null) {
end=end.next;
n=n.next;
• } }
• end.next=newNode;
• } n1=n.next;
• Add the below code in “main()” method and run.
n.next=n1.next;
• emptyList.insertAtEnd(29); }
• emptyList.printLinkedList("\nAfter Insertion at end"); 49
}
• length of the linked list • Linked list Node creation algorithm
• Add the below “findLength()” method code after the • Step1 : initialize Node class
“deleteAt()” method • Step2: initialize data
• private int findLength() {
•
•
Node current = head;
int count=0;
• Step3: initialize next
•
•
while (current!=null) {
current=current.next;
• Step4: initialize Node constructor
•
•
count=count+1;
}
• Step5: set data=data
•
•
return count;
}
• Step6: set next=null
• Add the below code in “main()” method and run. • Step7: exit
• int len=emptyList.findLength();
• System.out.println("\nthe length of the linked list:"+len);
• Traverse a linked list algorithm
• Search of the node • Step1: initialize set tempnode=head
• Add the below “searchNode()” method code after • Step2: repeat steps 3 to 4 while(tempnode!=null)
the “findLength()” method • Step3: write tempnode.data
• private boolean searchNode(int value) {
•
•
Node temp= head;
while(temp!=null) {
• Step4: set tempnode=tempnode.next
•
•
if(temp.data==value) {
return true;
• End of loop
•
•
}
temp=temp.next;
• Step5: exit
• }
•
•
return false;
}
• Insert a node at the beginning of LL - algorithm
• Add the below code in “main()” method and run. • Step1: initialize head
•
•
boolean found=emptyList.searchNode(16);
if(found) {
• Step2: initialize set newnode=datavalue
•
•
System.out.println("Node is Available");
}
• Step3: initialize set newnode.next=head
•
•
else
{
• Step4: initialize set head=newnode
•
•
System.out.println("Node Not Available");
}
• Step5: exit 50
• Insert a node at the given location algorithm • Delete node using the given location algorithm
• Step1: initialize set n=head • Step1: initialize set n=head
• Step2: initialize set n1=null
• Step2: initialize set newnode=datavalue
• Step3: initialize set index (based on given index)
• Step3: repeat steps 3 to 4 while(i<index-1) • Step4: repeat steps 3 to 4 while(i<index-1)
• Step4: initialize set n=n.next • Step5: set n=n.next
• End of loop • End of loop
• Step5: set newnode.next=n.next • Step6: set n1=n.next
• Step6: set n.next=newnode • Step7: n.next=n1.next
• Step8: exit
• Step7: exit
• Length of the linked list algorithm
• Insert a node at the end algorithm • Step1: initialize set current=head
• Step1: initialize set newnode=datavalue • Step2: initialize set count=0
• Step2: initialize set end=head • Step3: repeat steps 3 to 5 while(current!=null)
• Step3: repeat steps 3 to 4 while(end.next!=null) • Step4: set current=current.next
• Step4: set end=end.next • Step5: set count=count+1
• End of loop
• End of loop
• Step6: return count
• Step5: set end.next=newnode • Step7 exit
• Step6: exit
• Searching a node algorithm
• Delete front/starting/head node algorithm • Step1: initialize set temp=head
• Step1: initialize set temp=head • Step2: repeat steps 3 to 4 while(temp!=null)
• Step2: initialize key (based on node value/data) • Step3: if temp.data==value
• Return true
• Step3: initialize set prev=null
• Step4: set temp=temp.next
• Step4: if(temp!=null && temp.data==key) • End of loop
• Step5: set head=temp.next • Return false
• Step6: exit 51
• Step5: exit
• Doubly Linked List • Doubly Linked List Representation
• It is called 2 way linked list.
• A doubly linked list is a variation of a
Linked list in which navigation is
possible in both directions, forward • As per the above illustration, following
and backward, easily compared to a are the important points to be
Single Linked List. considered:
• Following are the important terms to • Head points to the first node, tail points
understand the concept of a doubly to the last node.
linked list. • Each node carries a data field and two link
• Data − Each data/link of a linked list can fields called next and prev.
store data called an element. • Each node is linked with its next link using
• Next − Each link of a linked list contains a its next link.
link to the next link called Next. • Each node is linked with its previous link
• Prev − Each link of a linked list contains a using its previous link.
link to the previous link called Prev. • The last node carries a link as null to mark
the end of the list.

52
 46. while(temp!= null)
1. import java.util.List; 25. public void
47. {
insertFirst(int value) {
2. public class DLL { 26. //create a list node
48. System.out.print(temp.data + "-->");
49. temp=temp.next;
3. ListNode head; like below and assign the
50. }
value to it
4. ListNode tail; 51. System.out.println("Null");
27. ListNode newNode = 52. }
5. private int length; new ListNode(value); 53. public void displayBackward() {
6. public DLL() { 28. if(isEmpty())//here 54. {
im checking DLL is empty 55. if (tail == null) {
7. this.head = null; or not 56. return;
8. this.tail = null; 29. { 57. }
30. tail=newNode; 58. ListNode temp = tail;
9. this.length = 0; 59. while (temp != null) {
31. }
10. } 60. System.out.print(temp.data + "-->");
32. else
11. private class ListNode { 33. 61. temp = temp.previous;
{ 62. }
12. private int data; 34. 63. System.out.println("Null");
head.previous=newNode 64. }
13. private ListNode next; ; 65. }
14. private ListNode previous;
35. } 66. public static void main (String[]args){
15. public ListNode(int data)
36.{ 67. DLL dll = new DLL();
newNode.next=head; 68. dll.insertFirst(5);
16. this.data = data; 69. dll.insertFirst(10);
37. head=newNode;
17. } 38. length=length+1;
70. dll.insertFirst(15);
71. dll.insertFirst(20);
18. } 39. } 72. dll.displayForward();
19. public boolean isEmpty() 40.
{ public void 73. dll.displayBackward();
displayForward() { 74. }
20. return length == 0; 41. if(head==null) 75. }
21. } 42. {
22. public int length() { 43. return;
44. }
23. return length;
45. ListNode temp =
24. } head; 53
DLL implementation • Creating a constructor for a DLL class to assign the
Create a new class DoublyLinkedList.java and represent the node as values of the instance variables like below in
follows: DoublyLinkedList.java:
public class DoublyLinkedList {
//in this case we need a list node class(this is inner class), //Creating a constructor for a DLL class
in SLL, I created node.java separately, but here im creating to assign the values of the instance
inside the DLL.java only
private class ListNode
variables
{ //when we initialize the DLL, the list
//in this node there are 3 components, previous, data, next,
here i am declaring those 3 components
will be empty
private int data; public class DoublyLinkedList {
private ListNode next;
private ListNode previous; public DoublyLinkedList()
//create a constructor to take data part
public ListNode(int data) {
{
this.data = data; this.head=null;
}
} this.tail=null;
}
this.length=0;
Like, in Singly linked list we are representing the node of DLL.
}
• In DLL we have head & tail pointers, so we create two }
instance variables of ListNode like below in • Create a method isempty() as below in DLL.java class to
DoublyLinkedList.java: check whether DLL is empty or not:
public class DoublyLinkedList { public boolean isempty()
{
//we create two instance variables of ListNode return length==0; //in this case if lenght=0 or head=null it will say
DLL is empty.
private ListNode head;//head will be the 1st
}
node
private ListNode tail;//tail will be the last • Create a method length() as below in DLL.java class to
node return back the length of the DLL:
//create a variable length to hold the number public int length()
{
of elements in the DLL
return length; 54
private int length; }
• How to insert node at the beginning of a • to save time and minimize the complexity of
Doubly Linked List in Java ? the student I’m writing the main method
• Algorithm inside the DLL class only
ListNode newNode=new ListNode(value); public class DoublyLinkedList
if(isempty()) {
{ public static void main (String[] args)
{
tail=newNode; DoublyLinkedList dll = new DoublyLinkedList();//created an object dll of
} DoublyLinkedList
dll.insertfirst(1);
else dll.insertfirst(10);
{ dll.displayforward();
}
head.previous=newNode;
}
}
newNode.next=head; • Create a method displayforward()to display
Head=newNode;
the list of elements in forward direction and
• Create a method in DLL.java class to insert a node at write DLL.java class:
first like below: public void displayforward()
public void insertfirst(int value)
{
{
//create a list node like below and assign the value to it if(head==null)
ListNode newNode = new ListNode(value); {
if(isempty())//here im checking DLL is empty or not return;
{ }
tail=newNode;
ListNode temp = head;
}
else while(temp!= null)
{ {
head.previous=newNode; System.out.print(temp.data + "-->");
} temp=temp.next;
newNode.next=head;
}
head=newNode;
length=length+1; System.out.println("Null");
} } 55
• Create a method displaybackward()to display the list of • How to insert node at the end of a Doubly Linked List?
elements in backward direction and write DLL.java • Algorithm
class: 1. ListNode newNode = new ListNode(value);
2. if (isempty())
public void displaybackward()
3. {
{ 4. head=newNode;
if(tail==null) 5. }
{ 6. Else
7. {
return;
8. tail.next=newNode;
} 9. newNode.previous=tail;
ListNode temp=tail; 10. }
11. tail=newNode;
while(temp!=null)
{
public void insertlast(int value)
System.out.print(temp.data + "-->");
{
temp=temp.previous; ListNode newNode = new ListNode(value);
} if(isempty())
System.out.println("Null"); {
head=newNode;
}
}
else
{
tail.next=newNode;
newNode.previous=tail;
}
tail=newNode;
}

56
• How to delete first node in a Doubly Linked public ListNode delfirst()
{
List? if(isempty())
• Algorithm {
if(isempty()) throw new NoSuchElementException();//import like this
-- import java.util.NoSuchElementException;
{ }
Raise Exception; ListNode temp=head; //creating temp variable like a
ListNode and assigning head to it
}
if(head==tail)//if it is true, DLL will be having
ListNode temp= head; only one node
if(head==tail) {
{ tail=null;
}
tail=null;
else
}
{
else head.next.previous=null;
{ }
head.next.previous=null; head=head.next;
} temp.next=null;

head=head.next; length=length-1;//after deleting the element, the

length also come down
temp.next=null; return temp;
return temp; }
57
• How to delete last node in a Doubly public ListNode dellast()
Linked List {
if(isempty()) {
• Algorithm
throw new NoSuchElementException();
if(isempty())
}
{
ListNode temp=tail;
Raise Exception;
if(head==tail)
}
{
ListNode temp= tail;
head=null;
if(head==tail)
}
{
else
head=null;
{
}
else tail.previous.next=null;

{ }

tail.previous.next=null; tail=tail.previous;

} temp.previous=null;
tail=tail.previous; length=length-1;
temp.previous=null; return temp;
return temp; }
58
• Circular Linked List • As per the image illustration, following
• Circular Linked List is a variation of Linked list in are the important points to be
which the first element points to the last element
and the last element points to the first element. considered.
• Both Singly Linked List and Doubly Linked List can be • The last link's next points to the first link of
made into a circular linked list. the list in both cases of singly as well as
doubly linked list.
• Singly Linked List as Circular • The first link's previous points to the last of
• In singly linked list, the next pointer of the last node the list in case of doubly linked list.
points to the first node. • Basic Operations
• insert − Inserts an element at the start of
the list.
• delete − Deletes an element from the start
of the list.
• display − Displays the list.

59
1. public class CircularSLL { 24. public void createcsll()
25. {
2. static ListNode last; 26. //creating nodes
3. static ListNode head; 27. ListNode first=new ListNode(10);
4. private int length; 28. ListNode second=new ListNode(20);
29. ListNode third=new ListNode(30);
5. public CircularSLL() { 30. ListNode fourth=new ListNode(40);
6. last=null; 31. //inter connect the above 4 nodes like below
7. length=0; 32. first.next=second;
33. second.next=third;
8. } 34. third.next=fourth;
9. private class ListNode{ 35. fourth.next=first;
36. last=fourth;
10. private ListNode next;
37. head=first;
11. private int data; 38. }
12. public ListNode(int data){ 39. public static void show()
40. {
13. this.data=data;
41. ListNode temp = head;
14. } 42. while(temp.next !=head)
15. } 43. {
44. System.out.print(temp.data + " ");
16. public int length()
45. temp=temp.next;
17. { 46. }
18. return length; 47. System.out.println(temp.data);//printing last node
48. }
19. } 49. public static void main(String[] args) {
20. public boolean isempty() 50. // TODO Auto-generated method stub
21. { 51. CircularSLL csll = new CircularSLL();
52. csll.createcsll();
22. return length == 0; 53. csll.show();
23. } 54. }
55. }

60
• Doubly Linked List as Circular • This search algorithm works on the searching
• In doubly linked list, the next pointer of the position of the required value.
last node points to the first node and the • For this algorithm to work properly, the data
previous pointer of the first node points to the collection should be in a sorted form and
last node making the circular in both equally distributed.
directions. • Binary search has a huge advantage of time
complexity over linear search.
• Assignment to the students • Linear search has worst-case complexity of
Ο(n) whereas binary search has Ο(log n).
• Interpolation Search
• Interpolation search is an improved variant of
binary search.
• Interpolation search is a variation of Binary
search, meaning it is also a divide and conquer
algorithm how it differs is that rather than
dividing the input array into two equal parts it
tries to divide the array in such a way that the
position is nearer to the searched element.

61
• Points to be noted
1. public class InterpolationSearch {
2. public static void main(String[] args) {
3. int[] a={1,2,3,4,5,6,7,8,9};
• Elements to be sorted and uniformly 4. int index=is(a,1);
distributed. 5. if (index!=-1){
6. System.out.println("Element fount at
• Searching element (se)=???? index:"+ index);
7. }
• Start index(si)=0; 8. else{
9. System.out.println("Element not found");
• End index(ei)= size-1; 10. }
• Where size= number of elements in the array 11. }
12. private static int is(int[] a, int value) {
‘a’. 13. int high=a.length-1;
14. int low=0;
• Algorithm 15. while(value>=a[low] && value<=a[high] &&
low<=high){
• While(si<=ei && se>=a[si] && se<=a[ei]) 16. int
p=low+(high-low)*(value-a[low])/(a[high]-a[low]) ;
• Position(pos)=si+((si-ei)/(a[ei]-a[si]))*(se- 17. System.out.println("probe:"+p);
a[si]) 18. if(a[p]==value){
19. return p;
• If(a[pos]==se) , then the element is found 20. }
• If(se>a[pos]) , then make si=pos+1; 21.
22.
else if(a[p]<value){
low=p+1;
• If(se<a[pos]), then make ei=pos-1; 23. }
24. else{
• End of loop 25. high=p-1;
26. }
27. }
• Ask the students to work with the following dataset: 28. return -1;
29. } 62
1,2,4,8,16,32,64,128,256,1024 30. }
• Hashing Technique
• This technique is used to search the elements.
• Linear search will randomly take elements and O(n) time.
• Binary search will take elements in sorted order and take O(logn)
time.
• Hashing techniques, unlike linear and binary search, take the
elements randomly and operate in O(1) time, offering a significant
advantage in terms of efficiency.
• It stores the element in the array’s index equivalent to the value.
• This means that if element 8 wants to be inserted, it will be
stored in index 8 of an array.
• If you want to search for any element, you can directly visit the
index of that element.
• In this case, the search time is O(1) because you reach the search
element directly.
• You will face a problem whenever you want to insert an element
whose values are greater than the size of the array.
• For example, the size of the array is 12, but you want to insert 20.
In the array, we don’t have 20 indexes to store 20 elements.
• We can solve the above problem by using the properties of the
hashing function like the below:
1. One to one – h(x)=x
2. Many to one – h(x)=x % size of an array(hash table)
• We have different hash functions like
1. K mod 10,
2. K mod n,
3. mid square, and 63
4. folding method.
• Collision resolution methods
• Open hashing
• chaining
• Closed hashing
• Linear probing
• Quadratic probing

64
• Hash-Table • Linked HashMap
• Hash--table in Java is an in-built class; it creates a hash table by mapping
keys to values. • The Map interface is implemented as a Hashtable and
• Hash-Table implements the Map interface and inherits from the Linked list in Java's LinkedHashMap class.
Dictionary class. 1. import java.util.*;
2. public class LinkedHashMap1{
1. import java.util.*;
2. public class HT { 3. public static void main(String args[]){
3. // imports useful collection framework, collection classes, classes 4. LinkedHashMap<Integer,String> LHM=new
related to date and time, event model, internationalization, and LinkedHashMap<Integer,String>();
miscellaneous utility classes. etc
4. public static void main(String args[]){
5. /* Hashtable() constructor is used to declare an empty
5. LHM.put(16,"Virat");
Hashtable of default size and load factor below, we have used the 6. LHM.put(1,"Alex");
same for creating a hashtable named HT */ 7. LHM.put(40,"Ishika");
6. Hashtable<Integer,String> HT=new Hashtable<Integer,String>();
7. //Put(key,value) method helps us to store data in hashtable
8. LHM.put(5,"Sonu");
8. HT.put(16,"Umid"); 9. LHM.put(3,"Mrinalini");
9. HT.put(1,"Max"); 10. LHM.put(38,"John");
10. HT.put(40,"Sim"); 11.
11. HT.put(5,"Dildora");
12. HT.put(3,"Diyor");
12. System.out.println("Does it maintain insertion
13. HT.put(38,"Johon");
order? ....");
14. /* Now we loop through the hashtable HT and print each key-value
pair one by one 13. for(Map.Entry m:LHM.entrySet()){
15. */
14. System.out.println(m.getKey()+"
16. for(Map.Entry m:HT.entrySet()){
17. System.out.println(m.getKey()+" "+m.getValue());
"+m.getValue());
18. } 15. }
19. } 16. }
20. } 17. }
65
• Sorting Techniques • Bubble Sort Algorithm
• Sorting refers to arranging data in a particular • Bubble sort is a simple sorting
format. Sorting algorithm specifies the way algorithm.
to arrange data in a particular order. Most
common orders are in numerical or • This sorting algorithm is comparison-
alphabetical order. based algorithm in which each pair of
• The importance of sorting lies in the fact that adjacent elements is compared, and
data searching can be optimized to a very the elements are swapped if they are
high level, if data is stored in a sorted not in order.
manner. • This algorithm is not suitable for large
• Sorting is also used to represent data in more data sets as its average and worst-case
readable formats. complexity are of Ο(n2) where n is the
• Following are some of the examples of number of items, O is the order (Big
sorting in real-life scenarios −
O) , it is used to check the complexity
• Telephone Directory − The telephone directory
stores the telephone numbers of people sorted like avg, best, worst cases.
by their names, so that the names can be • How Bubble Sort Works?
searched easily.
• We take an unsorted array for our
• Dictionary − The dictionary stores words in an
alphabetical order so that searching of any word example. Bubble sort takes Ο(n2) time so
becomes easy. we're keeping it short and precise.
66
• Bubble sort starts with very first • The new array should look like this −
two elements, comparing them to
check which one is greater.
• Next, we compare 33 and 35. We
find that both are in already sorted
positions.
• In this case, value 33 is greater • Then we move to the next two
than 14, so it is already in sorted values, 35 and 10.
locations. Next, we compare 33 • We know then that 10 is smaller 35.
with 27. Hence, they are not sorted.

• We find that 27 is smaller than 33 • We swap these values. We find that

and these two values must be we have reached the end of the
swapped. array. After one iteration, the array
should look like this −
67
• To be precise, we are now showing • Algorithm
how an array should look like after • We assume list is an array of n
each iteration. After the second elements.
iteration, it should look like this − • We further assume that swap function
swaps the values of the given array
elements.
• Notice that after each iteration, at begin BubbleSort(list)
least one value moves at the end. for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
• And when there's no swap required,
end if
bubble sorts learns that an array is
end for
completely sorted.
return list
end BubbleSort

68
public class BubbleSort { import java.util.*;
public static void main(String[] args) { public class BubbleSort {
int[] a= {14,33,27,35,10}; public static void main(String[] args) {
int temp; String[] a= {"safan","Ali","Fadi","Mohammad","Gouse"};
for (int i = 0; i<a.length;i++) String temp;
{ for (int i = 0; i<a.length;i++)
int flag=0; {
for (int j = 0; j<a.length-1-i;j++ )//the -i
int flag=0;
is used to skip the comparison of last rounds
largest element for (int j = 0; j<a.length-1-i;j++ )//the -i is
used to skip the comparison of last rounds largest
{ element
/* compare the adjacent elements */
{
if (a[j] > a[j+1])
/* compare the adjacent elements */ if
{ (a[j].compareTo( a[j+1])>0)//this compareto() method
temp=a[j]; takes every character and converts to unicode and
a[j]=a[j+1]; compares with another
a[j+1]=temp; {
flag=1; temp=a[j];
} a[j]=a[j+1];
} a[j+1]=temp;
if(flag==0)//to avoid continuous looping,im flag=1;
using flag
}}
{
if(flag==0)//to avoid continuous looping,im using
break; flag
} {
}
break;
for(int i=0;i<a.length;i++)
}}
{
for(int i=0;i<a.length;i++)
System.out.print(a[i]+ " ");
{
}
} System.out.print(a[i]+ " ");
69
} }
• Insertion Sort • How Insertion Sort Works?
• This is an in-place comparison-based • We take an unsorted array for our
sorting algorithm. example.
• Here, a sub-list is maintained which is
always sorted. • Insertion sort compares the first two
• For example, the lower part of an array is elements.
maintained to be sorted.
• An element which is to be inserted in this
sorted sub-list, has to find its appropriate • It finds that both 14 and 33 are already
place and then it has to be inserted there. in ascending order. For now, 14 is in
• Hence the name, insertion sort. sorted sub-list.
• The array is searched sequentially and
unsorted items are moved and inserted • Insertion sort moves ahead and
into the sorted sub-list (in the same compares 33 with 27.
array).
• This algorithm is not suitable for large
data sets as its average and worst case • And finds that 33 is not in the correct
complexity are of Ο(n2), where n is the
position.
number of items. 70
• It swaps 33 with 27. It also checks • However, swapping makes 27 and 10
with all the elements of sorted sub- unsorted.
list. Here we see that the sorted sub- • Hence, we swap them too.
list has only one element 14, and 27
is greater than 14. Hence, the sorted
sub-list remains sorted after • Again we find 14 and 10 in an
swapping. unsorted order.
• By now we have 14 and 27 in the
sorted sub-list. Next, it compares 33 • We swap them again. By the end of
with 10. third iteration, we have a sorted sub-
• These values are not in a sorted list of 4 items.
order.
• So we swap them. • This process goes on until all the
unsorted values are covered in a
sorted sub-list 71
• Algorithm • Pseudo code:
• Step 1 − If it is the first element, it is Int[] a={5,1,6,2,4,3}
already sorted. return 1; Int temp,j;
• Step 2 − Pick next element For(int i=1;i<a.length;i++)
• Step 3 − Compare with all elements in {
the sorted sub-list Temp=a[i];
• Step 4 − Shift all the elements in the J=i;
sorted sub-list that is greater than the
value to be sorted While(j>0 && a[j-1]>temp)
• Step 5 − Insert the value {
• Step 6 − Repeat until list is sorted A[j]=a[j-1];
J=j-1;
• Take some numbers and explain in }
programmatic way: 5,1,6,2,4,3 A[j]=temp
}
Print all the elements
72
public class InsertionSort {
public static void main(String[] args)
• Selection Sort
{ • Selection sort is a combination of
int[] a={5,1,6,2,4,3}; searching and sorting.
int temp,j; • First it identifies the smallest element
for(int i=1;i<a.length;i++)
in the list and replace in the 0th
{
temp=a[i];
position (index).
j=i; • Once again it searches which is the
while(j>0 && a[j-1]>temp) next smallest element and places it in
{ the 1st position (index).
a[j]=a[j-1];
• Like this it will do with the entire list.
j=j-1;
}
• In this selection sort, we will use two
a[j]=temp; lists, sorted list , unsorted list.
} • This algorithm is not suitable for large
for(int i=0;i<a.length;i++) data sets as its average and worst-case
{
complexities are of Ο(n2), where n is
System.out.print(a[i]+ " ");
the number of items.
}
} • Take some example and explain:
} 38,52,9,18,6,62,13 73
• Pseudo code public class Selection {
public static void main(String[] args) {
Declare array with list of elements // TODO Auto-generated method stub
int[] a= {38,52,9,18,6,62,13};
Int min, temp=0; int min,temp=0;
for(i=0;i<a.length;i++) for(int i=0;i<a.length;i++)
{ {
min=i;
int min=i; for(int j=i+1;j<a.length;j++)
for(j=i+1;j<a.length;j++) {
if(a[j]<a[min])
{ {
if(a[j]<a[min]) min=j;
}
{ }
min=j; temp=a[i];
a[i]=a[min];
} a[min]=temp;
} }

temp=a[i]; for(int i=0;i<a.length;i++)

{
a[i]=a[min]; System.out.println(a[i]+" ");
a[min]=temp; }
}
} }
74
• Merge Sort • Merge Sort
• Merge sort is one of the most
popular sorting algorithms and
widely used technique.
• Its time complexity is better as
compared to bubble sort, selection
sort, and insertion sort.
• Merge sort works on divide and
conquer rule.
• In merge sort we use 2 functions, one
merge() function, it is used for merging
2 halves. Second, mergesort() function,
it is used for calling itself (recursively)
to divide38 the array
27 43 3 9 till
82 size
10 becomes
one.
• Ex:
demonstrate
75
• Algorithm 1. Merge(l,r,a)
• Merge sort keeps dividing the list into equal halves until it can 2. {
no longer be divided. 1. Nl=length(l)
• 2. Nr=length(r )
By definition, if only one element is in the list, it is sorted.
3. i=j=k=0
Then, merge sort combines the smaller sorted lists keeping
4. While(i<nl && j<nr)
the new list sorted too.
5. {
1. If(l[i]<=r[j])
• Step 1 − if there is only one element in the list, it is already 2. {
sorted, return. 1. A[k]=l[i]
• Step 2 − divide the list recursively into two halves until it 2. i=i+1
3. }
can no longer be divided. 4. Else
• Step 3 − merge the smaller lists into new lists in sorted 5. {
order. 1. A[k]=r[j]
• Pseudo Code: 2. J=j+1
6. }
• Mergesort(A) 7. K=k+1
• { 6. }
• n=length(a)
7. While(i<nl)
• If(n<2)
• Return 8. {
• Mid=n/2 1. A[k]=l[i]
• Left=array of size(0 to mid-1) 2. i=i+1
• Right=array of size(mid – (n-1)) 3. K=k+1
• For(i=0 to mid-1) 9. }
• Left[i]=a[i]
• For(i=mid to n-1)
10. While(j<nr)
• right[i-mid]=a[i] 11. {
• Mergesort(left) 1. A[k]=r[j]
• Mergesort(right) 2. J=j+1
• Merge(l,r,a) 3. K=k+1 76
• }
1. import java.util.Arrays; 20. public static void merge(int[] arr, int[] left, int[] right) {
2. public class MergeSort { 21. int i = 0, j = 0, k = 0;
3. public static void mergeSort(int[] arr) { 22. int n1 = left.length, n2 = right.length;
4. int n = arr.length; 23. // Merge the sorted subarrays
5. if (n > 1) { 24. while (i < n1 && j < n2) {
6. // Divide the array into two halves 25. if (left[i] <= right[j]) {
7. int mid = n / 2; 26. arr[k++] = left[i++];
27. } else {
8. int left[] = new int[mid];
28. arr[k++] = right[j++];
9. int right[] = new int[n - mid];
29. }
10. // Copy data to left and right subarrays
30. }
11. System.arraycopy(arr, 0, left, 0, mid);
31. // Copy remaining elements from left array
12. System.arraycopy(arr, mid, right, 0, n - mid);
32. while (i < n1) {
13. // Recursively sort left and right subarrays 33. arr[k++] = left[i++];
14. mergeSort(left); 34. }
15. mergeSort(right); 35. // Copy remaining elements from right array
16. // Merge the sorted subarrays 36. while (j < n2) {
17. merge(arr, left, right); 37. arr[k++] = right[j++];
18. } 38. }
19. } 39. }
77
40. public static void main(String[] args) {

41. int[] arr = {12, 11, 13, 5, 6, 7};

42. System.out.println("Original array:");

43. System.out.println(Arrays.toString(arr));

44. mergeSort(arr);

45. System.out.println("Sorted array:");

46. System.out.println(Arrays.toString(arr));

47. }

48. }

78
• Shell Sort
• Shell sort is an algorithm that first sorts the
elements far apart from each other and
successively reduces the interval between
the elements to be sorted.
• It is a generalized version of insertion sort
and bubble sort.
• It is more efficient than insertion or bubble
sort.
• Algorithm • Pseudo Code
• Step1 – take input array & size of array as ShellSort(arr,n)
{
‘n’. for (int gap = n / 2; gap > 0; gap /= 2) {

• Step2 – initialize the value of gap or interval for (int i = gap; i < n; i++) {
int temp = arr[i];
(gap=n/2) int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
• Step3 – compare the elements at the arr[j] = arr[j - gap];
distance of gap at every iteration. }
arr[j] = temp;
• Step4 - If the element at the left is larger }

than element at the right, perform swap or }

}

shift. Note : ask the students to write a java program to implement above pseudo
79
• Step5 – repeat until complete list is sorted. code.
• public class ShellSort {
• public static void shellSort(int[] arr) {
• int n = arr.length;
• for (int gap = n / 2; gap > 0; gap /= 2) {
• for (int i = gap; i < n; i++) {
• int temp = arr[i];
• int j;
• for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
• arr[j] = arr[j - gap];
• }
• arr[j] = temp;
• }
• }
• }
• // Example usage
• public static void main(String[] args) {
• int[] arr = {12, 34, 54, 2, 3};
• shellSort(arr);
• System.out.println("Sorted array is:");
• for (int num : arr) {
• System.out.print(num + " ");
• }
• }
• }

80
• Quick Sort • List : 15,9,7,13,12,16,4,18,11 34. void rec(int[]
• It has another name called as Partition-Exchange sort. 1. public class QuickSort { arr,int low,int
• Compared to any other sorts, this sort is very fast, and it is proved and 2. public static void
implemented. main(String[] args) { high)
• It is developed by Tony Hoare in 1959. 3. // TODO Auto-generated 35. {
• It is using the concept of divide and conquer. method stub
• In this, you should choose one random element, which is called as pivot element. 4. int[] arr= 36. int
{15,9,7,13,12,16,4,18,11}; pi=partition(arr,
• Options to select pivot element: you can choose first element , or middle element,
5. int l=arr.length;
or last element. low,high);
• Better to choose middle element. 6. QuickSort qs = new
QuickSort(); 37. if(low<pi-1)
• Pseudo Code 7. qs.rec(arr, 0, l-1);
Quicksort(l,h) 8. qs.printarray(arr); 38. {
{ 9. } 39. rec(arr,low,pi-
10. int partition(int[] arr,int
If(l<h)
low,int high) 1);
{
J=partition(l,h);
11. { 40. }
12. int pivot=arr[(low+high)/2];
Quicksort(l,j); 41. if(pi<high)
13. while(low<=high)
Quicksor(j+1,h); 14. {
} 42. {
15. while(arr[low]<pivot)
} 16. { 43. rec(arr,pi,high);
Partition(l,h) 17. low++;
18. } 44. }
{
Pivot=a[l]
19. while(arr[high]>pivot) 45. }
20. {
i=l, j=h;
21. high--; 46. void
while(i<j) printarray(int[]
22. }
{
Do
23. if(low<=high) arr)
24. {
{
25. int temp=arr[low]; 47. {
i++;
}While(a[i]>=piovot); 26. arr[low]=arr[high]; 48. for(int i:arr)
Do 27. arr[high]=temp;
{ 49. {
J--; 28. low++;
} While(a[j]<=pivot); 29. high--; 50. System.out.printl
If(i<j)
30. } n(i);
Swap(a[i],a[j])
} 31. } 51. }
Swap(a[l],a[j]) //if I > j then swap will perform 32. return low; 52. }
Return j;
33. }
53. } 81
}
• Graphs
• Graph is a set of (V,E) pairs, where V is set of
vertices, E is set of edges.
• Graphs has closed loop; trees has open loop.
• Vertices – represented as circles , also known
as nodes.
• Edges – represented as lines, which are
connecting two vertices or nodes.
• Terminology of Graph
• Node – which is nothing but vertices,
represented as circles.
• Edge – which is a line, it’s a connection
between the 2 different nodes.
• Adjacent Nodes - Two node or vertices
are adjacent if they are connected to each
other through an edge.
• Degree of a Node – it represents the number of
edges connected to the corresponding node.
• Size of graph – total number of edges in graph.
• Path – sequence of vertices from source node 82
to destination node.
• Types of Graphs
1. Directed graph – direction will be available in
the graph.
• In this every edge specified with direction.
• In one direction only we can traverse.
• This is a unidirectional graph.
• (A,B)#(not equal) (B,A)
2. Undirected graph – no direction will be available
in the graph.
• In undirected graph, you can traverse from AB == BA
or (A,B)==(B,A)
• In both the directions we can travel.
• This is a Bi-Directional graph.
3. Weighted graph – in this graphs the weight is
specified for every edge.
4. Unweighted graph – in this graphs there is no
weights for the edges.
5. Cyclic graph – means it should perform loops,
the path should be the same.
• ABCDA (starting point and ending points are the
same)
6. Acyclic graph – it should not perform loops, the
path not be the same. 83
• ABC (starting point and ending points are different)
• Graph algorithms are methods used to
manipulate and analyze graphs, solving
various problems, such as finding the
shortest path and cycle detection.
• Representation of Graph
• We can represent a graph in two ways:
1. Multidimensional array
2. Linked Lists
1. Multidimensional Array
• Rows and columns are represented by Nodes.
• You need to fill the array with 0’s and 1’s.
• If any edge between the 2 nodes or vertices, it
will be represented by 1, otherwise by 0.
2. Linked List
• The edges are denoted by linked list node.
• You need to fill the array with 0’s and 1’s.
• If any edge between the 2 nodes or vertices, it
will be represented by 1, otherwise by 0.
https://www.jdoodle.com/online-java-compiler/

84
1. import java.util.Scanner; 28. public static void main(String[] args)
2. public class AdjMatrixGraph { 29. {
3. //data members vertices, matrix
30. Scanner s=new
4. int vertices;
Scanner(System.in);
5. int matrix[][];
6. //creating constructor
31. System.out.println("Enter the
number of vertices");
7. AdjMatrixGraph(int vertices)
8. { 32. int V = s.nextInt();
9. this.vertices=vertices; 33. AdjMatrixGraph amg = new
10. matrix=new int[vertices][vertices]; AdjMatrixGraph(V);
11. } 34. System.out.println("Enter the
12. void addEdge(int source, int destination) number of edges");
13. { 35. int E=s.nextInt();
14. matrix[source][destination]=1;
36. for(int i=0;i<E;i++){
15. matrix[destination][source]=1;
16. }
37. System.out.println("Enter
the source vertex");
17. void printGraph()
18. { 38. int a=s.nextInt();
19. for(int i=0;i<vertices;i++) 39. System.out.println("Enter
20. { the destination vertex");
21. for(int j=0;j<vertices;j++) 40. int b=s.nextInt();
22. { 41. amg.addEdge(a,b);
23. System.out.print(matrix[i][j]+ "
"); 42. }
24. } 43. amg.printGraph();
25. System.out.println(); 44. }
85
26. } 45. }
Implementing the graph using the linked list(using java linked list utility) 24. void displayGraph()
representation 25. {
1. import java.util.LinkedList; 26. for(int i=0;i<vertices;i++)
2. public class Graph { 27. {
3. //instance varaibles 28. //if the size of the linked list is > 0
4. int vertices; 29. if(adjList[i].size()>0)
5. //need to be create an array of linked lists 30. {
6. LinkedList<Integer> adjList[]; 31. System.out.println("Vertex "+ i + "
7. //create a constructor to initialize the is connected to:-");
values to instance variables 32. for(int j=0;j<adjList[i].size();j+
8. public Graph(int vertices) +)
9. { 33. {
10. this.vertices=vertices; 34. //get() method returns the element at the
specified position in the list.
11. //we are allocating memory to our
adjacency list 35.
System.out.print(adjList[i].get(j)+" ");
12. adjList=new LinkedList[vertices];
36. }
13. for(int i=0;i<vertices;i++)
37. System.out.println();
14. {
38. }
15. //here for every node, it will create
a linked list. 39. }
16. adjList[i]= new LinkedList<>(); 40. }
41. public static void main(String[] args) {
17. }
42. // TODO Auto-generated method stub
18. }
43. Graph g= new Graph(3);
19. void addEdge(int source, int destination)
44. g.addEdge(0,1);
20. {
45. g.addEdge(1,2);
21. adjList[source].add(destination);//add()
is inbuilt method of linked list 46. g.addEdge(2,0);
22. adjList[destination].add(source); 47. g.displayGraph();
23. } 48. } 86
49. }
• Graph Traversals
• Visiting all the nodes in the graph is called Traversals.
• In a traversal, every node must be visited only once.
• Types of traversals
1. Depth First Search (DFS) Traversal
2. Breadth First Search (BFS) Traversal
1. Depth First Search (DFS) traversal
• Based on depth of graph we are traversing all the nodes of
the graph.
• To implement the DFS, we use Stacks.
• Algorithm
• Step1 – put the starting node into the stack.
• Mark as visited
• Pop and Display it.
• Step2 – if(stack[top] has adjacent unvisited node)
• {
• Visit the adjacent unvisited node and mark it as
visited.
• Push it into the stack.
• Display it.
• Else
• {
• Pop the element from the stack.
• Display it.
• }
• (Repeat step2 until stack is empty)

87
1. import java.util.Scanner;
• void dfsRecursion(int start){
2. import java.util.LinkedList;
• visited[start]=true;
3. public class DFSRecursion {
• System.out.println(start+" ");
4. //create graph class
• for(int i=0;i<adjList[start].size();i++){
5. static class Graph{

6. //instance variables
• int dest=adjList[start].get(i);
7. int vertices; • if(!visited[dest])
8. //need to be create an array of linked list • dfsRecursion(dest);
9. LinkedList<Integer> adjList[]; • }
10. boolean visited[]; • }
11. //create a constructor to initialize the values to instance variables • }
12. Graph(int vertices){
• public static void main(String[] args) {
13. this.vertices=vertices;
• // TODO Auto-generated method stub
14. adjList = new LinkedList[vertices];
• Scanner s = new Scanner(System.in);
15. for(int i=0;i<vertices;i++) {

16. //here for every node, it will create a linked list.

• System.out.println("Enter the number of
vertices");
17. adjList[i]=new LinkedList<>();
• int v=s.nextInt();
18. }

19. }
• Graph g=new Graph(v);
20. void addEdge(int source, int destination){
• for(int i=0;i<v;i++){
21. adjList[source].addFirst(destination);//it is a directed graph • int source = s.nextInt();
22. } • int destination=s.nextInt();
23. void DFS(int startVertex){ • g.addEdge(source, destination);
24. visited=new boolean[vertices]; • }
25. dfsRecursion(startVertex);
• g.DFS(0);
26. }
• } 88
1. Breadth First Search (BFS) traversal
• Based on the breadth(level) of the graph, we are
traversing all the nodes of that level and
proceeding to the next level of the graph, until
traversing reaches the last level of the graph.
• To implement BFS, we use Q’s.
• Algorithm
• Step1 – visit the starting node and mark it as visited.
• Set a pointer to the starting node (currently working
node).
• Step2 – if(currently working node has adjacent
unvisited node)
• {
• Visit the adjacent unvisited node and mark it as
visited.
• Insert it into a Q.
• Display it.
• }
• Else
• {
• Update the pointer to the first element of a Q.
• Remove the first element from Q.
• }
• Repeat step2 until Q is empty. 89
• Create a class called BFSApp 11. class Graph {
1. import java.util.LinkedList; 12. private final int MAX_VERTS = 20;
2. import java.util.Queue; 13. private Vertex vertexList[];
14. private int adjMat[][];
3. class Vertex { 15. private int nVerts;
4. public char label; 16. private Queue<Integer> q;
5. public boolean wasVisited;
17. public Graph() {
6. public Vertex(char lab) { 18. vertexList = new
7. label = lab; Vertex[MAX_VERTS];
8. wasVisited = false; 19. adjMat = new int[MAX_VERTS]
[MAX_VERTS];
9. }
20. nVerts = 0;
10. }
21. q = new LinkedList<Integer>();
22. }

90
23. public void addVertex(char lab) { 41. public void bfs() {
24. vertexList[nVerts++] = new Vertex(lab);
42. vertexList[0].wasVisited = true;
25. }
43. displayVertex(0);
26. public void addEdge(int start, int end) { 44. q.add(0);
27. adjMat[start][end] = 1; 45. int v2;
28. adjMat[end][start] = 1;
29. } 46. while (!q.isEmpty()) {
47. int v1 = q.remove();
30. public void displayVertex(int v) { 48. while ((v2 =
31. System.out.print(vertexList[v].label); getAdjUnvisitedVertex(v1)) != -1) {
32. }
49. vertexList[v2].wasVisited =
33. public int getAdjUnvisitedVertex(int v) { true;
34. for (int j = 0; j < nVerts; j++) { 50. displayVertex(v2);
35. if (adjMat[v][j] == 1 && ! 51. q.add(v2);
vertexList[j].wasVisited) {
36. return j; 52. }
37. } 53. }
38. } 54. }
39. return -1;
40. }
55. } 91
56. public class BFSApp {
57. public static void main(String[] args) {
58. Graph theGraph = new Graph();
59. theGraph.addVertex('0');
60. theGraph.addVertex('1');
61. theGraph.addVertex('2');
62. theGraph.addVertex('3');
63. theGraph.addVertex('4');
64. theGraph.addVertex('5');

65. theGraph.addEdge(0, 1);

66. theGraph.addEdge(0, 2);
67. theGraph.addEdge(1, 3);
68. theGraph.addEdge(1, 4);
69. theGraph.addEdge(2, 5);

70. System.out.println("BFS Visits: ");

71. theGraph.bfs();
72. System.out.println();
73. } 92
74. }
• Trees
• It is another ADT (abstract data type) like stacks, linked lists, and Qs.
• Tree is a hierarchical data structure that stores the information naturally in the
form of a hierarchy style.
• Tree is one of the most powerful and advanced data structures.
• It is a non-linear data structure.
• Tree represents the nodes connected by edges.
• Terminology of the trees:
1. Node – element of the tree. (A, B, C, D, X, Y, Z)
2. Root node – starting node of the tree. (A, every tree will have only one root node)
3. Edge – link/connection between the 2 nodes. A tree with ‘n’ nodes will have ‘n-1’
edges. N=7, E=N-1=>7-1=>6.
4. Parent – a node with branches/child from top to bottom. (A, C, D)
5. Child – branches/children of parents. (B, C, D, X, Y, K)
6. Siblings – branches/leaves of the same parents. (B, C & D)(X & Y)
7. Leaf – node without a child node. (B, X, Y, K)
8. Internal nodes – all nodes other than leaf nodes. Or node with child. (A, C, D)
9. Degree – The number of child nodes represents the degree of a node. (A – has
three children, so the degree of A – 3, C- has two children, so the degree of C -2,
etc.,)
10. Degrees of a tree – maximum degree among all the nodes. (degree of the tree is 3)
11. Level – For every step/hierarchy in a tree, the level starts from 0. Every
level/hierarchy will be incremented by one. So, the overall level of the tree is 3. The
level of the root node is 0.
12. Height – the longest path from the leaf node to the particular node. H(B)=1, H(A)2.
13. Depth – the longest path from the root node to a particular node. D(Y)=2, D(B)=1.
14. Path – sequence of nodes from root to leaf. Or source to destination. P(A->X)=A-
>C->X.
15. Subtree - node with children.

93
• Classification of Trees
1. General Tree
2. Forest
3. Expression Tree
4. Tournament Tree
5. Binary Tree
6. Strictly Binary Tree
7. Complete Binary Tree
8. Binary Search Tree
1. General Tree – a tree with no limitations or restrictions is
called a General Tree. Every node has any number of
children.
2. Forest—A forest is a set of disjointed trees that appear by
deleting a root node, and its edges are connected to
further nodes.
3. Expression Tree—An expression tree evaluates simple
arithmetic expressions.
4. Tournament Tree—A tree used to record the winner of the
match in each round played among two players/teams is
called a Tournament Tree, Selection Tree, or Winner Tree.
5. Binary Tree—A binary tree is one in which every node has
a maximum of 2 children except leaf nodes. In BT, each
node has 0 children, one child, or 2 children, but not more
than 2 children.
6. Strictly Binary Tree—A tree in which every node has 2 or 0
94
children is called an SBT/Full BT/Proper BT/2-Tree.
7. Complete binary tree—a tree in which every
node has exactly 2 children, and all leaf
nodes are at the same level is called a
complete binary tree or perfect binary tree.
8. Binary search tree (BST): A BST is a BT where
the nodes are arranged in a specific order.
• In BST, the value of all the nodes in the left sub-
tree is less than that of the root node.
• Similarly, the value of all the nodes in the right
sub-tree is greater than that of the root node.
• This rule will be recursively applied to all the left
and right sub-trees of the root.
• In BST, all the elements are in sorted order.
• The middle element will be the root node; less
than the root node elements will be on the left
side, and the more significant than the root node
elements will be on the right side of the root
node.
Note: BT and BST differ because the data is not
arranged systematically in BT, so searching will
be difficult. The data is arranged systematically 95
in BST so that we can search easily.
• BST Basic Operations • Tree traversal Techniques
• The basic operations that can be • Traversal is a process to visit all the
performed on a binary search tree nodes of a tree and may print their
data structure, are the following − values too.
• Insert − Inserts an element in a • Because, all nodes are connected via
tree/create a tree. edges (links) we always start from the
• Search − Searches an element in a root (head) node.
tree.
• Preorder Traversal − Traverses a tree
• That is, we cannot randomly access a
in a pre-order manner. node in a tree.
• In-order Traversal − Traverses a tree • There are three ways which we use to
in an in-order manner. traverse a tree −
• Post-order Traversal − Traverses a 1. Pre-order Traversal (Root – Left – Right)
tree in a post-order manner. 2. In-order Traversal (Left – Root – Right)
3. Post-order Traversal (Left – Right – Root)

96
• Preorder traversal (Root – Left – Right) • Note: If you have a big tree like the
• This traversal starts the traversal from root , one below, add dummy nodes to the
then goes to left and then right.
• Traversal – x(root)  y(Left) z(Right)
leaf node, and nodes have only one
child.
• Inorder traversal (Left – Root – Right)
• This traversal starts the traversal from left , then • shortcut to traversals (apply left to right travers)
goes to root and then right. • If you are visiting a node 1st time, it's a
• Traversal – y(left)  x(root) z(Right) preorder; if you are visiting a node 2nd
• Note: inorder of BST elements are always sorted time, it’s in order; and if you are visiting
order. a node at 3rd time, it’s a post-order.
• Postorder traversal (Left – Right – Root)
• This traversal starts the traversal from left , then
goes to right and then root.
• Traversal – y(left)  z(right) x(root)

97
• Inorder tree traversal (Left – Root – Right) • Preorder tree traversal (Root – Left – Right)

98
• Postorder tree traversal (Left – Right – Root) • Assignment to the students -find
Inorder, preorder, and postorder to
the following binary search tree?

99
• PreorderTraversal that performs a preorder 10. public class BinaryTree {
11. Node root;
traversal of a binary tree.
1. import java.util.Stack; 12. void preorderTraversal(Node node) {
13. if (node == null)
14. return;
2. class Node { 15. // Create an empty stack and push the root node
3. int data; 16. Stack<Node> stack = new Stack<>();
4. Node left, right; 17. stack.push(node);

18. // Iterate until the stack is empty

5. public Node(int item) { 19. while (!stack.isEmpty()) {
6. data = item; 20. // Pop a node from the stack and visit it
21. Node current = stack.pop();
7. left = right = null;
22. System.out.print(current.data + " ");
8. } 23. // Push right and left children of the popped node to the
9. } stack
24. // (Right child is pushed first so that left is processed
first)
25. if (current.right != null) {
26. stack.push(current.right);
27. }
28. if (current.left != null) {
29. stack.push(current.left);
30. }
31. }
100
32. }
33. public static void main(String[] args) {
34. BinaryTree tree = new BinaryTree();
• InorderTraversal that performs an
35. tree.root = new Node(1); Inorder traversal of a binary tree.
36. tree.root.left = new Node(2); 1. import java.util.Stack;
37. tree.root.right = new Node(3);
38. tree.root.left.left = new Node(4);
39. tree.root.left.right = new Node(5); 2. class Node {
3. int data;
40. System.out.println("Preorder traversal of the binary
tree is:"); 4. Node left, right;
41. tree.preorderTraversal(tree.root);
42. }
43. } 5. public Node(int item) {
6. data = item;
44. Output:12453
7. left = right = null;
8. }
9. }

101
10. public class BinaryTree { 31. public static void main(String[] args) {
11. Node root;
32. BinaryTree tree = new
12. void inorderTraversal(Node node) { BinaryTree();
13. if (node == null)
14. return;
33. tree.root = new Node(1);
34. tree.root.left = new Node(2);
15. Stack<Node> stack = new Stack<>(); 35. tree.root.right = new Node(3);
16. Node current = node;
36. tree.root.left.left = new Node(4);
17. // Loop till the current node is null and stack is empty
37. tree.root.left.right = new Node(5);
18. while (current != null || !stack.isEmpty()) {
19. // Reach the leftmost node
20. while (current != null) { 38. System.out.println("Inorder
21. stack.push(current);
22. current = current.left;
traversal of the binary tree is:");
23. } 39. tree.inorderTraversal(tree.root);
40. }
24. // Current must be null at this point
25. current = stack.pop(); 41. }
26. System.out.print(current.data + " ");

27. // Traverse the right subtree 42. Output:42513

28. current = current.right;
29. }
102
30. }
• PostorderTraversal that performs a 10.
11.
public class BinaryTree {
Node root;
postorder traversal of a binary tree.
1. import java.util.Stack;
12. void postorderTraversal(Node node) {
13. if (node == null)
14. return;

15. Stack<Node> stack1 = new Stack<>();

2. class Node { 16. Stack<Node> stack2 = new Stack<>();

3. int data; 17.

18.
// Push the root to the first stack
stack1.push(node);

4. Node left, right; 19.

20.
// Process all nodes
while (!stack1.isEmpty()) {
21. Node current = stack1.pop();
22. stack2.push(current);

5. public Node(int item) 23. // Push the left and right children into stack1

{ 24.
25.
if (current.left != null)
stack1.push(current.left);

6. data = item;
26. if (current.right != null)
27. stack1.push(current.right);
28. }
7. left = right = null; 29. // Pop all elements from stack2 and print them
8. } 30.
31.
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().data + " ");

9. } 32.
33. }
} 103
34. public static void main(String[] args) {
35. BinaryTree tree = new BinaryTree();
36. tree.root = new Node(1);
37. tree.root.left = new Node(2);
38. tree.root.right = new Node(3);
39. tree.root.left.left = new Node(4);
40. tree.root.left.right = new Node(5);

41. System.out.println("Postorder traversal of

the binary tree is:");
42. tree.postorderTraversal(tree.root);
43. }
44. }
45. Output: 45231

104
105
106
• Creating a Binary search tree • Representation of BST
• Ex: 4,2,3,6,5,7,1 • BST is a collection of nodes, which are
represented by doubly linked list
nodes.

• Rules: On the left side of the root, all the

elements should be smaller than the root
node, and on the right side of the root, all
the elements should be greater than the
root node.
• If the element value is the same as the
root value, then you can put it either on
the left or right side.
• After creating the BST, if you go to the left
side until the bottom, you will find the
least element; if you go to the right side
until the bottom, you will find the largest
element.
• Note: ask the students to find pre-, in, and 107
post-orders of the above tree.
Binary Search Tree Program 26. // Function to print inorder traversal of the tree
1. class Node { 27. void inorderTraversal(Node root) {
2. int data; 28. if (root != null) {
3. Node left, right; 29. inorderTraversal(root.left);
30. System.out.print(root.data + " ");
4. Node(int item) { 31. inorderTraversal(root.right);
5. data = item; 32. }
6. left = right = null; 33. }
7. } 34. public static void main(String[] args) {
8. } 35. BinaryTree tree = new BinaryTree();
9. class BinaryTree { 36. /* Let us create the following BST
10. Node root; 37. 50
11. // Function to insert a new node with the given key into the BST 38. / \
12. Node insert(Node node, int key) { 39. 30 70
13. /* 1. If the tree is empty, return a new node */ 40. / \ / \
14. if (node == null) { 41. 20 40 60 80 */
15. node = new Node(key); 42. tree.root = tree.insert(tree.root, 50);
16. return node; 43. tree.root = tree.insert(tree.root, 30);
17. } 44. tree.root = tree.insert(tree.root, 20);
18. /* 2. Otherwise, recur down the tree */ 45. tree.root = tree.insert(tree.root, 40);
19. if (key < node.data) 46. tree.root = tree.insert(tree.root, 70);
20. node.left = insert(node.left, key); 47. tree.root = tree.insert(tree.root, 60);
21. else if (key > node.data) 48. tree.root = tree.insert(tree.root, 80);
22. node.right = insert(node.right, key); 49. System.out.println("Inorder traversal of the binary tree: ");
23. /* return the (unchanged) node pointer */ 50. tree.inorderTraversal(tree.root);
24. return node; 51. } 108
25. } 52. }
• How to search for a given key in 1.
2.
class Node {
int data;
a Binary Search Tree (Recursive) 3. Node left, right;
4. Node(int item) {
• Pseudo code: 5. data = item;
6. left = right = null;
public TreeNode 7. }
search(TreeNode root, int key){ 8.
9.
}
class BinarySearchTree {
if(root==null || root.data==key){ 10. Node root;
11. // Function to insert a new node with the given key into the BST
return root; 12. Node insert(Node node, int key) {

} 13.
14.
/* 1. If the tree is empty, return a new node */
if (node == null) {
if(key<root.data){ 15. node = new Node(key);
16. return node;
return search(root.left, key); 17. }

} else { 18.
19.
/* 2. Otherwise, recur down the tree */
if (key < node.data)
return search(root.right, key); 20. node.left = insert(node.left, key);
21. else if (key > node.data)
} 22. node.right = insert(node.right, key);

} 23.
24.
/* return the (unchanged) node pointer */
return node; 109
26. // Function to search for a given key in the BST 48. tree.root = tree.insert(tree.root, 50);
27. boolean search(Node root, int key) {
28. // Base Case: If root is null, key is not present. 49. tree.root = tree.insert(tree.root, 30);
29. if (root == null) 50. tree.root = tree.insert(tree.root, 20);
30. return false;
31. // If root's data is equal to the key, return true. 51. tree.root = tree.insert(tree.root, 40);
32. if (root.data == key) 52. tree.root = tree.insert(tree.root, 70);
33. return true;
34. // Recursively search in the left subtree if the key is 53. tree.root = tree.insert(tree.root, 60);
smaller.
54. tree.root = tree.insert(tree.root, 80);
35. if (key < root.data)
36. return search(root.left, key); 55. int key = 90;
37. // Recursively search in the right subtree if the key is 56. if (tree.search(tree.root, key))
greater.
38. return search(root.right, key); 57. System.out.println("Key " + key +
39. } " found!");
40. public static void main(String[] args) {
41. BinarySearchTree tree = new BinarySearchTree();
58. else
42. /* Let us create following BST 59. System.out.println("Key " + key +
43. 50 " not found!");
44. / \
45. 30 70 60. }
46. / \ / \ 61. } 110
47. 20 40 60 80 */
• AVL Trees
• It is a type of binary tree / binary search
tree.
• This is a self balancing binary search
tree, which was invented by Adelson,
Velsky, Lindas (AVL).
• Balancing means, it will maintain the
heights of the left and right subtrees.
• Heights are measured by balancing
factor.
• BF=HLST-HRST (results = 0,1,-1)
• If the answer is other than 0,1,-1, it is
not AVL Tree.

111
• AVL Rotations/Transformations
• To balance itself, an AVL tree may perform the following four kinds of
rotations −
1. Right-Right (RR) rotation(1 Left)
2. Left-Left (LL) rotation (1 Right)
3. Right-Left (RL) rotation (1 Right 1 Left)
4. Left-Right (LR) rotation (1 Left 1 Right)

112
• Construct the AVL tree using the following elements, which are added in the given order:
• 35, 50, 40, 25, 30, 60, 78, 20, 28 https://www.youtube.com/watch?v=CVA85JuJEn0&ab_channel=KunalKushwaha

113
• Spanning Tree • Application of Spanning Tree
• A spanning tree is a subset of Graph G, with all the • Spanning tree is basically used to find a
vertices covered with the minimum possible number of
edges. minimum path to connect all nodes in a graph.
• Hence, a spanning tree does not have cycles and • Common application of spanning trees are −
cannot be disconnected. • Civil Network Planning
• General Properties of Spanning Tree • Computer Network Routing Protocol
• We now understand that one graph can have more • Cluster Analysis
than one spanning tree. The following are a few
properties of the spanning tree connected to graph G • Minimum Spanning Tree (MST)
−
• A connected graph G can have more than one spanning
• In a weighted graph, a minimum spanning
tree. tree is a spanning tree that has minimum
• All possible spanning trees of graph G have the same weight than all other spanning trees of the
number of edges and vertices. same graph.
• The spanning tree does not have any cycles (loops). • In real-world situations, this weight can be
• Removing one edge from the spanning tree disconnects
the graph; the tree is minimally connected.
measured as distance, congestion, traffic load
• Adding one edge to the spanning tree creates a circuit or any arbitrary value denoted to the edges.
or loop; the tree is maximally acyclic.
• Mathematical Properties of Spanning Tree
• Minimum Spanning-Tree Algorithm
• A spanning tree has n-1 edges, where n is the number of • We shall learn about two most important
nodes (vertices).
• From a complete graph, we can construct a spanning tree by
spanning tree algorithms here −
removing maximum e - n + 1 edges. • Kruskal's Algorithm
• A complete graph can have a maximum nn-2 number of
spanning trees. • Prim's Algorithm
• Thus, we can conclude that spanning trees are a subset of
connected graphs and disconnected graphs do not have a 114
spanning tree.
• Kruskal Algorithm for Minimum Spanning • By using the given graph, we need to
Tree construct a spanning tree; in this case,
the number of edges in this spanning
tree will be n-1.
• Here, n means the number of vertices.
• Using the above graph, 7-1 = 6 edges
• Kruskal’s algorithm is used to find the will come in the spanning tree.
minimum cost spanning tree. • While constructing the spanning tree
• While finding the minimum cost spanning with the six edges, you should not
tree, the number of vertices in your graph form a loop(cycle); the cost must be
must be the same as that in the spanning less and connected.
tree. • While forming the minimum spanning
tree, first, you must choose the
minimum weight in ascending order.
• Better you try to list all the weights in
the ascending order: 2,3,4,5,6 115
• In our case, the minimum weight is 2 • Here, I will choose (B-C) and draw the
• If you have more than one (2), you choose edge.
any one and draw the edge; if the second • The following four (4) are in between
two (2) do not form the cycle/loop, you (E-G), before drawing an edge, check
can also draw that edge. whether it is forming a cycle/loop; if it is
• Here, I draw the edge between B-E. creating, don’t draw that edge.
• In the following case, choose the • The following four (4) are between (F-
minimum, i.e., 3. In this case, you have G), forming a cycle/loop. So, don’t
two 3’s (A-C) and (E-F), and choose any include it in the spanning tree.
one and draw the edge, but it should not
form a cycle/loop. • In the following case, choose the
minimum, i.e., 5. In this case, you have
• Here, I will be choosing A-C and drawing
two 5’s (A-B) & (C-D).
the edge.
• If the next three (3) do not form any • If you choose (A-B) weight, it forms a
cycle/loop, you can draw that edge too. cycle/loop, so don’t add it.
• In the following case, choose the
minimum, i.e., 4. In this case, you have 116
three 4’s (B-C),(E-G) & (F-G).
• Here's a breakdown of how it works: • Ask students to work on the graph
• 1. Sort Edges: below and find the minimum
• All edges in the graph are sorted in spanning tree using Kruskal's
ascending order based on their weights. algorithm.
• 2. Iterative Addition:
• The algorithm iterates through the sorted
edges, adding each one to the growing tree
if it doesn't create a cycle.
• 3. Cycle Detection:
• A disjoint-set data structure (a Union-Find
data structure) determines if adding an
edge would create a cycle efficiently.
• 4. Minimum Spanning Tree:
• The process continues until all vertices are
connected, forming the MST.

117
• Algorithm • Prims Algorithm
• Sort all the edges in the graph in
ascending order and store them in an
array edge[].
• Construct the forest of the graph on a
plane with all the vertices in it.
• Select the least cost edge from the
edge[] array and add it to the forest of
the graph. Mark the vertices visited by
adding them to the visited[] array. • The Prim's algorithm finds the
• Repeat steps 2 and 3 until all the minimum cost spanning tree.
vertices are visited without forming any • In the prim’s algorithm, the edges
cycles in the graph must be v–1, where v is the number
• When all the vertices are visited, the of vertices.
minimum spanning tree is formed.
• Calculate the minimum cost of the • Here, you must choose any random
output spanning tree formed. vertex as a starting vertex to
establish the spanning tree. 118
• In this example, I choose vertex “b” as • Now, you have reached the “d” vertex;
a starting vertex. repeat the above steps.
• You have to identify how many edges • The vertex “d” has formed two edges,
the vertex “b” forms, in this case, (b-a) like (d-g) & (d-f), and find the minimum
& (b-c), then choose the minimum weight, considering the previous steps’
weight edge. weights that have not been used.
• So, the (b-a) has minimum weight, i.e., • So, (d-f) has minimum weight, i.e., 2,
1, and draw the edge. and draw the edge.
• Now that you have reached “a” vertex, • Now, you have reached the “f” vertex;
repeat the above steps. repeat the above steps.
• The vertex “a” has formed two edges, • The vertex “f” has formed three edges,
like (a-d) & (a-c), and find the minimum like (f-d), (f-h) & (f-c), and find the
weight, considering the previous steps’ minimum weight, considering the
previous steps’ weights that have not
weights that have not been used.
been used.
• So, (a-d) has minimum weight, i.e., 5, • So, (f-c) has minimum weight, i.e., 3,
and draw the edge. and draw the edge. 119
• Now, you have reached the “c”
vertex; repeat the above steps.
• The vertex “c” has formed four edges,
like (c-b), (c-a), (c-f) & (c-e), and find
the minimum weight, considering the
previous steps’ weights that have not
been used.
• Observe the edges while adding to
the spanning tree, see if a cycle/loop
is forming; if it is, try to avoid it.
• In the above case, (c-a) & (c-b) have
the minimum weight, but they form a
cycle/loop, so avoid them and choose
(c-e) and draw.
• Repeat the above steps and form a
minimum spanning tree. 120
• Dijkstra's Algorithm
• Dijkstra's algorithm is a greedy algorithm
that solves the single-source shortest path
problem for a graph with non-negative
edge weights, producing a shortest-path
tree from a starting vertex to all other
vertices.
• In the above directed graph, we have
• Key Characteristics
• Purpose: Find the shortest paths from a source
three vertices, like, and 1,2,3.
node to all other nodes in a weighted graph • For example, I want to go to vertex
• Edge Weights: Works only with non-negative
weights two from 1 (12). In this case, we
• Approach: Uses a greedy strategy, always don’t know the cost to reach 2, so
selecting the next most promising node we will set it as infinite (∞).
• Applications
• Network routing protocols (OSPF, IS-IS) • In the same way, we don’t know the
• Google Maps and other navigation systems cost between 1 and 3, so we will set
• Traffic information systems it as infinite (∞).
• Flight itinerary planning
• Robotics path planning
121
• Network design and analysis
• If you want to know the cost between
1 and 2, consider one as the source
(u) and two as the destination (v).
• If d(u)+c(u,v)<d(v)
• d(v)=d(u)+c(u,v)
• Where d(1) is zero because the
distance from 1 to 1 is zero, and the
cost of (u,v), c(1,2), is 20, and the
distance of v is infinite.
• If 0+20 < ∞
• d(2)=20
• Repeat the above steps to find the
cost.

122
• Heap Tree • Common Operations and Their
• A Heap is a special Tree-based data structure in which
the tree is a complete binary tree. Complexities
• If you want to construct a heap tree, you should • Operation Time Complexity
follow the following properties:
• Structural property – Almost Complete Binary Tree
• Insert O(log n)
(ACBT). • Delete O(log n)
• Ordering property – max heap or min heap.
• Generally, Heaps can be of two types:
• Find Min/Max O(1)
• Max-Heap: In a Max-Heap, the key at the root node • Build Heap O(n)
must be the greatest among the keys at all of its
children.
• Heap Sort O(n log n)
• The same property must be recursively true for all sub-
trees in that Binary Tree.
• Min-Heap: In a Min-Heap, the key present at the root
node must be the minimum among the keys present at
all of its children.
• The same property must be recursively true for all sub-
trees in that Binary Tree.

123