COMPUTER LABORATORY MANUAL

Data Structure and Algorithms

Version 1.3

Muhammad Afrasiyab Khan Khattak

FA22-BSSE-4B-087

DEPARTMENT OF SOFTWARE ENGINEERING (DSE)

FOUNDATION UNIVERSITY RAWALPINDI CAMPUS
(FURC)
www.fui.edu.pk
http://www.fui.edu.pk/FURC/

1 Data Structure and Algorithms Lab Manual

 PREFACE
To learn a subject such as computer science, you need to immerse yourself in it - learning by doing
rather than by simply observing. Through the study of several classic data structures and algorithms,
you will become a better informed and more knowledgeable computer science student and
programmer. To be able to professionally choose the best algorithm and data structure for a
particular set of resource constraints takes practice.
An emphasis on learning by doing is used throughout Data Structures through Java: a laboratory
manual. In each laboratory, you explore a particular data structure by implementing it. As you create
an implementation, you learn how the data structure works and how it can be applied. The resulting
implementation is a working piece of software that you can use in later laboratories and
programming projects.
One cannot learn to program just by reading a book. It is a skill that must be developed by practice.
Nevertheless, the best practitioners study the works of others and incorporate their observations into
their own practice. I firmly believe that after learning the fundamentals of program writing, students
should be exposed to examples of complex, yet well-designed program objects so that they can learn
about the designing good software.
This laboratory manual includes the programs relating to Overview of Java and Data Structures.

PREPARED BY
Lab manual is prepared by Mr. Aqib Rehman under the supervision of Head of Department, Dr.
Muhammad Shaheen.

GENERAL INSTRUCTIONS
a. Students are required to maintain the lab manual with them till the end of the semester.
b. All readings, answers to questions and illustrations must be solved on the place provided. If more
space is required then additional sheets may be attached.
c. It is the responsibility of the student to have the manual graded before deadlines as given by the
instructor.
d. Loss of manual will result in re-submission of the complete manual.
e. Students are required to go through the experiment before coming to the lab session.
f. Students must bring the manual in each lab.
g. Keep the manual neat clean and presentable.
h. Plagiarism is strictly forbidden. No credit will be given if a lab session is plagiarised and no re-
submission will be entertained.
i. Marks will be deducted for late submission.
j. You need to submit the report even if you have demonstrated the exercises to the lab instructor or
shown them the lab report during the lab session.

VERSION HISTORY
Date Update By Details
Fall 2019 Version 1.0
Sep 2019 Aqib Rehman Version 1.1. Designed in Java language
Sep 2019 Aqib Rehman Version 1.2. Formating, Experiments are
added, Exercises are added
Fall 2019 Ms. Aania Majeed Version 1.3. Complex Problems added
Dr. Muhammad Asif

2 Data Structure and Algorithms Lab Manual

 MARKS

LAB Date Lab Title Max. Marks Instructor

# Conducted Marks Obtained Sign
1 Overview of Java Language and 10
Measuring Execution Time of
Java
Program
2 Arrays (Static, Dynamic and Multi- 10
dimensional)
3 Array based Stack implementation 10

4 Array based 10
Queues
implementation
5 Circular and Priority Queues 10

6 Singly Link List 10

7 Doubly Link List 10

8 Semester Project Proposal 10

9 Binary Trees, Binary Tree Traversals 10

and Level Order Traversal
10 Binary Search Trees 10

11 Balanced Trees 10

12 Dictionary using Hashing 10

13 Dictionary using Hashing and 10

HashTable
14 Heap 10

15 Graphs, Graph Traversals and 10

Memory Management
16 Semester Project Final

Grand Total

3 Data Structure and Algorithms Lab Manual

 LIST OF LAB TASKS

LAB TASK 1 – Overview of Java Language and Measuring Execution Time of Java Program...5
LAB TASK 3 – Array based Stack implementation......................................................................23
LAB TASK 4 – Array based Queue implementation....................................................................31
LAB TASK 5 – Circular Queue and Implementation of Deque using circular array...................40
LAB TASK 8 – SEMESTER PROJECT GUIDELINES..............................................................74
LAB TASK 9 – Binary Trees, Binary Tree Traversals and Level Order Traversal......................77
LAB TASK 10 – Binary Search Trees..........................................................................................90
LAB TASK 11 – Balanced Trees..................................................................................................96
LAB TASK 16 – SEMESTER PROJECT PRESENTATION......................................................128

4 Data Structure and Algorithms Lab Manual

LAB TASK 1 – Overview of Java Language and Measuring Execution Time of Java
Program

Name / Group ID: Reg. No:

Class / Section: Date: _

Time Required : 3 hrs

Programming Language : Java
Software Required : Netbeans
Hardware Required : Computer System

Overview of Java
This section introduces the students to elementary Java. Java is a vast computer language and
programming environment, it is not possible to touch upon all Java-related issues. This section
introduces only those aspects of Java that are necessary for understanding the Java code offered
in this book. Java program examples presented in this section give you to implement data
structures.

What is an Algorithm?
An algorithm is a technique for solving a problem or performing an analysis. Algorithms act as
an accurate list of instructions that execute specified actions step by step in either hardware or
software-based practices. Algorithms are widely used throughout all regions of IT.

Overview of data structures

There are certain types of containers that are used to store data. These containers are nothing but
data structures. These containers have different properties associated with them, which are used
to store, organize, and manipulate the data stored in them.
There can be two types of data structures based on how they allocate the data. Linear data
structures like arrays and linked lists and dynamic data structures like trees and graphs.

Difference between Linear and Non-linear data structures

In linear data structures, each element is linearly connected to each other having reference to the
next and previous elements whereas in non-linear data structures, data is connected in a non-
linear or hierarchical manner.
Implementing a linear data structure is much easier than a non-linear data structure since it
involves only a single level. If we see memory-wise then the non-linear data structures are better
than their counterpart since they consume memory wisely and do not waste it.

Types of Data Structure

 Arrays
 Linked Lists
 Stacks
 Queues
 Trees
 Hash tables
 Graphs

5 Data Structure and Algorithms Lab Manual

Quadratic equation
Write a Java program that prints all real solutions to the quadratic equation ax2 + bx + c = 0. Read in
a, b, c and use the quadratic formula. If the discriminant (b2– 4ac) is negative; display a message
stating that there are no real solutions.
The roots of the quadratic equation, ax2 + bx + c = 0 are given by:
x = [–b ± √(b2 – 4ac) ]/2a
The discriminant, d = (b2 – 4ac)
Case (1): When d is greater than zero, the two roots are real.
x1 = (–b + √d )/2a and x2 = (–b – √d )/2a
Case (2): When d is equal to zero, the two roots are equal.
x1 = x2 = – b /2a
Case (3): When d is less than zero, the two roots are imaginary. Each of the two roots has
two parts: real-part-1, imaginary-part-1 and real-part-2, imaginary-part-2.
real-part-1, xr1 = –b/2a imaginary-part-1, xi1 = +√d
/2a real-part-2, xr2 = –b/2a imaginary-part-2, xi2 = –√d
/2a

Program: Roots of a quadratic equation

import java.lang.Math;
import java.util.Scanner;
class QuadraticEquation
{
double a, b, c; // coefficients
QuadraticEquation( double a, double b, double
c)

6 Data Structure and Algorithms Lab Manual

 {
this.a = a;
this.b = b;
this.c = c;
}
public void roots()
{
if( a == 0.0 )
{ System.out.println("One root = " +
(-c/b)); return;
}
double d = b*b - 4.0*a*c;
if(d < 0) // Roots are imaginary
{
System.out.println("There are no real solutions."); return;
}
if(d == 0)
{
// Roots are equal
System.out.println("Two roots are equal: " + (-b /(2.0*a))); return;
}
// Roots are real
double x1 = (-b + Math.sqrt(d))/(2.0*a);
double x2 = (-b - Math.sqrt(d))/(2.0*a);
System.out.println("Roots are: " + x1 + ", " + x2);
}
}
//////////////////// QuadraticEquationDemo.java /////////////////
class QuadraticEquationDemo
{
public static void main(String[] args)
{
Scanner scr = new Scanner(System.in);
System.out.print(" a = ");
double a = scr.nextDouble();
System.out.print(" b = ");
double b =
scr.nextDouble();
System.out.print(" c = ");
double c = scr.nextDouble();
QuadraticEquation qe = new QuadraticEquation(a, b,

c); qe.roots();
}
}

Output:
7 Data Structure and Algorithms Lab Manual
 a=0
b=4
c=1
One root = -0.25
a=1
b=4
c=4
Two roots are equal: -2.0
a=1
b=4
c=8
There are no real solutions
a=1
b=4
c=3

Roots are: -1.0, -3.0

Prime numbers
A prime number is a positive integer that is exactly divisible only by 1 and itself. The first few
prime numbers are:

2 3 5 7 11 13 17 23 29 31 37…

All primes apart from 2 are odd.

As a starting point in developing the prime number generator let us explore how we can establish
whether or not a particular number is a prime. To do this, let us consider a number 13. The definition
of prime number suggests that to determine whether or not 13 is prime, we need to divide it in turn
by the set of numbers 2, 3, 4, 5 …12. If any of these numbers divide into 13 without remainder we
will know it cannot be prime number. Therefore, to test an integer n for prime, n-2 calls to the mod
operation are required. As our n is 13, we need 11 calls. As n grows, the cost of making these
divisions and tests is going to get very expensive. We must therefore look for ways of improving the
efficiency of the algorithm. Firstly, we can try to keep to a minimum the number of numbers that we
have to test for primes, and secondly we can try to improve the efficiency of testing a number for
prime.

Following up these suggestions, we know that apart from 2, we do not need to examine any of the
even numbers, and only first half of the numbers is enough for testing prime. That is, we can test for
mod operation with numbers, from 3 to n/2. Hence, the following set of numbers is sufficient to test
13 for prime.
3 4 5 6

8 Data Structure and Algorithms Lab Manual

 Program : Prime numbers

import java.io.*;
class PrimeNumber
{
public void primes(int n)
{
int k, m;
System.out.print("Prime numbers up to " + n + ": 2 3");
for(m=3; m <= n; m = m+2)
{
boolean isPrime = false;
for(k=2; k <= m/2; k++)
{
if(m % k == 0) { isPrime = false; break;
} else isPrime = true;
}
if(isPrime) System.out.print(" " + m);
}
}
}
////////////////////////// PrimeNumberDemo.java /////////////////
class PrimeNumberDemo
{
public static void main(String[] args) throws IOException
{ PrimeNumber pn = new PrimeNumber();
BufferedReader kb = new
BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter n: ");
int n = Integer.parseInt(kb.readLine());
pn.primes(n);
}
}
Output:
Enter n: 50
Prime numbers up to 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Palindrome

“MADAM” is a palindrome.

A string is an array of characters. For example, the string “MADAM” is stored as follows: [0] [1] [2]

[3] [4]
M A D A M

9 Data Structure and Algorithms Lab Manual

Java supports the manipulation of character data through the primitive data type char and the associated
operations for the input, output, assignment, and comparison of characters. Most applications of character
data require character sequences - or strings - rather than individual characters. In Java a string is
represented by the built-in class String. However, manipulating a String data type in Java is quite
different from manipulating a set (or array) of characters. In the Java, strings are objects. The Java
platform provides the String class to create and manipulate strings. The most direct way to create a string
is to write:
String str = "MADAM";

In this case, "MADAM" is a string literal - a series of characters that is enclosed in double quotes.
The String class provides the method length(), which returns as an int value the number of characters
in the String object. The method of the String class
char charAt(int n)

returns the nth character in a string (where n must be less than string length);

If the first character is equal to the last character of the string, second character is equal to the second
one from the last character of the string, and so on, then the string is a palindrome.

Program 4: Palindrome

class Palindrome
{
public boolean isPalindrome(String str)
{
System.out.print("Given string: " + str);
int n = str.length();
boolean flag =
true;
for( int i=0; i < n/2; i++ )
if( str.charAt(i) != str.charAt(n-i-1) ) flag = false; return flag;

}
}
////////////////////////// PalindromeDemo.java ////////////////////
class PalindromeDemo
{
public static void main(String[] args)
{

Palindrome pal = new

Palindrome(); String str =
"MADAM";
if( pal.isPalindrome(str))
System.out.print(" is a
10 Data Structure and Algorithms Lab Manual
 palindrome.");
else
System.out.print(" is not a palindrome.");

11 Data Structure and Algorithms Lab Manual

 }
}

Output:
Given string: MADAM is a palindrome.

Execution Time in Java

class TimeTest1 {
public static void main(String[] args) {

long startTime =

System.currentTimeMillis(); long total = 0;

for (int i = 0; i < 10000000; i++)
{ total += i;
}

long stopTime =
System.currentTimeMillis(); long
elapsedTime = stopTime - startTime;
System.out.println(elapsedTime);
}
}
Difference Between Linear Search and Binary Search
The major difference between linear search and binary search is that binary search takes less time to
search an element from the sorted list of elements. So it is inferred that efficiency of binary search
method is greater than linear search. Another difference between the two is that there is a prerequisite
for the binary search, i.e., the elements must be sorted while in linear search there is no such
prerequisite. Although both the searching methods use different techniques which are discussed below.

1. Linear search is iterative in nature and uses sequential approach. On the other hand, Binary
search implements divide and conquer approach.
2. The time complexity of linear search is O(N) while binary search has O(log2N).
3. The best case time in linear search is for the first element i.e., O(1). As against, in binary
search, it is for the middle element, i.e., O(1).
4. In the linear search, worst case for searching an element is N number of comparison. In
contrast, it is log2N number of comparison for binary search.
5. Linear search can be implemented in an array as well as in linked list whereas binary search
can not be implemented directly on linked list.
6. As we know Binary search requires the sorted array that is reason It requires processing to
insert at its proper place to maintain a sorted list. On the contrary linear search does not require
sorted elements, so elements are easily inserted at the end of the list.
7. Linear search is easy to use, and there is no need for any ordered elements. On the other
hand, Binary search algorithm is however tricky, and elements are necessarily arranged in order.

12 Data Structure and Algorithms Lab Manual

 Conclusion

Both linear and binary search algorithms can be useful depending on the application. When an array is
the data structure and elements are arranged in rted order, then binary search is preferred for
quick searching. If linked list is the data structure regardless how the elements are arranged, linear
search is adopted due to unavailability of direct implementation of binary search algorithm.

Exercise 1: (5)
Calculate the elapsed time of Linear search and Binary Search.
import java.util.Arrays;
import java.util.Date;

public class Main {

public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int key = 11;

long startTime = new Date().getTime();

int result = linearSearch(arr, key);
long endTime = new Date().getTime();
System.out.println("Elapsed time for linear search: " + (endTime - startTime) + " milliseconds");

startTime = new Date().getTime();

result = binarySearch(arr, key);
endTime = new Date().getTime();
System.out.println("Elapsed time for binary search: " + (endTime - startTime) + " milliseconds");
}

public static int linearSearch(int[] arr, int key) {

for (int i = 0; i < arr.length; i++) {
if (arr[i] == key) {
return i;
}
}
return -1;
}

public static int binarySearch(int[] arr, int key) {

int low = 0;
int high = arr.length - 1;

while (low <= high) {

int mid = low + (high - low) / 2;

if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}

return -1;
}
}

13 Data Structure and Algorithms Lab Manual

Exercise 2: (5)
Write down the menu-driven program for addition and subtraction and perform respective functions.
import java.util.Scanner;

public class Calculator {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

while (true) {
System.out.println("Menu:");
System.out.println("1. Addition");
System.out.println("2. Subtraction");
System.out.println("3. Exit");
System.out.print("Enter your choice: ");

int choice = scanner.nextInt();

switch (choice) {
case 1:
performAddition(scanner);
break;
case 2:
performSubtraction(scanner);
break;
case 3:
System.out.println("Exiting...");
return;
default:
System.out.println("Invalid choice. Please try again.");
}
}
}

private static void performAddition(Scanner scanner) {

System.out.print("Enter first number: ");
int num1 = scanner.nextInt();
System.out.print("Enter second number: ");
int num2 = scanner.nextInt();

int result = num1 + num2;

System.out.println("Result: " + result);
}

14 Data Structure and Algorithms Lab Manual

private static void performSubtraction(Scanner scanner) {
System.out.print("Enter first number: ");
int num1 = scanner.nextInt();
System.out.print("Enter second number: ");
int num2 = scanner.nextInt();

int result = num1 - num2;

System.out.println("Result: " + result);
}
}

15 Data Structure and Algorithms Lab Manual

LAB TASK 2 – Arrays (Static, Dynamic and Multi dimensional)

Name / Group ID: Reg. No:

Class / Section: Date: _

Time Required : 3 hrs
Programming Language : Java
Software Required : Netbeans
Hardware Required : Computer System

Arrays in Java
An array is a group of like-typed variables that are referred to by a common name.Arrays in Java work
differently than they do in C/C++. Following are some important point about Java arrays.
 In Java all arrays are dynamically allocated. (discussed below)
 Since arrays are objects in Java, we can find their length using member length. This is different
from C/C++ where we find length using sizeof.
 A Java array variable can also be declared like other variables with [] after the data type.
 The variables in the array are ordered and each have an index beginning from 0.
 Java array can be also be used as a static field, a local variable or a method parameter.
 The size of an array must be specified by an int value and not long or short.
 The direct superclass of an array type is Object.
 Every array type implements the interfaces Cloneable and java.io.Serializable.
Array can contains primitives data types as well as objects of a class depending on the definition of
array. In case of primitives data types, the actual values are stored in contiguous memory locations. In
case of objects of a class, the actual objects are stored in heap segment.

Figure 1 Creating, Initializing, and Accessing an Array

One-Dimensional Arrays
:
The general form of a one-dimensional array declaration is

type var-name[];
OR
type[] var-name;

An array declaration has two components: the type and the name. type declares the element type of the
array. The element type determines the data type of each element that comprises the array. Like array of
int type, we can also create an array of other primitive data types like char, float, double.etc or user
defined data type (objects of a class). Thus, the element type for the array d etermines what type of data
the array will hold.
16 Data Structure and Algorithms Lab Manual
Example:
// both are valid declarations
int intArray[];
or int[] intArray;

byte byteArray[];
short shortsArray[];
boolean booleanArray[];
long longArray[];
float floatArray[];
double doubleArray[];
char charArray[];

// an array of references to objects of

// the class MyClass (a class created by
// user)
MyClass myClassArray[];

Object[] ao, // array of Object

Collection[] ca; // array of
Collection
// of unknown type

Although the above first declaration establishes the fact that intArray is an array variable, no array
actually exists. It simply tells to the compiler that this (intArray) variable will hold an array of the
integer type. To link intArray with an actual, physical array of integers, you must allocate one
using new and assign it to intArray.
Instantiating an Array in Java
When an array is declared, only a reference of array is created. To actually create or give memory to
array, you create an array like this:The general form of new as it applies to one-dimensional arrays
appears as follows:
var-name = new type [size];
Here, type specifies the type of data being allocated, size specifies the number of elements in the
array, and var-name is the name of array variable that is linked to the array. That is, to use new to
allocate an array, you must specify the type and number of elements to allocate.
Example:
int intArray[]; //declaring array
intArray = new int[20]; // allocating memory to array
OR
int[] intArray = new int[20]; // combining both statements in
one Note :
1. The elements in the array allocated by new will automatically be initialized to zero (for
numeric types), false (for boolean), or null (for reference types).
2. Obtaining an array is a two-step process. First, you must declare a variable of the
desired array type. Second, you must allocate the memory that will hold the array, using
new, andassign it to the array variable. Thus, in Java all arrays are dynamically allocated.
Array Literal
In a situation, where the size of the array and variables of array are already known, array literals can
be used.
int[] intArray = new int[]{ 1,2,3,4,5,6,7,8,9,10 };
// Declaring array literal
17 Data Structure and Algorithms Lab Manual
  The length of this array determines the length of the created array.
 There is no need to write the new int[] part in the latest versions of
Java Accessing Java Array Elements using for Loop
Each element in the array is accessed via its index. The index begins with 0 and ends at (total array
size)-1. All the elements of array can be accessed using Java for Loop.

// accessing the elements of the specified array

for (int i = 0; i < arr.length; i++)
System.out.println("Element at index " + i + " : "+ arr[i]);
Implementation:
// Java program to illustrate creating an array
// of integers, puts some values in the array,
// and prints each value to standard output.

class GFG
{
public static void main (String[] args)
{
// declares an Array of
integers. int[] arr;

// allocating memory for 5

integers. arr = new int[5];

// initialize the first elements of the array

arr[0] = 10;

// initialize the second elements of the array

arr[1] = 20;

//so on...
arr[2] = 30;
arr[3] = 40;
arr[4] = 50;

// accessing the elements of the specified array

for (int i = 0; i < arr.length; i++)
System.out.println("Element at index " + i +
" : "+ arr[i]);
}
}
Output:
Element at index 0 : 10
Element at index 1 : 20
Element at index 2 : 30
Element at index 3 : 40
Element at index 4 : 50

18 Data Structure and Algorithms Lab Manual

 Figure 2 1-D Array Visualization

Example
2

class SortNames
{
public void sort(String[] a)
{
int i, pass, n =
a.length;
String tmp;
for( pass = 0; pass < n; pass++ )
{
for( i = 0; i < n-pass-1; i++ )
if( ((Comparable)a[i]).compareTo(a[i+1]) > 0)
{
tmp = a[i]; // Swap a[i], a[i+1]
a[i] = a[i+1];
a[i+1] = tmp;
}
}
}
}
////////////////////////// SortNamesDemo.java ////////////////////
class SortNamesDemo
{
public static void main(String[] args)
{
SortNames sn = new SortNames();
String[] names =
{"Ramu", "John", "Anu", "Priya", "Basha", "Prem"};
int i;
System.out.println("Unsorted names:");

for(i=0; i < names.length; i++)

System.out.println(names[i]);
sn.sort(names);

19 Data Structure and Algorithms Lab Manual

 System.out.println("Sorted names:");

20 Data Structure and Algorithms Lab Manual

 for(i=0; i < names.length; i++)
System.out.println(names[i]);
}
}

Output:
Unsorted names:
Ramu
John
Anu
Priya
Basha
Prem
Sorted names:
Anu
Basha
John
Prem
Priya
Ramu

Multidimensional Arrays
Multidimensional arrays are arrays of arrays with each element of the array holding the reference of
other array. These are also known as Jagged Arrays. A multidimensional array is created by
appending one set of square brackets ([]) per dimension.
Examples:
int[][] intArray = new int[10][20]; //a 2D array or
matrix int[][][] intArray = new int[10][20][10]; //a 3D
array Implementation
class multiDimensional
{
public static void main(String args[])
{
// declaring and initializing 2D array
int arr[][] = { {2,7,9},{3,6,1},{7,4,2} };

// printing 2D array
for (int i=0; i< 3 ; i+
+)
{
for (int j=0; j < 3 ; j++)
System.out.print(arr[i][j] + " ");

System.out.println();
}
}
}

21 Data Structure and Algorithms Lab Manual

Output:
279
361
742

Figure 3 Multidimensional Array Visualization

Passing Arrays to Methods

Like variables, we can also pass arrays to methods. For example, below program pass array to
method sum for calculating sum of array’s values.
// Java program to demonstrate
// passing of array to method
Example
class Test
{
// Driver method
public static void main(String args[])
{
int arr[] = {3, 1, 2, 5, 4};

// passing array to method m1

sum(arr);

public static void sum(int[] arr)

{
// getting sum of array
values int sum = 0;

for (int i = 0; i < arr.length; i+

+) sum+=arr[i];

System.out.println("sum of array values : " + sum);

}
}

22 Data Structure and Algorithms Lab Manual

 Output:
sum of array values : 15
Returning Arrays from Methods
As usual, a method can also return an array. For example, below program returns an array from
method m1.
Example
// Java program to demonstrate
// return of array from method

class Test
{
// Driver method
public static void main(String args[])
{
int arr[] = m1();

for (int i = 0; i < arr.length; i++)

System.out.print(arr[i]+" ");

public static int[] m1()

{
// returning array
return new int[]{1,2,3};
}
}
Output:
1 2 3

Exercises
Exercise 1: (2)
Write the program to store the students in the array having size 5. Consider the below data members
for student. Populate the array by user values.
// Java program to illustrate creating an array of
// objects
import java.util.Scanner;

class Student {
String name;
int age;
double gpa;

public Student(String name, int age, double gpa) {

this.name = name;
this.age = age;
this.gpa = gpa;

23 Data Structure and Algorithms Lab Manual

 }
}

public class Main1 {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

Student[] students = new Student[5];

for (int i = 0; i < students.length; i++) {

System.out.println("Enter details for student " + (i + 1) + ":");
System.out.print("Name: ");
String name = scanner.nextLine();
System.out.print("Age: ");
int age = scanner.nextInt();
scanner.nextLine(); // consume newline character
System.out.print("GPA: ");
double gpa = scanner.nextDouble();
scanner.nextLine(); // consume newline character

students[i] = new Student(name, age, gpa);

}

System.out.println("\nStudent Details:");
for (int i = 0; i < students.length; i++) {
System.out.println((i + 1) + ". " + students[i].name + ", Age: " + students[i].age + ", GPA: " + students[i].gpa);
}
}
}

24 Data Structure and Algorithms Lab Manual

Exercise 2: (2)
Consider the below code for interative binary search. Run the code and write down the output. And
also explain its working.

class BinarySearchDemo
{
static Object[] a = { "AP", "KA", "MH", "MP", "OR", "TN", "UP", "WB"}; static
Object key = "UP";
public static void main(String args[])
{
if( binarySearch() )
System.out.println(key + " found in the list"); else System.out.println(key + " not found in the list");
}
static boolean binarySearch()
{
int c, mid, low = 0, high = a.length-1; while( low <= high)
{
mid = (low + high)/2;
c = ((Comparable)key).compareTo(a[mid]);
if( c < 0) high = mid-1; else if( c > 0) low = mid+1;
else return true;
}
return false;
}
}

Out put:

Working:

Class and Variables:

The code defines a class BinarySearchDemo with two static variables:

a: an array of strings containing the elements to be searched.

key: the element to be searched for in the array.

Main Method:

The main method is the entry point of the program. It calls the binarySearch method and prints the result to the console. If the
binarySearch method returns true, it means the key was found in the array, and the program prints "UP found in the list".
Otherwise, it prints "UP not found in the list".
25 Data Structure and Algorithms Lab Manual
Binary Search Method:

The binarySearch method performs the actual binary search on the array a. Here's how it works:

Initialize three variables:

low: the lower bound of the search range, initially set to 0.

high: the upper bound of the search range, initially set to the length of the array minus 1.
mid: the midpoint of the search range, calculated as (low + high) / 2.
Loop until low is greater than high.
In each iteration, compare the key with the element at the mid-index of the array using the compareTo method. This method
returns:

a negative integer if key is less than the element at mid.

a positive integer if key is greater than the element at mid.
0 if key is equal to the element at mid.
Based on the comparison result:

If key is less than the element at mid, update high to mid - 1 to search in the lower half of the range.
If key is greater than the element at mid, update low to mid + 1 to search in the upper half of the range.
If key is equal to the element at mid, return true to indicate that the key was found.
If the loop completes without finding the key, return false to indicate that the key was not found.
In this specific example, the key "UP" is present in the array, so the binarySearch method returns true, and the program prints "UP
found in the list"

26 Data Structure and Algorithms Lab Manual

 Exercise 3: (1)
Write a Java program to sort a numeric array and a string array.

import java.util.Arrays;

public class SortArrays {

public static void main(String[] args) {

// Numeric array
int[] numericArray = {1789, 2035, 1899, 1456, 2013};

// Sorting numeric array

Arrays.sort(numericArray);

// Printing sorted numeric array

System.out.println("Sorted Numeric Array: " + Arrays.toString(numericArray));

// String array
String[] stringArray = {"apple", "banana", "cherry", "date", "fig"};

// Sorting string array

Arrays.sort(stringArray);

// Printing sorted string array

System.out.println("Sorted String Array: " + Arrays.toString(stringArray));
}
}

Exercise 4: (1)
Write a Java program to sum values of an array.

public class ArraySum {

public static void main(String[] args) {

// Create an array of integers

int[] numbers = {3, 4, 5, 7, 9};

// Initialize a variable to store the sum

int sum = 0;

// Iterate through the array and add each element to the sum
for (int i = 0; i < numbers.length; i++) {
 sum += numbers[i];
}

// Print the sum of the array elements

System.out.println("Sum of the array elements: " + sum);
}
}

Exercise 5: (1)
Write a Java program to calculate the average value of array elements.

public class ArraySum {

public static void main(String[] args) {

// Create an array of integers

int[] numbers = {3, 4, 5, 7, 9};

// Initialize a variable to store the sum

int sum = 0;

// Iterate through the array and add each element to the sum
for (int i = 0; i < numbers.length; i++) {
sum += numbers[i];
}

// Print the sum of the array elements

System.out.println("Sum of the array elements: " + sum);
}
}

23 Data Structure and Algorithms Lab Manual

 Exercise 6: (1)
Write a Java program to test if an array contains a specific value.

public class ArrayContains {

public static void main(String[] args) {

// Array of integers
int[] numbers = {1789, 2035, 1899, 1456, 2013};

// Specific value to search for

int target = 2013;

// Flag to indicate if the target value is found

boolean found = false;

// Iterate through the array

for (int i = 0; i < numbers.length; i++) {
// Check if the current element is equal to the target value
if (numbers[i] == target) {
// Set the flag to true and break the loop
found = true;
break;
}
}

// Print the result

System.out.println("The array contains " + target + ": " + found);
}
}

24 Data Structure and Algorithms Lab Manual

 Exercise 7: (2)
Write a Java program that returns the missing letter from an array of increasing letters (upper or lower). Assume there will always
be one omission from the array.
Sample Data:
{"A", "B", "D", "E"} -> “C”
{"a", "b", "c", "e"} -> “d”
{"p", "r", "s", "t"} -> “q”

public class MissingLetter {

public static void main(String[] args) {
String[] letters1 = {"A", "B", "D", "E"};
String[] letters2 = {"a", "b", "c", "e"};
String[] letters3 = {"p", "r", "s", "t"};

System.out.println(findMissingLetter(letters1)); // Output: "C"

System.out.println(findMissingLetter(letters2)); // Output: "d"
System.out.println(findMissingLetter(letters3)); // Output: "q"
}

public static String findMissingLetter(String[] letters) {

for (int i = 0; i < letters.length - 1; i++) {
char current = letters[i].charAt(0);
char next = letters[i + 1].charAt(0);

if (next - current > 1) {

char missing = (char) (current + 1);
return String.valueOf(missing);
}
}

return null; // Should not happen, but just in case

}
}

25 Data Structure and Algorithms Lab Manual

 LAB TASK 3 – Array based Stack implementation

Name / Group ID: Reg. No:

Class / Section: Date: _

Time Required : 3 hrs
Programming Language : Java
Software Required : Netbeans
Hardware Required : Computer System

Stack ADT
A Stack is an Abstract Data Type (ADT) used for storing the elements. The elements are stored
based on the principle of LIFO (Last In, First Out). In stack insertion and deletion of elements
take place at the same end (Top). The last element inserted will be the first to be retrieved.
• This end is called Top
• The other end is called Bottom

Stack supports the following methods:

Top(): The stack top operation gets the data from the top-most position and returns it to the user
without deleting it. The underflow state can also occur in stack top operation if stack is empty.

push(obj): Add object obj at the top of the stack.

Input: Object; Output: None.

obj pop(): Delete an item from the top of the stack and returns object obj; an error occurs if
the stack is empty.
Input: None; Output: Object.

obj peek(): Returns the top object obj on the stack , without removing it; an error occurs if
the stack is empty.
Input: None; Output: Object.

boolean isEmpty(): Returns a boolean indicating if the stack is empty.

Input: None; Output: boolean (true or false).

int size(): Returns the number of items on the stack.

Input: None; Output: integer.

boolean isUnderflow(): When stack contains equal number of elements as per its capacity and no
more elements can be added, the status of stack is known as overflow.
Input: None; Output: boolean (true or false).

Type Object may be any type that can be stored in the stack. The actual type of the object
will be provided by the user.

26 Data Structure and Algorithms Lab Manual

 Data4 Top

Data3

Data2

Data1 Bottom

Figure 4 Stack Visualization 1

Figure 5 Stack Visualization 2

Stack Implementation:

/* Java program to implement basic

stack operations */
class Stack {
static final int MAX = 1000;
int top;
int a[] = new int[MAX]; // Maximum size of Stack

boolean isEmpty()
{
return (top < 0);
}
Stack()
{
top = -1;
}
boolean push(int x){

27 Data Structure and Algorithms Lab Manual

 if (top >= (MAX - 1)) {
System.out.println("Stack Overflow");
return false;
}
else
{ a[++top] = x;
System.out.println(x + " pushed into
stack"); return true;

}
}

int pop()
{
if (top < 0) {
System.out.println("Stack Underflow");
return 0;
}
else
{ int x = a[top--];
return x;

}
}

int peek()
{
if (top < 0) {
System.out.println("Stack Underflow");
return 0;
}
else
{ int x = a[top];
return x;

}
}
}

// Driver
code class
Main {
public static void main(String args[])
{
Stack s = new
Stack(); s.push(10);
s.push(20);
s.push(30);
System.out.println(s.pop() + " Popped from stack");
}
}

28 Data Structure and Algorithms Lab Manual

 Applications of stack:

 Balancing of symbols
 Infix to Postfix /Prefix conversion
 Redo-undo features at many places like editors, photoshop.
 Forward and backward feature in web browsers
 Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram
problem.
 Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen
problem and sudoku solver
 In Graph Algorithms like Topological Sorting and Strongly Connected Components

Exercices:

Exercise 1: Display ( ) Function test in main function (2)

Write this function to display the elements of stack e.g.
import java.util.Stack;
public static void displayStack(Stack<String> stack) {
System.out.print("Stack elements: ");
for (String element : stack) {
System.out.print(element + " ");
}
System.out.println();
}
Exercise 2: Implement using stacks. (3)
Write a program using stack operations, which accepts a non-negative base 10 integer as a
parameter, and display binary representation of number.
Description: To convert a number from decimal to binary, you simply divide by two and push
reminder to stack until quotient is reached to zero, then use pop operation to display the binary
representation of number. For example, to convert (35)10 to binary, you perform the following
computation.
35/2 = 1
17/2 = 1
8/2 = 0
4/2 = 0

29 Data Structure and Algorithms Lab Manual

 2/2 = 0
1
If you examine the remainders from the last division to the first one, writing them down as you go,
you will get the following sequence: 100011. i.e. (100011)2=(35)10

import java.util.Stack;
public class DecimalToBinary {
public static void decimalToBinary(int decimalNumber) {
if (decimalNumber < 0) {
System.out.println("Invalid input. Please enter a non-negative integer.");
return;
}

Stack<Integer> stack = new Stack<>();

while (decimalNumber > 0) {

int reminder = decimalNumber % 2;
stack.push(reminder);
decimalNumber /= 2;
}

while (!stack.isEmpty()) {
System.out.print(stack.pop());
}

System.out.println();
}

public static void main(String[] args) {

decimalToBinary(35); // Output: 100011
decimalToBinary(10); // Output: 1010
decimalToBinary(0); // Output: 0
}
}

30 Data Structure and Algorithms Lab Manual

 Exercise 3: (5)

Write a program to compare opening and closing brackets in expression. This program takes an
expression in the form of string and scan it character by character. Finally the output of the program is
the valid or invalid expression.

Algorithm: To do this comparison a stack ADT can be used to keep track of the scope
delimiters encountered while scanning the expression.
• Whenever a scope “opener” is encountered, it can be “pushed” onto a stack
• Whenever a scope “ender” is encountered, the stack is examined:
– If the stack is “empty”, there is no matching scope “opener” and the expression is invalid.
– If the stack is not empty, we pop the stack and check if the “popped” item corresponds to
the scope ender
– If match occurs, we continue scanning the expression
• When end of the expression string is reached, the stack must be empty, otherwise one or
more opened scopes have not been closed and the expression is invalid
import java.util.Stack;

public class DecimalToBinary {

public static void decimalToBinary(int decimalNumber) {
if (decimalNumber < 0) {
System.out.println("Invalid input. Please enter a non-negative integer.");
return;
}

Stack<Integer> stack = new Stack<>();

while (decimalNumber > 0) {

int reminder = decimalNumber % 2;
stack.push(reminder);
decimalNumber /= 2;
}

while (!stack.isEmpty()) {
System.out.print(stack.pop());
}

System.out.println();
}

public static void main(String[] args) {

decimalToBinary(35); // Output: 100011
decimalToBinary(10); // Output: 1010
decimalToBinary(0); // Output: 0
}
}
 LAB TASK 4 – Array based Queue implementation

Name / Group ID: Reg. No:

Class / Section: Date: _

Time Required : 3 hrs
Programming Language : Java
Software Required : Netbeans
Hardware Required : Computer System

Queue ADT

In queue, insertion and deletion happen at the opposite ends, so implementation is not as simple
as stack.
To implement a queue using array, create an array arr of size n and take two
variables front and rear both of which will be initialized to 0 which means the queue is currently
empty. Element rear is the index upto which the elements are stored in the array and front is the
index of the first element of the array.

Some of the implementation of queue operations are as follows:

Enqueue: Addition of an element to the queue. Adding an element will be performed after
checking whether the queue is full or not. If rear < n which indicates that the array is not full
then store the element at arr[rear] and increment rear by 1 but if rear == n then it is said to be an
Overflow condition as the array is full.

Dequeue: Removal of an element from the queue. An element can only be deleted when there is
at least an element to delete i.e. rear > 0. Now, element at arr[front] can be deleted but all the
remaining elements have to shifted to the left by one position in order for the dequeue operation
to delete the second element from the left on another dequeue operation.

Front: Get the front element from the queue i.e. arr[front] if queue is not empty.

Display: Print all element of the queue. If the queue is non-empty, traverse
and print all the elements from index front to rear.

Data Structure and Algorithms Lab Manual

31
 Figure 6 Queue Visualization

Queue Implementation:

// Java program to implement a queue using an array

class Queue {
private static int front, rear,
capacity; private static int queue[];

Queue(int c)
{
front = rear =
0; capacity = c;
queue = new int[capacity];
}

// function to insert an element

32 Data Structure and Algorithms Lab Manual

// at the rear of the queue
static void queueEnqueue(int data)
{
// check queue is full or not
if (capacity == rear) {
System.out.printf("\nQueue is full\n");
return;
}

// insert element at the

rear else {
queue[rear] =
data; rear++;
}
return;
}

// function to delete an element

// from the front of the
queue static void
queueDequeue()
{
// if queue is empty
if (front == rear) {
System.out.printf("\nQueue is empty\n");
return;
}

// shift all the elements from index 2 till rear

// to the right by
one else {
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}

// store 0 at rear indicating there's no

element if (rear < capacity)
queue[rear] = 0;

// decrement
rear rear--;
}
return;
}

33 Data Structure and Algorithms Lab Manual

 // print queue elements
static void
queueDisplay()
{
int i;
if (front == rear) {
System.out.printf("\nQueue is Empty\n");
return;
}

// traverse front to rear and print

elements for (i = front; i < rear; i++) {
System.out.printf(" %d <-- ", queue[i]);
}
return;
}

// print front of queue

static void
queueFront()
{
if (front == rear) {
System.out.printf("\nQueue is Empty\n");
return;
}
System.out.printf("\nFront Element is: %d", queue[front]);
return;
}
}

public class StaticQueueinjava {

// Driver code
public static void main(String[] args)
{
// Create a queue of capacity
4 Queue q = new Queue(4);

// print Queue
elements
q.queueDisplay();

// inserting elements in the

queue q.queueEnqueue(20);
q.queueEnqueue(30);
q.queueEnqueue(40);
q.queueEnqueue(50);

// print Queue
elements
q.queueDisplay();
34 Data Structure and Algorithms Lab Manual
 // insert element in the
queue q.queueEnqueue(60);

35 Data Structure and Algorithms Lab Manual

 // print Queue
elements
q.queueDisplay();

q.queueDequeue();
q.queueDequeue();
System.out.printf("\n\nafter two node deletion\n\n");
// print Queue
elements
q.queueDisplay();

// print front of the

queue q.queueFront();
}
}

Output:

Queue is Empty
20 <-- 30 <-- 40 <-- 50 <--
Queue is full
20 <-- 30 <-- 40 <-- 50 <--

after two node

deletion 40 <-- 50 <--

Front Element is: 40

Applications of Queue

 Queue is useful in CPU scheduling, Disk Scheduling. When multiple processes require
CPU at the same time, various CPU scheduling algorithms are used which are implemented
using Queue data structure.
 When data is transferred asynchronously between two processes.Queue is used for
synchronization. Examples : IO Buffers, pipes, file IO, etc.
 In print spooling, documents are loaded into a buffer and then the printer pulls them off
the buffer at its own rate. Spooling also lets you place a number of print jobs on a queue
instead ofwaiting for each one to finish before specifying the next one.
 Breadth First search in a Graph .It is an algorithm for traversing or searching graph
data structures. It starts at some arbitrary node of a graph and explores the neighbor nodes
first, before moving to the next level neighbors.This Algorithm uses Queue data structure.

36 Data Structure and Algorithms Lab Manual

 Exercices

Exercise 1: (4)
Write a menu driven program to perform different operations with queue such a Enqueue ( ),
Dequeue( ) and DisplayQueue( ).
import java.util.Scanner;

class Queue {
private int maxSize;
private int[] queueArray;
private int front;
private int rear;
private int numberOfItems;

public Queue(int size) {

maxSize = size;
queueArray = new int[maxSize];
front = 0;
rear = -1;
numberOfItems = 0;
}

public void insert(int value) {

if (rear == maxSize - 1)
rear = -1;
queueArray[++rear] = value;
numberOfItems++;
}

public int remove() {

int temp = queueArray[front++];
if (front == maxSize)
front = 0;
numberOfItems--;
return temp;
}

public boolean isEmpty() {

return (numberOfItems == 0);
}

public void display() {

if (isEmpty()) {
System.out.println("Queue is empty");
} else {
for (int i = front; i < front + numberOfItems; i++) {
System.out.print(queueArray[i % maxSize] + " ");
}
System.out.println();
}
}
}

public class QueueApp {

public static void main(String[] args) {
Scanner input = new Scanner(System.in);
Queue theQueue = new Queue(5);
int choice;
37 Data Structure and Algorithms Lab Manual
 int value;

do {
System.out.println("\n1. Insert");
System.out.println("2. Remove");
System.out.println("3. Display");
System.out.println("4. Quit");
System.out.print("Enter your choice: ");
choice = input.nextInt();

switch (choice) {
case 1:
System.out.print("Enter the value to insert: ");
value = input.nextInt();
theQueue.insert(value);
break;
case 2:
value = theQueue.remove();
if (value != -1)
System.out.println("Removed: " + value);
else
System.out.println("Queue is empty");
break;
case 3:
theQueue.display();
break;
case 4:
System.out.println("Goodbye!");
break;
default:
System.out.println("Invalid choice");
}
} while (choice != 4);
}
}

38 Data Structure and Algorithms Lab Manual

Exercise 2: (6)
In this Exercise, you have to take a single string as input. Using this input string, you have to create multiple
queues in which each queue will comprise of separate word appeared in input string. At the end, you will again
concatenate all queues to a single queue.
Example:
String = “Data Structure and
Algo” Q1 = D → a → t → a
Q2 = S → t → r → u → c → t → u → r → e
Q3 = a → n → d
Q4 = A → l → g → o
At the end concatenate all queues and display them.
Q1 → Q2 → Q3 → Q4

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class QueueExercise {

public static void main(String[] args) {
// Take input from the user
Scanner scanner = new Scanner(System.in);
System.out.print("Enter a string: ");
String inputString = scanner.nextLine();
scanner.close();

// Split the input string into words

String[] words = inputString.split("\\s+");

// Create a queue for each word

Queue<Character>[] queues = new LinkedList[words.length];
for (int i = 0; i < words.length; i++) {
queues[i] = new LinkedList<>();
for (char c : words[i].toCharArray()) {
queues[i].add(c);
}
}

// Concatenate all queues into a single queue

Queue<Character> concatenatedQueue = new LinkedList<>();
for (Queue<Character> queue : queues) {
while (!queue.isEmpty()) {
concatenatedQueue.add(queue.remove());
}
}

// Display the concatenated queue

System.out.println("Concatenated Queue: " + concatenatedQueue);
}
}

37 Data Structure and Algorithms Lab Manual

37 Data Structure and Algorithms Lab Manual
 LAB TASK 5 – Circular Queue and Implementation of Deque using circular array

Name / Group ID: Reg. No:

Class / Section: Date: _

Time Required : 3 hrs
Programming Language : Java
Software Required : Netbeans
Hardware Required : Computer System

Circular Queue ADT

Circular Queue is a linear data structure in which the operations are performed based on FIFO
(First In First Out) principle and the last position is connected back to the first position to make a
circle. It is also called ‘Ring Buffer’.

Figure 7 Cicular Queue Visulaization

In a normal Queue, we can insert elements until queue becomes full. But once queue becomes full, we
can not insert the next element even if there is a space in front of queue.

37 Data Structure and Algorithms Lab Manual

 Figure 8 Visulaization of Circular Queue through its operations

Operations on Circular Queue:

Front: Get the front item from

queue. Rear: Get the last item from

queue.

enQueue(value) This function is used to insert an element into the circular queue. In a circular queue,
the new element is always inserted at Rear position.
Steps:
1. Check whether queue is Full – Check ((rear == SIZE-1 && front == 0) || (rear == front-1)).
2. If it is full then display Queue is full. If queue is not full then, check if (rear == SIZE – 1
&& front != 0) if it is true then set rear=0 and insert element.

deQueue() This function is used to delete an element from the circular queue. In a circular queue, the
element is always deleted from front position.
Steps:
3. Check whether queue is Empty means check (front==-1).
4. If it is empty then display Queue is empty. If queue is not empty then step 3
5. Check if (front==rear) if it is true then set front=rear= -1 else check if (front==size-1), if it
is true then set front=0 and return the element.

39 Data Structure and Algorithms Lab Manual

Deque
Deque or Double Ended Queue is a generalized version of Queue data structure that allows insert and
delete at both ends.In previous post we had discussed introduction of deque. Now in this post we see
how we implement deque Using circular array.

Operations on Deque:

Mainly the following four basic operations are performed on

queue: insetFront(): Adds an item at the front of Deque.

insertRear(): Adds an item at the rear of Deque.

deleteFront(): Deletes an item from front of

Deque. deleteRear(): Deletes an item from rear of

Deque.

In addition to above operations, following operations are also supported

getFront(): Gets the front item from queue.

getRear(): Gets the last item from queue.

isEmpty(): Checks whether Deque is empty or not.

isFull(): Checks whether Deque is full or not.

Figure 9 Deque visualization

40 Data Structure and Algorithms Lab Manual

Circular array implementation deque

For implementing deque, we need to keep track of two indices, front and rear. We enqueue(push)
an item at the rear or the front end of qedue and dequeue(pop) an item from both rear and front end.
Working
1. Create an empty array ‘arr’ of size ‘n’
initialize front = -1 , rear = 0
Inserting First element in deque, at either front or rear will lead to the same result.

After insert Front Points = 0 and Rear points = 0

Insert Elements at Rear end

a). First we check deque if Full or

Not b). IF Rear == Size-1
then reinitialize Rear = 0
; Else increment Rear by '1'
and push current key into Arr[ rear ] =
key Front remain same.
Insert Elements at Front end

a). First we check deque if Full or Not

b). IF Front == 0 || initial position, move
Front to points last index of
array
front = size - 1
Else decremented front by '1' and
push current key into Arr[ Front] =
key
Rear remain same.

41 Data Structure and Algorithms Lab Manual

Delete Element From Rear end

a). first Check deque is Empty or

Not b). If deque has only one
element
front = -1 ; rear =-1 ;
Else IF Rear points to the first index of array
it's means we have to move rear to points
last index [ now first inserted element at
front end become rear end ]
rear = size-1 ;
Else || decrease rear by '1'
rear = rear-1;
Delete Element From Front end

a). first Check deque is Empty or

Not b). If deque has only one
element
front = -1 ; rear =-1 ;
Else IF front points to the last index of the array
it's means we have no more elements in array
so we move front to points first index of array
front = 0 ;
Else || increment Front by '1'
front = front+1;
42 Data Structure and Algorithms Lab Manual
Program

// Java implementation of De-queue using circular

// array

// A structure to represent a
Deque class Deque
{
static final int MAX = 100;
int arr[];
int front;
int rear;
int size;

public Deque(int size)

{
arr = new int[MAX];
front = -1;
rear = 0;
this.size =
size;
}

/*// Operations on Deque:

void insertfront(int key);
void insertrear(int key);
void deletefront();
void deleterear();
bool isFull();
bool isEmpty();
int getFront();
int getRear();*/

// Checks whether Deque is full or

not. boolean isFull()
{
return ((front == 0 && rear == size-1)||
front == rear+1);
}

43 Data Structure and Algorithms Lab Manual

// Checks whether Deque is empty or
not. boolean isEmpty ()
{
return (front == -1);
}

// Inserts an element at
front void insertfront(int
key)
{
// check whether Deque if full or
not if (isFull())
{
System.out.println("Overflow");
return;
}

// If queue is initially empty

if (front == -1)
{
front = 0;
rear = 0;
}

// front is at first position of

queue else if (front == 0)
front = size - 1 ;

else // decrement front end by

'1' front = front-1;

// insert current element into

Deque arr[front] = key ;
}

// function to inset element at rear end

// of Deque.
void insertrear(int key)
{
if (isFull())
{
System.out.println(" Overflow ");
return;
}

// If queue is initially empty

if (front == -1)
{
front = 0;
rear = 0;
}

44 Data Structure and Algorithms Lab Manual

 // rear is at last position of
queue else if (rear == size-1)
rear = 0;

// increment rear end by

'1' else
rear = rear+1;

// insert current element into

Deque arr[rear] = key ;
}

// Deletes element at front end of

Deque void deletefront()
{
// check whether Deque is empty or not
if (isEmpty())
{
System.out.println("Queue Underflow\n");
return ;
}

// Deque has only one element

if (front == rear)
{
front = -1;
rear = -1;
}
else
// back to initial position
if (front == size -1)
front = 0;

else // increment front by '1' to remove current

// front value from
Deque front = front+1;
}

// Delete element at rear end of

Deque void deleterear()
{
if (isEmpty())
{
System.out.println(" Underflow");
return ;
}

// Deque has only one element

if (front == rear)
{front = -1;

45 Data Structure and Algorithms Lab Manual

 rear = -1;
}
else if (rear == 0)
rear = size-1;
else
rear = rear-1;
}

// Returns front element of

Deque int getFront()
{
// check whether Deque is empty or not
if (isEmpty())
{
System.out.println(" Underflow");
return -1 ;
}
return arr[front];
}

// function return rear element of

Deque int getRear()
{
// check whether Deque is empty or not
if(isEmpty() || rear < 0)
{
System.out.println(" Underflow\n");
return -1 ;
}
return arr[rear];
}

// Driver program to test above

function public static void
main(String[] args)
{

Deque dq = new Deque(5);

System.out.println("Insert element at rear end : 5

"); dq.insertrear(5);

System.out.println("insert element at rear end : 10

"); dq.insertrear(10);

System.out.println("get rear element : "+ dq.getRear());

dq.deleterear();
System.out.println("After delete rear element new rear become : " +
dq.getRear());
System.out.println("inserting element at front end");

46 Data Structure and Algorithms Lab Manual

 dq.insertfront(15);

System.out.println("get front element: "

+dq.getFront()); dq.deletefront();

System.out.println("After delete front element new front become : " +

+ dq.getFront());

}
}

Output:
insert element at rear end : 5
insert element at rear end : 10
get rear element : 10
After delete rear element new rear become :
5 inserting element at front end
get front element : 15
After delete front element new front become : 5

Exercise: (10)
Run the given program and write down the output and explain the steps.
//Java program to find circular tour for a truck

import java.util.*;

public class PetrolPumpProblem {

// Inner class representing a petrol pump
static class PetrolPump {
int petrol;
int distance;

public PetrolPump(int petrol, int distance) {

this.petrol = petrol;
this.distance = distance;
}
}

// Method to find the starting point of the tour

static int printTour(PetrolPump arr[], int n) {
47 Data Structure and Algorithms Lab Manual
 int start = 0;
int end = 1;
int curr_petrol = arr[start].petrol - arr[start].distance;

while (end != start) {

while (curr_petrol < 0 && start != end) {
curr_petrol -= arr[start].petrol - arr[start].distance;
start = (start + 1) % n;

if (start == 0) {
return -1;
}
}
curr_petrol += arr[end].petrol - arr[end].distance;
end = (end + 1) % n;
}

return (curr_petrol >= 0) ? start : -1;

}

public static void main(String[] args) {

// Create an array of petrol pumps
PetrolPump[] arr = {
new PetrolPump(6, 4),
new PetrolPump(3, 6),
new PetrolPump(7, 3)
};

// Find the starting point of the tour

int start = printTour(arr, arr.length);

// Print the result

System.out.println(start == -1 ? "No Solution" : "Start = " + start);
}
}
Output

48 Data Structure and Algorithms Lab Manual

 LAB TASK 9 – Binary Trees, Binary Tree Traversals and Level Order Traversal

Name / Group ID: Reg. No:

Class / Section: Date: _

Time Required : 3 hrs
Programming Language : Java
Software Required : Netbeans
Hardware Required : Computer System

Binary Tree Data Structure

A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary
tree can have only 2 children, we typically name them the left and right child.

A Binary Tree node contains following parts.

1. Data
2. Pointer to left child
3. Pointer to right child

Node Code
/* Class containing left and right child of
current node and key value*/
class Node
{
int key;
Node left, right;
public Node(int
item)
{
key = item;
left = right = null;

49 Data Structure and Algorithms Lab Manual

 }
}

Binary Trees Code

/* Class containing left and right child of current
node and key value*/
class Node
{
int key;
Node left, right;
public Node(int
item)
{
key = item;
left = right = null;
}
}
// A Java program to introduce Binary Tree
class BinaryTree
{
// Root of Binary
Tree Node root;

// Constructors
BinaryTree(int key)
{
root = new Node(key);
}
BinaryTree()
{
root = null;
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*create root*/
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new
Node(4);
}
}

50 Data Structure and Algorithms Lab Manual

Complete Program

// Java program to insert element in binary

tree import java.util.LinkedList;
import java.util.Queue;
static class Node {
int key;
Node left, right;

// constructor
Node(int key){
this.key = key;
left = null;
right = null;
}
}
public class GFG {
/* A binary tree node has key, pointer
to left child and a pointer to right child
*/ static Node root;
static Node temp = root;
/* Inorder traversal of a binary
tree*/ static void inorder(Node
temp)
{
if (temp == null)
return;

inorder(temp.left);
System.out.print(temp.key+" ");
inorder(temp.right);
}

/*function to insert element in binary tree

*/ static void insert(Node temp, int key)
{
Queue<Node> q = new
LinkedList<Node>(); q.add(temp);

// Do level order traversal until we find

// an empty place.
while (!q.isEmpty()) {
temp = q.peek();
q.remove();

51 Data Structure and Algorithms Lab Manual

 if (temp.left == null) {
temp.left = new
Node(key); break;
} else
q.add(temp.left);

if (temp.right == null) {
temp.right = new
Node(key); break;
} else
q.add(temp.right);
}
}

// Driver code
public static void main(String args[])
{
root = new Node(10);
root.left = new Node(11);
root.left.left = new
Node(7); root.right = new
Node(9);
root.right.left = new Node(15);
root.right.right = new
Node(8);

System.out.print( "Inorder traversal before insertion:");

inorder(root);

int key = 12;

insert(root, key);

System.out.print("\nInorder traversal after

insertion:"); inorder(root);
}
}

Output:
Inorder traversal before insertion: 7 11 10 15 9 8
Inorder traversal after insertion: 7 11 12 10 15 9 8

Binary Tree Traversals

(a) Preorder
(b) Inorder, and
52 Data Structure and Algorithms Lab Manual
(c) Postorder.

53 Data Structure and Algorithms Lab Manual

Program

class Node
{ Object data;
Node left;
Node right;
Node( Object d ) // constructor
{ data = d; }
}
class BinaryTree
{
Object tree[];
int maxSize;
java.util.Stack<Node> stk = new java.util.Stack<Node>();

BinaryTree( Object a[], int n ) // constructor

{ maxSize = n;
tree = new Object[maxSize]; for( int
i=0; i<maxSize; i++ )
tree[i] = a[i];
}
public Node buildTree( int index )
{ Node p = null;
if( tree[index] != null )
{ p = new Node(tree[index]);

p.left = buildTree(2*index+1);
p.right =
buildTree(2*index+2);
}
return p;
}
/* Recursive methods - Binary tree traversals */ public void
inorder(Node p) {

if( p != null )
{
inorder(p.left);
System.out.print(p.data + "
"); inorder(p.right);
}
}
public void preorder(Node p)
{
if( p != null )
{
System.out.print(p.data + " ");
54 Data Structure and Algorithms Lab Manual
 preorder(p.left);
preorder(p.right);
}
}
public void postorder(Node p)
{
if( p != null )
{
postorder(p.left);
postorder(p.right);
System.out.print(p.data + "
");
}
}
/* Non-recursive methods - Binary tree traversals */ public void
preorderIterative(Node p) {

if(p == null )
{ System.out.println("Tree is empty");
return;
}
stk.push(p);
while( !stk.isEmpty() )
{
p = stk.pop();
if( p != null )
{
System.out.print(p.data + "
"); stk.push(p.right);
stk.push(p.left);
}
}
}
public void inorderIterative(Node p)
{
if(p == null )
{ System.out.println("Tree is empty"); return;
}
while( !stk.isEmpty() || p != null )
{
if( p != null )
{ stk.push(p); // push left-most path onto stack p =
p.left;
}
else
{
p = stk.pop(); // assign popped node to p System.out.print(p.data
+ " "); // print node data p = p.right; // move p to right subtree
}
}
55 Data Structure and Algorithms Lab Manual
 }

}
56 Data Structure and Algorithms Lab Manual
 public void postorderIterative(Node p)
{
if(p == null )
{ System.out.println("Tree is empty"); return;
}
Node tmp = p;
while( p != null
)
{
while( p.left != null )
{ stk.push(p); p = p.left;
}
while( p != null && (p.right == null || p.right == tmp ))
{ System.out.print(p.data + " "); // print node data tmp = p;
if( stk.isEmpty() )
return;
p = stk.pop();
}
stk.push(p);
p = p.right;
}
}
} // end of BinaryTree class
//////////////////////// BinaryTreeDemo.java //////////////////////
class BinaryTreeDemo
{
public static void main(String args[])
{
Object arr[] = {'E', 'C', 'G', 'A', 'D', 'F', 'H', null,'B', null,
null, null, null, null, null, null, null, null, null};
BinaryTree t = new BinaryTree( arr, arr.length );

Node root = t.buildTree(0); // buildTree() returns reference to

root System.out.print("\n Recursive Binary Tree Traversals:");
System.out.print("\n inorder: "); t.inorder(root);

System.out.print("\n preorder: ");

t.preorder(root);
System.out.print("\n postorder: ");
t.postorder(root);
System.out.print("\n Non-recursive Binary Tree
Traversals:"); System.out.print("\n inorder: ");
t.inorderIterative(root);
System.out.print("\n preorder: ");
t.preorderIterative(root);

}
57 Data Structure and Algorithms Lab Manual
 System.out.print("\n postorder: ");
t.postorderIterative(root);

}
58 Data Structure and Algorithms Lab Manual
 }

Output:
Recursive Binary Tree
Traversals: inorder: A B C D E F
G H preorder: E C A B D G F H
postorder: B A D C F H G E
Non-recursive Binary Tree
Traversals: inorder: A B C D E F G H
preorder: E C A B D G F H
postorder: B A D C F H G
E

Level Order Traversal

Traverse a binary tree level by level. That is, the root is visited first, then the immediate
children of the root (from left to right), then grandchildren of the root (from left to right), and
so on. The algorithm uses a queue to keep track of the children of a node until it is time to
visit them. This algorithm is also known as breadth-first traversal.
1. Initialize a queue.
2. Insert the root into the queue.
3. Repeat steps 4 to 7 until the queue is empty.
4. Delete the node from the queue.
5. Process the node being deleted.
6. If the left child of node exists (is not null), insert it into the queue.
7. If the right child of node exists (is not null), insert it into the queue

59 Data Structure and Algorithms Lab Manual

Program
class Node
{
Object data;
Node left;
Node right;
Node( Object d ) // constructor
{ data = d; }
}
class BinaryTree
{ Object tree[]; int maxSize;
java.util.LinkedList<Node> que =

new java.util.LinkedList<Node>();
BinaryTree( Object a[], int n ) // constructor { maxSize =
n;
tree = new Object[maxSize];
for( int i=0; i<maxSize; i++
)
tree[i] = a[i];
}
public Node buildTree( int index )
{ Node p = null;
if( tree[index] != null )
{ p = new Node(tree[index]);
p.left = buildTree(2*index+1);
p.right =
buildTree(2*index+2);
}
return p;
}

public void levelorder(Node p)

{
que.addLast(p);
while( !que.isEmpty() )
{
p = que.removeFirst();
System.out.print(p.data + "
"); if(p.left != null)
que.addLast(p.left);
if(p.right != null)
que.addLast(p.right);
}
}
} // end of BinaryTree class
60 Data Structure and Algorithms Lab Manual
//////////////////////// LevelOrderTraversal.java //////////////////////
class LevelOrderTraversal
{

61 Data Structure and Algorithms Lab Manual

 public static void main(String args[])
{
Object arr[] = {'E', 'C', 'G', 'A', 'D', 'F', 'H', null,'B', null,
null, null, null, null, null, null, null, null, null};
BinaryTree t = new BinaryTree( arr, arr.length );
Node root = t.buildTree(0); // buildTree() returns reference to root

System.out.print("\n Level Order Tree Traversal:

"); t.levelorder(root);
}
}

Output:
Level Order Tree Traversal: E C G A D F H B
Exersises

Exercise 1: (10)
Write a program which should implement a binary tree using a static array of size 10. Elements of this
array of integer type, user will provide values as input for elements of this array. Your program should
allow searching of a value specified by user in tree and it will also provide deletion of a value specified
by user.

import java.util.Scanner;

public class BinaryTree {

private static final int MAX_SIZE = 10;
private int[] tree;

public BinaryTree() {
tree = new int[MAX_SIZE];
}

public static void main(String[] args) {

BinaryTree bt = new BinaryTree();
Scanner scanner = new Scanner(System.in);

System.out.println("Enter values for the binary tree (type 'done' when finished):");
while (true) {
String input = scanner.nextLine();
if (input.equalsIgnoreCase("done")) {
break;
}
int value = Integer.parseInt(input);
bt.insert(value);
}

System.out.println("Enter a value to search for:");

int searchValue = scanner.nextInt();
if (bt.search(searchValue)) {
System.out.println("Value found!");

62 Data Structure and Algorithms Lab Manual

} else {
System.out.println("Value not found.");
}

System.out.println("Enter a value to delete:");

int deleteValue = scanner.nextInt();
bt.delete(deleteValue);

System.out.println("Tree after deletion:");

bt.printTree();
}

private void insert(int value) {

int i = 0;
while (i < MAX_SIZE && tree[i] != 0) {
i = (value < tree[i]) ? (2 * i + 1) : (2 * i + 2);
}
if (i < MAX_SIZE) {
tree[i] = value;
} else {
System.out.println("Tree is full.");
}
}

private boolean search(int value) {

int i = 0;
while (i < MAX_SIZE && tree[i] != value) {
i = (value < tree[i]) ? (2 * i + 1) : (2 * i + 2);
}
return i < MAX_SIZE && tree[i] == value;
}

private void delete(int value) {

int i = 0;
while (i < MAX_SIZE && tree[i] != value) {
i = (value < tree[i]) ? (2 * i + 1) : (2 * i + 2);
}
if (i < MAX_SIZE && tree[i] == value) {
tree[i] = 0;
} else {
System.out.println("Value not found.");
}
}

private void printTree() {

for (int i = 0; i < MAX_SIZE; i++) {
System.out.print(tree[i] + " ");
}
System.out.println();
}
}

63 Data Structure and Algorithms Lab Manual

 Exercise 2: (10)
Write a program which should implement a binary tree using array. Elements of array are objects of
“student” class. “student” class contains attributes (privately defined) reg_no(int), st_name (string) and
cgpa (float). “student” class should also contain member functions (publicly defined); constructor,
input and output functions. User will insert objects of class “student” array of binary tree, values of
attributes of objects will be provided by user. Program should insert the values using level order
insertion technique.

import java.util.Scanner;

class Student {
private int regNo;
private String stName;
private float cgpa;

public Student() {
this.regNo = 0;
this.stName = "";
this.cgpa = 0.0f;
}

public Student(int regNo, String stName, float cgpa) {

this.regNo = regNo;
this.stName = stName;
this.cgpa = cgpa;
}

public void input() {

Scanner scanner = new Scanner(System.in);
System.out.print("Enter registration number: ");
regNo = scanner.nextInt();
System.out.print("Enter student name: ");
stName = scanner.next();
System.out.print("Enter CGPA: ");
cgpa = scanner.nextFloat();
}

64 Data Structure and Algorithms Lab Manual

 public void output() {
System.out.println("Registration Number: " + regNo);
System.out.println("Student Name: " + stName);
System.out.println("CGPA: " + cgpa);
}
}

public class BinaryTree1 {

private static final int MAX_SIZE = 10;
private final Student[] tree;

public BinaryTree1() {
tree = new Student[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++) {
tree[i] = new Student();
}
}

public void insert(Student student) {

int i = 0;
while (i < MAX_SIZE && tree[i] != null) {
i++;
}
if (i < MAX_SIZE) {
tree[i] = student;
} else {
System.out.println("Tree is full.");
}
}

public void levelOrderInsertion() {

Scanner scanner = new Scanner(System.in);
for (int i = 0; i < MAX_SIZE; i++) {
Student student = new Student();
student.input();
insert(student);
}
}

public void printTree() {

for (int i = 0; i < MAX_SIZE; i++) {
if (tree[i] != null) {
tree[i].output();
System.out.println();
}
}
}

public static void main(String[] args) {

BinaryTree1 bt = new BinaryTree1();
bt.levelOrderInsertion();
bt.printTree();
}
}

65 Data Structure and Algorithms Lab Manual

66 Data Structure and Algorithms Lab Manual
67 Data Structure and Algorithms Lab Manual
68 Data Structure and Algorithms Lab Manual
 LAB TASK 10 – Binary Search Trees

Name / Group ID: Reg. No:

Class / Section: Date: _

Time Required : 3 hrs
Programming Language : Java
Software Required : Netbeans
Hardware Required : Computer System

Binary Search Tree

A binary search tree is a binary tree that is either empty or in which every node contains a key
and satisfies the conditions:
The key in the left child of a node (if it exists) is less than the key in its parent node.
The key in the right child of a node (if it exists) is greater than the key in its parent
node. The left and right subtrees of the root are again binary search trees.
The first two properties describe the ordering relative to the key in the root node, and that the third
property extends them to all nodes in the tree; hence we can continue to use the recursive structure
of the binary tree. After we examine the root of the tree, we shall move to either its left or right
subtree, and this subtree is again a binary search tree. Thus we can use the same method again on
this smaller tree. This definition assumes that no duplicate keys are permitted.

45

25 65
15 30 55 75

10 20 50 60 80

Binary search tree operations

class BSTNode
{
int data;
BSTNode left;
BSTNode right;
BSTNode( int d ) { data = d; }// constructor

69 Data Structure and Algorithms Lab Manual

 }
class BinarySearchTree{

public BSTNode insertTree(BSTNode p, int key) // create BST {

if( p == null )
p = new
BSTNode(key); else if( key
< p.data)
p.left = insertTree( p.left, key);
else p.right = insertTree( p.right,
key);
return p; // return root
}
public BSTNode search(BSTNode root, int key)
{
BSTNode p = root; while(
p != null )
{ if( key == p.data ) return p; else if( key < p.data
) p = p.left; else p = p.right;
}
return null;
}
public int leafNodes(BSTNode p)
{
int count = 0;
if( p != null)
{ if((p.left == null) && (p.right == null))
count = 1;
else
count = count + leafNodes(p.left)
+ leafNodes(p.right);
}
return count;
}
public BSTNode deleteTree(BSTNode root, int key)
{
BSTNode p; // refer to node to be deleted
BSTNode parent = root; // refer to parent of node to be
deleted
BSTNode inorderSucc; //refer to inorder succ. of node to be
deleted if(root == null)
{ System.out.println("Tree is empty");
return null;
}
p = root; // initialize p with root
/* find node being deleted & its parent */
while( p != null && p.data != key)
70 Data Structure and Algorithms Lab Manual
 { parent = p;
if( key < p.data) p = p.left; else p
= p.right;

71 Data Structure and Algorithms Lab Manual

 }
if( p == null )
{ System.out.println("\n Node " + key + " not found for deletion"); return null;
}
/* find inorder successor of the node being deleted and its parent */

if(p.left != null && p.right != null) // case-3

{ parent = p; inorderSucc =
p.right; while(inorderSucc.left
!= null)

{
parent = inorderSucc; inorderSucc
= inorderSucc.left;
}
p.data = inorderSucc.data;
p = inorderSucc;
} // case-
if(p.left == null && p.right == null) 1
{
if( parent.left == p ) parent.left = null;
else parent.right = null;
}
if(p.left == null && p.right != null) // case-2(a)
{
if(parent.left == p) parent.left =
p.right; else parent.right = p.right;
} // case-
if(p.left != null && p.right == 2(b)
null)
{
if(parent.left == p) parent.left =
p.left; else parent.right = p.left;
}
return root;
}
// 'p' starts
public void inorder(BSTNode with root
p)
{ if( p != null )
{ inorder(p.left);
System.out.print(p.data + "
"); inorder(p.right);
}
}
public void preorder(BSTNode p)
{ if( p != null )
{ System.out.print(p.data + " ");
preorder(p.left);
preorder(p.right);
72 Data Structure and Algorithms Lab Manual
 }
}
public void postorder(BSTNode p)

73 Data Structure and Algorithms Lab Manual

 { if( p != null )
{ postorder(p.left);
postorder(p.right);
System.out.print(p.data + " ");
}
}
} // end of BinarySearchTree class
////////////////////// BinarySearchTreeDemo.java //////////////////// class
BinarySearchTreeDemo
{ public static void main(String args[])
{
int arr[] = { 45, 25, 15, 10, 20, 30, 65, 55, 50, 60, 75, 80 };
BinarySearchTree bst = new BinarySearchTree();

BSTNode root = null;

// build tree by repeated
insertions for( int i = 0; i <
arr.length; i++ )
root = bst.insertTree( root, arr[i]);
BSTNode root2 = root; // copy
BST
int key = 66;
BSTNode item = bst.search(root2,
key); if( item != null )
System.out.print("\n item found: " + item.data);
else System.out.print("\n Node " + key + " not
found");
System.out.print("\n Number of leaf nodes: " + bst.leafNodes(root));

System.out.print("\n Inorder: ");

bst.inorder(root);
System.out.print("\n Preorder: ");
bst.preorder(root);
System.out.print("\n Postorder: ");
bst.postorder(root);
key = 55; // delete 55
bst.deleteTree(root, key);
System.out.print("\n Inorder, after deletion of " + key + ": "); bst.inorder(root);
key = 44; // insert 44
bst.insertTree(root, key);
System.out.print("\n Inorder, after insertion of " + key + ": "); bst.inorder(root);
}
}

Output:

74 Data Structure and Algorithms Lab Manual

 Node 66 not found
Number of leaf nodes:
6
Inorder: 10 15 20 25 30 45 50 55 60 65 75 80

75 Data Structure and Algorithms Lab Manual

 Preorder: 45 25 15 10 20 30 65 55 50 60 75 80
Postorder: 10 20 15 30 25 50 60 55 80 75 65 45
Inorder, after deletion of 55: 10 15 20 25 30 45 50 60 65 75 80
Inorder, after insertion of 44: 10 15 20 25 30 44 45 50 60 65 75 80
Exercises:

Exersise 1 [5]
Write a program which should implement a binary search tree containing floating point values as its
elements. Program should allow user to insert a value in tree and program should also perform pre
order, post order and in order traversal of this tree. Program should also count the number of nodes
present in the tree.
2.3

2.1 3.4

1.9 5.6

1.5

import java.util.Scanner;

class Node {
double data;
Node left, right;

Node(double data) {
this.data = data;
left = right = null;
}
}

class BinarySearchTree {
Node root;
int nodeCount;

BinarySearchTree() {
root = null;
nodeCount = 0;
}

void insert(double data) {

root = insertRecursive(root, data);
nodeCount++;
}

Node insertRecursive(Node root, double data) {

if (root == null) {
return new Node(data);
76 Data Structure and Algorithms Lab Manual
 }

if (data < root.data) {

root.left = insertRecursive(root.left, data);
} else if (data > root.data) {
root.right = insertRecursive(root.right, data);
}
return root;
}

void preOrder(Node node) {

if (node != null) {
System.out.print(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
}

void inOrder(Node node) {

if (node != null) {
inOrder(node.left);
System.out.print(node.data + " ");
inOrder(node.right);
}
}

void postOrder(Node node) {

if (node != null) {
postOrder(node.left);
postOrder(node.right);
System.out.print(node.data + " ");
}
}

public static void main(String[] args) {

BinarySearchTree bst = new BinarySearchTree();
Scanner scanner = new Scanner(System.in);

System.out.println("Binary Search Tree Operations:");

System.out.println("1. Insert");
System.out.println("2. Pre-order Traversal");
System.out.println("3. In-order Traversal");
System.out.println("4. Post-order Traversal");
System.out.println("5. Count Nodes");
System.out.println("6. Exit");

while (true) {
System.out.print("\nEnter your choice: ");
int choice = scanner.nextInt();

switch (choice) {
case 1:
System.out.print("Enter value to insert: ");
double data = scanner.nextDouble();
bst.insert(data);
break;
case 2:
System.out.print("Pre-order Traversal: ");
bst.preOrder(bst.root);
System.out.println();
break;
case 3:
77 Data Structure and Algorithms Lab Manual
 System.out.print("In-order Traversal: ");
bst.inOrder(bst.root);
System.out.println();
break;
case 4:
System.out.print("Post-order Traversal: ");
bst.postOrder(bst.root);
System.out.println();
break;
case 5:
System.out.println("Number of nodes: " + bst.nodeCount);
break;
case 6:
System.exit(0);
default:
System.out.println("Invalid choice!");
}
}
}
}

78 Data Structure and Algorithms Lab Manual

79 Data Structure and Algorithms Lab Manual
 Exersise 2 [5]
Write a program which should implement a binary serach tree using linked list. Elements of tree are
objects of “student” class. “student” class contains attributes (privately defined) reg_no(int), st_name
(string) and cgpa (float). “student” class should also contain member functions (publicly defined);
constructor, input and output functions. User will insert objects of class “student” in binary tree, values
of attributes of objects will be provided by user. Program should display the objects of student class in
pre order, post order and in order traversal formats. Program should also search an object from tree
which is provided by user as input.

import java.util.Scanner;

class Student {
private int reg_no;
private String st_name;
private float cgpa;

public Student() {}

public Student(int reg, String name, float gpa) {

reg_no = reg;
st_name = name;
cgpa = gpa;
}

public void input() {

Scanner scanner = new Scanner(System.in);
System.out.print("Enter registration number: ");
reg_no = scanner.nextInt();
System.out.print("Enter student name: ");
st_name = scanner.next();
System.out.print("Enter CGPA: ");
cgpa = scanner.nextFloat();
}

public void output() {

System.out.println("Registration Number: " + reg_no);
System.out.println("Student Name: " + st_name);
System.out.println("CGPA: " + cgpa);
}

public int getRegNo() {

return reg_no;
}

public String getName() {

return st_name;
}

public float getCGPA() {

return cgpa;
}
}

class Node {
Student data;
Node left;
Node right;
94 Data Structure and Algorithms Lab Manual
 Node(Student s) {
data = s;
left = right = null;
}
}

class BinarySearchTree {
Node root;

public BinarySearchTree() {
root = null;
}

public void insert(Student s) {

root = insertRecursive(root, s);
}

private Node insertRecursive(Node root, Student s) {

if (root == null) {
return new Node(s);
} else if (s.getRegNo() < root.data.getRegNo()) {
root.left = insertRecursive(root.left, s);
} else if (s.getRegNo() > root.data.getRegNo()) {
root.right = insertRecursive(root.right, s);
}
return root;
}

public void preOrderTraversal() {

preOrderTraversal(root);
}

private void preOrderTraversal(Node root) {

if (root!= null) {
root.data.output();
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}
}

public void inOrderTraversal() {

inOrderTraversal(root);
}

private void inOrderTraversal(Node root) {

if (root!= null) {
inOrderTraversal(root.left);
root.data.output();
inOrderTraversal(root.right);
}
}

public void postOrderTraversal() {

postOrderTraversal(root);
}

private void postOrderTraversal(Node root) {

if (root!= null) {
postOrderTraversal(root.left);
postOrderTraversal(root.right);
root.data.output();
94 Data Structure and Algorithms Lab Manual
 }
}

public void search(int regNo) {

Node found = searchRecursive(root, regNo);
if (found!= null) {
found.data.output();
} else {
System.out.println("Student not found!");
}
}

private Node searchRecursive(Node root, int regNo) {

if (root == null || root.data.getRegNo() == regNo) {
return root;
} else if (regNo < root.data.getRegNo()) {
return searchRecursive(root.left, regNo);
} else {
return searchRecursive(root.right, regNo);
}
}
}

public class Main2 {

public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
Student s = new Student();

Scanner scanner = new Scanner(System.in);

System.out.println("Binary Search Tree Operations:");

System.out.println("1. Insert Student");
System.out.println("2. Pre-order Traversal");
System.out.println("3. In-order Traversal");
System.out.println("4. Post-order Traversal");
System.out.println("5. Search Student");
System.out.println("6. Exit");

while (true) {
System.out.print("\nEnter your choice: ");
int choice = scanner.nextInt();

switch (choice) {
case 1:
s.input();
bst.insert(s);
break;
case 2:
System.out.println("Pre-order Traversal:");
bst.preOrderTraversal();
break;
case 3:
System.out.println("In-order Traversal:");
bst.inOrderTraversal();
break;
case 4:
System.out.println("Post-order Traversal:");
bst.postOrderTraversal();
break;
case 5:
System.out.print("Enter registration number to search: ");
int regNo = scanner.nextInt();
94 Data Structure and Algorithms Lab Manual
 bst.search(regNo);
break;
case 6:
System.exit(0);
default:
System.out.println("Invalid choice!");
}
}
}
}

94 Data Structure and Algorithms Lab Manual

Practical Application of Binary Search Trees
Obscure binary search trees
Items, such as names, numbers, etc. can be stored in memory in a sorted order called binary search
trees or BSTs. And some of these data structures can automatically balance their height when arbitrary
items are inserted or deleted. Therefore, they are known as self-balancing BSTs. Further, there can be
different implementations of this type, like the BTrees, AVL trees, and red-black trees. But there are
many other lesser-known executions that you can learn about. Some examples include AA trees, 2-3
trees, splay trees, scapegoat trees, and treaps.

You can base your project on these alternatives and explore how they can outperform other widely-
used BSTs in different scenarios. For instance, splay trees can prove faster than red-black trees under
the conditions of serious temporal locality.

BSTs following the memoization algorithm

Memoization related to dynamic programming. In reduction-memoizing BSTs, each node can memoize
a function of its subtrees. Consider the example of a BST of persons ordered by their ages. Now, let the
child nodes store the maximum income of each individual. With this structure, you can answer queries
like, “What is the maximum income of people aged between 18.3 and 25.3?” It can also handle
updates in logarithmic time.

Moreover, such data structures are easy to accomplish in C language. You can also attempt to bind it
with Ruby and a convenient API. Go for an interface that allows you to specify ‘lambda’ as your
ordering function and your subtree memoizing function. All in all, you can expect reduction-memoizing
BSTs to be self-balancing BSTs with a dash of additional book-keeping.

Dynamic coding will need cognitive memorisation for its implementation. Each vertex in a reducing BST
can memorise its sub–trees’ functionality. For example, a BST of persons is categorised by their age.

This DSA topics based project idea allows the kid node to store every individual’s maximum salary. This
framework can be used to answer the questions like “what’s the income limit of persons aged 25 to
30?”

95 Data Structure and Algorithms Lab Manual

 LAB TASK 11 – Balanced Trees

Name / Group ID: Reg. No:

Class / Section: Date: _

Time Required : 3 hrs
Programming Language : Java
Software Required : Netbeans
Hardware Required : Computer System

Balanaced Tree
A B-tree of order m is an m-way tree in
which All leaf nodes are on the same level.
All nodes, except the root and the leaves, have between [m/2] and m children.
The nonleaf nodes store up to m-1 keys to guide the searching; and these keys partition the keys
in the children in the fashion of a search tree.
The root is either a leaf or has between two and m children.
If a node has ‘d’ number of children, then it must have d-1 number of keys.

Program B-Tree

class BTree
{
final int MAX =
4; final int MIN =
2;

class BTNode // B-Tree node

{
int count;
int key[] = new int[MAX+1];
BTNode child[] = new BTNode[MAX+1];
}
BTNode root = new BTNode();
class Ref // This class creates an object reference
{ int m; } // and is used to retain/save index values
// of current node between method calls.
/*
* New key is inserted into an appropriate node.
* No node has key equal to new key (duplicate keys are not allowed.
96 Data Structure and Algorithms Lab Manual
 */
void insertTree( int val )
{
Ref i = new Ref();
BTNode c = new BTNode();
BTNode node = new
BTNode(); boolean pushup;
pushup = pushDown( val, root, i, c

); if ( pushup )
{
node.count = 1;
node.key[1] = i.m;
node.child[0] = root;
node.child[1] = c;
root = node;
}
}
/*
* New key is inserted into subtree to which current node points.
* If pushup becomes true, then height of the tree grows.
*/
boolean pushDown( int val, BTNode node, Ref p, BTNode c )
{
Ref k = new Ref();
if ( node == null )
{
p.m = val;
c = null;
return true;
}
else
{
if ( searchNode( val, node, k ) ) System.out.println("Key
already exists.");
if ( pushDown( val, node.child[k.m], p, c ) )
{

if ( node.count < MAX )

{

97 Data Structure and Algorithms Lab Manual

 pushIn( p.m, c, node, k.m
); return false;
}
else
{
split( p.m, c, node, k.m, p, c );
return true;
}
}
return false;
}
}
/*
* Search through a B-Tree for a target key in the node: val
* Outputs target node and its position (pos) in the node
*/
BTNode searchTree( int val, BTNode root, Ref pos )
{
if ( root == null
) return
null ;
else
{
if ( searchNode( val, root, pos )
) return root;
else
return searchTree( val, root.child[pos.m], pos );
}
}
/*
* This method determines if the target key is present in
* the current node, or not. Seraches keys in the current node;
* returns position of the target, or child on which to continue search.
*/
boolean searchNode( int val, BTNode node, Ref pos )
{
if ( val < node.key[1] )
{
pos.m = 0 ; return false
;
}
else
{
pos.m = node.count ;
while ( ( val < node.key[pos.m] ) && pos.m > 1 )
(pos.m)--; if ( val == node.key[pos.m] ) return
true;
else
return false;
}
}
100 Data Structure and Algorithms Lab Manual
 /*
* Inserts the key into a node, if there is room

* for the insertion

*/
void pushIn( int val, BTNode c, BTNode node, int k )
{
int i ;
for ( i = node.count; i > k ; i-- )
{
node.key[i + 1] = node.key[i]; node.child[i +
1] = node.child[i];
}
node.key[k + 1] = val ;
node.child[k + 1] = c ; node.count++ ;
}
/*
* Splits a full node into current node and new right child
* with median.
*/
void split( int val, BTNode c, BTNode
node, int k, Ref y, BTNode
newnode )
{
int i, mid; // mid is median
if ( k <= MIN )
mid =
MIN;
else
mid = MIN + 1;
newnode = new
BTNode();
for ( i = mid+1; i <= MAX; i++ )
{
newnode.key[i-mid] = node.key[i];
newnode.child[i-mid] = node.child[i];
}
newnode.count = MAX - mid;
node.count = mid;
if ( k <= MIN )
pushIn ( val, c, node, k );
else
pushIn ( val, c, newnode, k-mid ) ;

101 Data Structure and Algorithms Lab Manual

 y.m = node.key[node.count];
newnode.child[0] = node.child[node.count]
; node.count-- ;
}

102 Data Structure and Algorithms Lab Manual

 // calls display( ) void
displayTree()
{
display( root );
}
// displays the B-Tree
void display( BTNode root )
{

int i;

if ( root != null )
{
for ( i = 0; i < root.count; i++ )
{
display( root.child[i] );
System.out.print( root.key[i+1] + " "
);
}
display( root.child[i] );
}
}
} // end of BTree class
////////////////////////// BTreeDemo.java /////////////////////////////
class BTreeDemo
{
public static void main( String[] args )
{
BTree bt = new BTree();
/*
* Refer Textbook, the section 13.3 B-Trees,
* inserting into a B-Tree
* Figure 13.30: Building a B-tree of order 5
*/
int[] arr = { 11, 23, 21, 12, 31, 18, 25, 35, 29, 20, 45, 27, 42, 55, 15, 33,
36, 47, 50, 39 };
for ( int i = 0; i < arr.length; i++
) bt.insertTree( arr[i] );
System.out.println("B-Tree of order 5:");
bt.displayTree();
}
}

103 Data Structure and Algorithms Lab Manual

 Output:
B-Tree of order 5:
11 12 15 18 20 21 23 25 27 29 31 33 35 36 39 42 45 47 50 55

Exersise [1o]
Write a deletion method
Node deleteNode(Node root, int key) {
if (root == null)
return root;

if (key < root.key)

root.left = deleteNode(root.left, key);
else if (key > root.key)
root.right = deleteNode(root.right, key);
else {
if ((root.left == null) || (root.right == null)) {
Node temp = null;
if (temp == root.left)
temp = root.right;
else
temp = root.left;

if (temp == null) {
temp = root;
root = null;
} else
root = temp;
} else {
Node temp = minValueNode(root.right);
root.key = temp.key;
root.right = deleteNode(root.right, temp.key);
}
}

if (root == null)
return root;

root.height = max(height(root.left), height(root.right)) + 1;

int balance = getBalance(root);

if (balance > 1 && getBalance(root.left) >= 0)

return rightRotate(root);

if (balance > 1 && getBalance(root.left) < 0) {

root.left = leftRotate(root.left);
return rightRotate(root);
}

if (balance < -1 && getBalance(root.right) <= 0)

return leftRotate(root);

if (balance < -1 && getBalance(root.right) > 0) {

root.right = rightRotate(root.right);
return leftRotate(root);

104 Data Structure and Algorithms Lab Manual

 }

return root;
}

105 Data Structure and Algorithms Lab Manual

Important Concepts
1. STACK: The operations like push, pop, top of the stack, is empty, is full are performed on the stack.
2. QUEUE: The operations like insertion, deletion, rear of the queue, front of the queue, is empty, is full are
performed on the queue.
3. CIRCULAR QUEUE: The operations like insertion, deletion, rear of the queue, front of the queue, is empty,
is full are performed on the circular queue.
4. SINGLY LINKED LIST: The operations like insertion, deletion and search operations are performed on the
singly linked list.
5. DOUBLY LINKED LIST: The operations like insertion, deletion and search operations are performed on the
doubly linked list.
6. BUBBLE SORT: Various numbers are sorted in ascending order according to the bubble sort technique.
7. INSERTION SORT: Various numbers are sorted in ascending order according to the insertion sort technique.
8. SELECTION SORT: Various numbers are sorted in ascending order according to the selection sort technique.
9. LINEAR SEARCH: A list of elements are created and the required value is searched in the list based on the
linear search strategy.
10. BINARY SEARCH: A list of elements are created and the required value is searched in the list based on the
binary search strategy.
11. BINARY SEARCH TREE: Operations insertion, deletion are performed on the binary search tree. Also the
search operation is performed on the tree.
12. TREE TRAVERSAL: A tree is created and the operations infix, prefix, postfix are performed on the tree.
13. GRAPH TRAVERSAL: A graph is created and the operations BFS,DFS are performed on the graph.
14. DIJKSTRA’S ALGORITHM: A graph is created and the shortest path from start node to each node in the
graph is determined.
15. PRIM’S ALGORITHM: A graph is created and the minimum spanning tree is determined according to the
prim’s algorithm.
16. KRUSKAL’S ALGORITHM: A graph is created and the minimum spanning tree is determined according to
the kruskal’s algorithm.
17. AVL TREE: Operations insertion, deletion are performed on the AVL tree. Also the search operation is
performed on the tree.
18. NQUEENS PROBLEM: A board of n*n dimension is created and the solution to the nqueens board is
displayed. Also the solution is animated at each step.
19. DFA: The required graph is created, and we check whether the given input string is accepted or rejected by the
DFA.
20. NFA: The required graph is created, and we check whether the given input string is accepted or rejected by the
NFA.
21. BINARY ADDITION: Two decimal numbers are accepted as input and are automatically converted into
binary numbers and are added. At each step, the results are displayed.
22. PROCESS SCHEDULING: Various processes and their execution times are taken as input, and they are
scheduled according to the selected strategy(FCFS,SJF,ROUND-ROBIN).
23. TRAVELLING SALES PERSON PROBLEM: The number of cities to be traversed are taken as input and
the path through which the traveler need to traverse is determined both at a time and step by step.
24. LINEAR HASHING: The hash table is created for required number of elements and insertion, deletion and
search operations are performed on it.

132 Data Structure and Algorithms Lab Manual

“I insist you to strive. Work, Work
and only work for satisfaction with
patience, humbleness and serve
thy nation”.
Muhammad Ali Jinnah

“A scientist in his laboratory is not

a mere technician: he is also a
child confronting natural
phenomena that impress him as
though they were fairy tales”.
Marie Curie

“I have not failed. I've just found

10,000 ways that won't work”.
Thomas Alva Edison

133 Data Structure and Algorithms Lab Manual