Data Structures

Lab Manual

NAME: _____________________________________

ID: ________________________________________

SECTION: __________________________________

DEGREE: ___________________________________

IQRA UNIVERSITY,
 Data Structure
(LIST OF LABS)
Lab #1______________________________________________________________
Revision of Object Oriented Programming in Java (Part 1)
 Class and Object
 Constructor and Methods
 Passing Argument by reference.

Lab # 2______________________________________________________________
Revision of Object Oriented Programming in Java (Part 2)
 Arrays in Java
o Searching values in java
o Sorting Array
o Matrix Multiplication Using 2D Arrays
 Generic Class in Java
Lab # 3______________________________________________________________
Use and evaluate Built-in Data structure in Java (Part 1).
 ArrayList
 Vector
 BitSet

Lab # 4____________________________________________________________

Use and evaluate Built-in Data structure in Java (Part 2).

 Stack
 HashTable
 Properties

Lab # 5____________________________________________________________

Understand Recursion technique in java.

Lab # 6____________________________________________________________

Implement different sorting technique in java

Lab # 7_____________________________________________________________
Develop Array List Using Generic Array in Java Programming Language
Lab # 8______________________________________________________________

Develop Stack and Queue Using Generic Array in Java Programming Language

Lab # 9_____________________________________________________________
Develop Basic (Singly) LinkedList in Java.

Lab # 10_____________________________________________________________
Develop Circular and Doubly LinkedList in Java.

Lab # 11_____________________________________________________________
Implement Hash Table in java.

Lab # 12_____________________________________________________________
Using HashTable and LinkedList Class, Develop HashMap in Java

Lab # 13_____________________________________________________________
Implement Binary Search Tree in Java using Node class having
left and right pointer in it.

Lab # 14____________________________________________________________

Implement In order Tree Traversal in Java for BST

Lab # 15____________________________________________________________
Implement Post order Tree Traversal in Java for BST
 Data Structures
LAB-1

Name ____________________
Roll No ___________________
Date ______________________
Marks Obtained ____________
Signature___________________
 Revision of Object Oriented
Programming in Java (Part 1)
Objective:
 Class and Object
 Constructor and Methods
 Passing Argument by reference.

Object: Objects have states and behaviors. Example: A dog has states - color,
name, breed as well as behaviors – wagging the tail, barking, eating. An object is an
instance of a class.

Class: A class can be defined as a template/blueprint that describes the

behavior/state that the object of its type support.

Example
publicclassUniversity{
publicUniversity(String name){
System.out.println("University Name:"+ name );
}

publicstaticvoid main(String[]args){
University IU=newUniversity("Iqra University");
}
}

If we compile and run the above program, then it will produce the
following result −

Output
University Name: Iqra University
Constructors:When discussing about classes, one of the most
important sub topic would be constructors. Every class has a
constructor. If we do not explicitly write a constructor for a class,
the Java compiler builds a default constructor for that class.

Creating an Object:As mentioned previously, a class provides the

blueprints for objects. So basically, an object is created from a class.
In Java, the new keyword is used to create new objects.

Pass by value - In this case actual parameter is evaluated and its value is
copied into memory (stack) used by the parameters of the method.

Pass by reference - In this case the memory address of the actual parameter is
copied in the parameter of the method. Thus anytime method is using its
parameter it is actually using the actual parameter.

Lab Tasks:

Develop Java Class IU_Mark_Sheet with following Constructor and Methods.

Constructor:
 IU_Mark_Sheet(String Student, String Registration Number);

Methods:
 Void Subject_Name(String Subject[]);
 Void Subject_Max_Mark(double MaxMark[]);
 Void Subject_Scored_Mark(double ScoredMark[]);
 Double StudentGPA();

Take Home Assignment:

Program Statement:

You are required to model a vehicle parking lot system. The parking lot has a facility to park cars and
scooters. The parking lot contains four parking lanes-two for cars and two for scooters.

Each lane can hold ten vehicles. There is an operator with a console at the East end of the parking
lot. The system should be able to handle following scenarios.

Arrival of a vehicle:
1. Type of vehicle (car or scooter) and Registration No. of vehicle should be entered

2. Program should display suitable parking slot

3. Vehicles arrive at East end, leave from West end

Departure of Car:

1. If not western most, all cars should be moved to the west

2. When the car is driven out, rest of the cars should be moved to the left

3. Vehicle data should be updated

Departure of Scooter:

1. Scooters should be able to drive out at random

2. Vehicle data should be updated

Note that when desired the operator must be able to obtain information like number of vehicles,
number of scooters or number of cars currently parked in the parking lot. Also, the system should be
able to display all the parking lots (currently occupied) if desired.
 Data Structures

LAB-2

Name ____________________
Roll No ___________________
Date ______________________
Marks Obtained ____________
Signature___________________
Revision of Object Oriented
Programming in Java (Part 2)
Objective:
 Arrays in Java
o Searching values in java
o Sorting Array
o Vector Multiplication Using two integer Arrays
 Generic Class in Java

Array in Java: Java provides a data structure, the array, which stores a
fixed-size sequential collection of elements of the same type. An array is
used to store a collection of data, but it is often more useful to think of an
array as a collection of variables of the same type.
Example
The following code snippets are examples of this syntax −

double[] IUList;// preferred way.

or
double IUList[];// works but not preferred way.

Following statement declares an array variable, myList, creates an array

of 10 elements of double type and assigns its reference to myList −

double[] IUList = new double[10];

Here is a complete example showing how to create, initialize, and

process arrays −

public class TestArray {

public static void main(String[] args) {

double[] IUList = {1.9, 2.9, 3.4, 3.5};
 // Print all the array elements
for (int i = 0; i < IUList.length; i++) {
System.out.println(IUList[i] + " ");
}

// Summing all elements

double total = 0;
for (int i = 0; i < IUList.length; i++) {
total += IUList[i];
}
System.out.println("Total is " + total);

// Finding the largest element

double max = IUList[0];
for (int i = 1; i < IUList.length; i++) {
if (IUList[i] > max) max = IUList[i];
}
System.out.println("Max is " + max);
}
}

Passing Arrays to Methods

Just as you can pass primitive type values to methods, you can also pass
arrays to methods. For example, the following method displays the
elements in an int array −

Example
publicstaticvoid printArray(int[] array){
for(int i =0; i < array.length; i++){
System.out.print(array[i]+" ");
}
}
Lab Tasks 1:
 Develop Method in java which can find the smallest and the largest value from integer Array.
o int[] TwoExtreamValue(int A[]).
 Develop Method in java which can sort integer array using bubble sort.
o Int[] SortArray(int A[]).

 Vector Multiplication Using two integer Arrays

o int VectorMultiplication(int A[],int B[]).

Generic Classes
A generic class declaration looks like a non-generic class declaration,
except that the class name is followed by a type parameter section.

As with generic methods, the type parameter section of a generic class

can have one or more type parameters separated by commas. These
classes are known as parameterized classes or parameterized types
because they accept one or more parameters.

Example
Following example illustrates how we can define a generic class −

publicclassBox<T>{
private T t;

publicvoid add(T t){

this.t = t;
}

public T get(){
return t;
}

publicstaticvoid main(String[] args){

Box<Integer> integerBox =newBox<Integer>();
Box<String> stringBox =newBox<String>();
integerBox.add(newInteger(10));
stringBox.add(newString("Hello World"));

System.out.printf("Integer Value :%d\n\n", integerBox.get());

System.out.printf("String Value :%s\n", stringBox.get());
}
}

This will produce the following result −

Output
Integer Value :10
String Value :Hello World

Lab Tasks 2:
Develop Generic Class which can set Data type of Single dimension array.
 Data Structures

LAB-3

Name ____________________
Roll No ___________________
Date ______________________
Marks Obtained ____________
Signature___________________
Use and evaluate Built-in Data
structure in Java. (Part 1)
Objective:
 ArrayList
 Vector
 BitSet

ArrayList
The ArrayList class extends AbstractList and implements the List
interface. ArrayList supports dynamic arrays that can grow as needed.

Standard Java arrays are of a fixed length. After arrays are created, they
cannot grow or shrink, which means that you must know in advance how
many elements an array will hold.

Array lists are created with an initial size. When this size is exceeded, the
collection is automatically enlarged. When objects are removed, the array
may be shrunk.

The Vector
The Vector class is similar to a traditional Java array, except that it can
grow as necessary to accommodate new elements.
Like an array, elements of a Vector object can be accessed via an index
into the vector.

The BitSet
The BitSet class implements a group of bits or flags that can be set and
cleared individually.

This class is very useful in cases where you need to keep up with a set of
Boolean values; you just assign a bit to each value and set or clear it as
appropriate.

Task 1:
Use and Evaluate following Constructor and
Methods of Vector

Constructor:
Vector( ): This constructor builds an empty array list.
Vector(int capacity): This constructor builds an array list that has the
specified initial capacity.

Methods:
void add(int index, Object element): Inserts the specified element at
the specified position index in this list.

boolean add(Object o) :Appends the specified element to the end of

this list.

void clear() :Removes all of the elements from this list.

boolean contains(Object o) :Returns true if this list contains the

specified element.
Object get(int index) :Returns the element at the specified position in
this list.

int indexOf(Object o) :Returns the index in this list of the first

occurrence of the specified element, or -1 if the List does not contain this
element.

Object remove(int index) :Removes the element at the specified

position in this list.

int size(): Returns the number of elements in this list.

Object[] toArray(Object[] a) :Returns an array containing all of the

elements in this list in the correct order; the runtime type of the returned
array is that of the specified array.

void trimToSize() :Trims the capacity of this ArrayList instance to be

the list's current size.

Task 2:
Use and Evaluate following Constructor and
Methods of ArrayList

Constructor:
ArrayList( ): This constructor builds an empty array list.
ArrayList(int capacity): This constructor builds an array list that has
the specified initial capacity.

Methods:
void add(int index, Object element): Inserts the specified element at
the specified position index in this list.
boolean add(Object o) :Appends the specified element to the end of
this list.

void clear() :Removes all of the elements from this list.

boolean contains(Object o) :Returns true if this list contains the

specified element.

Object get(int index) :Returns the element at the specified position in

this list.

int indexOf(Object o) :Returns the index in this list of the first

occurrence of the specified element, or -1 if the List does not contain this
element.

Object remove(int index) :Removes the element at the specified

position in this list.

int size() :Returns the number of elements in this list.

Object[] toArray(Object[] a) :Returns an array containing all of the

elements in this list in the correct order; the runtime type of the returned
array is that of the specified array.

void trimToSize() :Trims the capacity of this ArrayList instance to be

the list's current size.

Task 3:
Use and Evaluate following Constructor and
Methods of BitSet

Constructor:
BitSet( ): This constructor creates a default object.
BitSet(int size): This constructor allows you to specify its initial size, i.e., the
number of bits that it can hold. All bits are initialized to zero.

Methods:
void and(BitSet bitSet): ANDs the contents of the invoking BitSet object with
those specified by bitSet. The result is placed into the invoking object.

void andNot(BitSet bitSet): For each 1 bit in bitSet, the corresponding bit in the
invoking BitSet is cleared.

int cardinality( ) :Returns the number of set bits in the invoking object.

void clear( ) :Zeros all bits.

void clear(int index) :Zeros the bit specified by index.

void clear(int startIndex, int endIndex) :Zeros the bits from startIndex to
endIndex.

void flip(int index) :Reverses the bit specified by the index.

boolean equals(Object bitSet) :Returns true if the invoking bit set is equivalent
to the one passed in bitSet. Otherwise, the method returns false.

void flip(int startIndex, int endIndex) :Reverses the bits from startIndex to
endIndex.

boolean get(int index) :Returns the current state of the bit at the specified index.

boolean intersects(BitSet bitSet) :Returns true if at least one pair of

corresponding bits within the invoking object and bitSet are 1.

boolean isEmpty( ) :Returns true if all bits in the invoking object are zero.

int length( ) :Returns the number of bits required to hold the contents of the
invoking BitSet. This value is determined by the location of the last 1 bit.

void or(BitSet bitSet): ORs the contents of the invoking BitSet object with that
specified by bitSet. The result is placed into the invoking object.

void set(int index): Sets the bit specified by index.

int size( ): Returns the number of bits in the invoking BitSet object.
void xor(BitSet bitSet): XORs the contents of the invoking BitSet object with that
specified by bitSet. The result is placed into the invoking object.

Data Structures

LAB-4

Name ____________________
Roll No ___________________
Date ______________________
Marks Obtained ____________
Signature___________________
Use and evaluate Built-in Data
structure in Java. (Part 2)
Objective:
 Stack
 HashTable
 Properties

The Stack
The Stack class implements a last-in-first-out (LIFO) stack of elements.

You can think of a stack literally as a vertical stack of objects; when you
add a new element, it gets stacked on top of the others.

When you pull an element off the stack, it comes off the top. In other
words, the last element you added to the stack is the first one to come
back off.

The Hashtable
The Hashtable class provides a means of organizing data based on some
user-defined key structure.

For example, in an address list hash table you could store and sort data
based on a key such as ZIP code rather than on a person's name.

The specific meaning of keys with regard to hash tables is totally

dependent on the usage of the hash table and the data it contains.
The Properties
Properties is a subclass of Hashtable. It is used to maintain lists of values
in which the key is a String and the value is also a String.

The Properties class is used by many other Java classes. For example, it
is the type of object returned by System.getProperties( ) when obtaining
environmental values.

Task 1:
Use and Evaluate following Constructor and
Methods of Stack

Constructor:
Stack(): This constructor creates a default object.

Methods:
boolean empty() :Tests if this stack is empty. Returns true if the stack is empty,
and returns false if the stack contains elements.

Object peek() :Returns the element on the top of the stack, but does not remove
it.

Object pop() :Returns the element on the top of the stack, removing it in the
process.

Object push(Object element) :Pushes the element onto the stack. Element is
also returned.

int search(Object element) :Searches for element in the stack. If found, its offset
from the top of the stack is returned. Otherwise, .1 is returned

Task 2:
Use and Evaluate following Constructor and
Methods of HashTable
Hashtable( ) :This is the default constructor of the hash table it instantiates the
Hashtable class.

Hashtable(int size) :This constructor accepts an integer parameter and creates a

hash table that has an initial size specified by integer value size.

Hashtable(int size, float fillRatio) :This creates a hash table that has an initial
size specified by size and a fill ratio specified by fillRatio. This ratio must be
between 0.0 and 1.0, and it determines how full the hash table can be before it is
resized upward.

Methods:
void clear() :Resets and empties the hash table.

Object clone() :Returns a duplicate of the invoking object.

boolean contains(Object value) :Returns true if some value equal to the value
exists within the hash table. Returns false if the value isn't found.

boolean containsKey(Object key) :Returns true if some key equal to the key
exists within the hash table. Returns false if the key isn't found.

boolean containsValue(Object value) :Returns true if some value equal to the

value exists within the hash table. Returns false if the value isn't found.

Enumeration elements() :Returns an enumeration of the values contained in the

hash table.

Object get(Object key) :Returns the object that contains the value associated
with the key. If the key is not in the hash table, a null object is returned.

boolean isEmpty() :Returns true if the hash table is empty; returns false if it
contains at least one key.

Enumeration keys() :Returns an enumeration of the keys contained in the hash

table.
Object put(Object key, Object value) :Inserts a key and a value into the hash
table. Returns null if the key isn't already in the hash table; returns the previous
value associated with the key if the key is already in the hash table.

void rehash() :Increases the size of the hash table and rehashes all of its keys.

Object remove(Object key) :Removes the key and its value. Returns the value
associated with the key. If the key is not in the hash table, a null object is returned.

int size() :Returns the number of entries in the hash table.

Task 3:
Use and Evaluate following Constructor and
Methods of Properties

Constructor:
Properties() :This constructor creates a Properties object that has no default
values.

Properties(Properties propDefault) :Creates an object that uses propDefault for

its default values. In both cases, the property list is empty

Methods:
String getProperty(String key) :Returns the value associated with the key. A
null object is returned if the key is neither in the list nor in the default property list.

String getProperty(String key, String defaultProperty) :Returns the value

associated with the key; defaultProperty is returned if the key is neither in the list
nor in the default property list.

void list(PrintStream streamOut) :Sends the property list to the output stream
linked to streamOut.

void list(PrintWriter streamOut) :Sends the property list to the output stream
linked to streamOut.

void load(InputStream streamIn) throws IOException :Inputs a property list

from the input stream linked to streamIn.
Enumeration propertyNames( ) :Returns an enumeration of the keys. This
includes those keys found in the default property list, too.

Object setProperty(String key, String value) :Associates value with the key.
Returns the previous value associated with the key, or returns null if no such
association exists.

void store(OutputStream streamOut, String description) :After writing the

string specified by description, the property list is written to the output stream
linked to streamOut.

Data Structures

LAB-5

Name ____________________
Roll No ___________________
Date ______________________
 Marks Obtained ____________
Signature___________________

Recursion
Objective: To Understand Recursion in Java

Description:
In order to solve a problem using recursion in Java or any other programming
language e.g. C or C++, You must be able to figure out:

1.Base case, last point which can be resolve without calling recursive function e.g. in
case of Fibonacci series its 1 and 2 where result will be 1. In the case of a recursive
power function, it's zero power which is equal to 1 or in the case of calculating
Factorial its factorial of zero which is equal to 1.

2. With every recursive method call, Your problem must reduce and approach to the
base case. If this is not the case then you won't be able to calculate the result and
eventually die with java.lang.StackOverFlowError

Recursion Programming Example in Java

In our programming example of recursion in Java, we will calculate Fibonacci number

of giving length using recursion. In the case of Fibonacci number current number is
the sum of previous two number except first and second number which will form the
base case for the recursive solution.

public class RecursionTest {

public static void main(String args[]) {

System.out.println("fibonacci series for length 1 is " + fibonacci(6));
}

public static int fibonacci(int number){

if(number < 1){
throw new IllegalArgumentException("Invalid argument for Fibonacci
series: "
+ number);
}
//base case of recursion
 if(number == 1 || number == 2){
return 1;
}
//recursive method call in java
return fibonacci(number-2) + fibonacci(number -1);
}

Task:
Using Recursion Perform the following Tasks

 Calculate factorial of a given number in Java

 Calculate power of a given number in java
 Reverse a String using recursion in Java

Data Structures

LAB-6

Name ____________________
 Roll No ___________________
Date ______________________
Marks Obtained ____________
Signature___________________

Sorting
Objective:
Implement bubble sort, selection sort, insertion sort in java, quick sort, merge
sort in java.

Bubble Sort:

Bubble sort, also referred to as sinking sort, is a simple sorting algorithm that
works by repeatedly stepping through the list to be sorted, comparing each
pair of adjacent items and swapping them if they are in the wrong order. The
pass through the list is repeated until no swaps are needed, which indicates
that the list is sorted. The algorithm gets its name from the way smaller
elements "bubble" to the top of the list. Because it only uses comparisons to
operate on elements, it is a comparison sort. Although the algorithm is simple,
most of the other sorting algorithms are more efficient for large lists.
Bubble sort has worst-case and average complexity both О(n2), where n is the
number of items being sorted.

publicclassMyBubbleSort {

// logic to sort the elements

publicstaticvoidbubble_srt(intarray[]) {
 intn = array.length;
intk;
for(intm = n; m >= 0; m--) {
for(inti = 0; i < n - 1; i++) {
k = i + 1;
if(array[i] > array[k]) {
swapNumbers(i, k, array);
}
}
printNumbers(array);
}
}

privatestaticvoidswapNumbers(inti, intj, int[] array) {

inttemp;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}

privatestaticvoidprintNumbers(int[] input) {

for(inti = 0; i < input.length; i++) {

System.out.print(input[i] + ", ");
}
System.out.println("\n");
}

publicstaticvoidmain(String[] args) {
int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1};
bubble_srt(input);

}
}

Output :

Selection sort:

The selection sort is a combination of searching and sorting. During each pass, the
unsorted element with the smallest (or largest) value is moved to its proper position
in the array. The number of times the sort passes through the array is one less than
the number of items in the array. In the selection sort, the inner loop finds the next
smallest (or largest) value and the outer loop places that value into its proper
location. Selection sort is not difficult to analyze compared to other sorting
algorithms since none of the loops depend on the data in the array.

publicclassMySelectionSort {

publicstaticint[] doSelectionSort(int[] arr){

for(inti = 0; i < arr.length - 1; i++)

{
intindex = i;
for(intj = i + 1; j < arr.length; j++)
if(arr[j] < arr[index])
index = j;

intsmallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
returnarr;
}

publicstaticvoidmain(String a[]){

int[] arr1 = {10,34,2,56,7,67,88,42};

int[] arr2 = doSelectionSort(arr1);
for(inti:arr2){
System.out.print(i);
System.out.print(", ");
}
}
}

Insertion sort:

Insertion sort is a simple sorting algorithm, it builds the final sorted array one item at
a time. It is much less efficient on large lists than other sort algorithms.

Advantages of Insertion Sort:

1. It is very simple.
2. It is very efficient for small data sets.
3. It is stable; i.e., it does not change the relative order of elements with equal keys.
4. In-place; i.e., only requires a constant amount O(1) of additional memory space.

Insertion sort iterates through the list by consuming one input element at each
repetition, and growing a sorted output list
publicclassMyInsertionSort {

publicstaticvoidmain(String a[]){
int[] arr1 = {10,34,2,56,7,67,88,42};
int[] arr2 = doInsertionSort(arr1);
for(inti:arr2){
System.out.print(i);
System.out.print(", ");
}
}

publicstaticint[] doInsertionSort(int[] input){

inttemp;
for(inti = 1; i < input.length; i++) {
for(intj = i ; j > 0; j--){
if(input[j] < input[j-1]){
temp = input[j];
input[j] = input[j-1];
input[j-1] = temp;
}
}
}
returninput;
}
}

Quick sort:

Quicksort or partition-exchange sort, is a fast sorting algorithm, which is using divide

and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists:
the low elements and the high elements. Quicksort can then recursively sort the sub-
lists.

Steps to implement Quick sort:

1. Choose an element, called pivot, from the list. Generally pivot can be the middle
index element.
2. Reorder the list so that all elements with values less than the pivot come before
the pivot, while all elements with values greater than the pivot come after it (equal
values can go either way). After this partitioning, the pivot is in its final position. This
is called the partition operation.
3. Recursively apply the above steps to the sub-list of elements with smaller values
and separately the sub-list of elements with greater values.

publicclassMyQuickSort {

privateintarray[];
privateintlength;

publicvoidsort(int[] inputArr) {

if(inputArr == null|| inputArr.length == 0) {

 return;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
}

privatevoidquickSort(intlowerIndex, inthigherIndex) {

inti = lowerIndex;
intj = higherIndex;
// calculate pivot number, I am taking pivot as middle index number
intpivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two arrays
while(i <= j) {
while(array[i] < pivot) {
i++;
}
while(array[j] > pivot) {
j--;
}
if(i <= j) {
exchangeNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if(lowerIndex < j)
quickSort(lowerIndex, j);
if(i < higherIndex)
quickSort(i, higherIndex);
}

privatevoidexchangeNumbers(inti, intj) {
inttemp = array[i];
array[i] = array[j];
array[j] = temp;
}

publicstaticvoidmain(String a[]){

MyQuickSort sorter = newMyQuickSort();

int[] input = {24,2,45,20,56,75,2,56,99,53,12};
sorter.sort(input);
for(inti:input){
System.out.print(i);
System.out.print(" ");
}
}
}

Merge sort :

Merge sort is a divide and conquer algorithm.

Steps to implement Merge Sort:

1. Divide the unsorted array into n partitions, each partition contains 1 element.
Here the one element is considered as sorted.
2. Repeatedly merge partitioned units to produce new sub-lists until there is only 1
sub-list remaining. This will be the sorted list at the end.

Merge sort is a fast, stable sorting routine with guaranteed O(n*log(n)) efficiency.
When sorting arrays, merge sort requires additional scratch space proportional to
the size of the input array. Merge sort is relatively simple to code and offers
performance typically only slightly below that of quicksort.

publicclassMyMergeSort {
privateint[] array;
privateint[] tempMergArr;
privateintlength;

publicstaticvoidmain(String a[]){

int[] inputArr = {45,23,11,89,77,98,4,28,65,43};

MyMergeSort mms = newMyMergeSort();
mms.sort(inputArr);
for(inti:inputArr){
System.out.print(i);
System.out.print(" ");
}
}
publicvoidsort(intinputArr[]) {
this.array = inputArr;
this.length = inputArr.length;
this.tempMergArr = newint[length];
doMergeSort(0, length - 1);
}
privatevoiddoMergeSort(intlowerIndex, inthigherIndex) {

if(lowerIndex < higherIndex) {

intmiddle = lowerIndex + (higherIndex - lowerIndex) / 2;
// Below step sorts the left side of the array
doMergeSort(lowerIndex, middle);
// Below step sorts the right side of the array
doMergeSort(middle + 1, higherIndex);
// Now merge both sides
mergeParts(lowerIndex, middle, higherIndex);
}
}
privatevoidmergeParts(intlowerIndex, intmiddle, inthigherIndex) {

for(inti = lowerIndex; i <= higherIndex; i++) {

tempMergArr[i] = array[i];
}
inti = lowerIndex;
intj = middle + 1;
intk = lowerIndex;
while(i <= middle && j <= higherIndex) {
if(tempMergArr[i] <= tempMergArr[j]) {
 array[k] = tempMergArr[i];
i++;
} else{
array[k] = tempMergArr[j];
j++;
}
k++;
}
while(i <= middle) {
array[k] = tempMergArr[i];
k++;
i++;
}

}
}
 Data Structures

LAB-7

Name ____________________
Roll No ___________________
Date ______________________
Marks Obtained ____________
Signature___________________
ArrayList
Objective: Develop your own ArrayList in Java having following
methods
 add ()
 remove()
 get()
 contain()
 is_empty()
 IndexOff()
 ToArray()
 TrimToSize()

Basic Code:
publicclassMyArrayList<T>
{
private T[] asArray;

@SuppressWarnings("unchecked")
publicMyArrayList()
{
asArray=(T[])newObject[0];
}

publicvoid add(T t)
{
@SuppressWarnings("unchecked")
T[] temp =(T[])newObject[asArray.length +1];

// copy everything over to the new array

for(int i =0; i < asArray.length; i++)
{
temp[i]= asArray[i];
}

// add the new element

temp[asArray.length]= t;
asArray= temp;
}

publicvoid remove(int index)

{
if(index <0|| index >= asArray.length)return;
@SuppressWarnings("unchecked")
T[] temp =(T[])newObject[asArray.length -1];
boolean found =false;
// copy everything over to the new element
for(int i =0; i < asArray.length; i++)
{
// don't copy if the indices are the same
if(i == index)
{
found=true;
continue;
}
temp[i -(found ?1:0)]= asArray[i];// it's i - 1 after the removed object so
then it doesn't leave a gap and it doesn't go over the array's length
}
asArray= temp;
}

public T get(int index)

{
return asArray[index];
}
}
 Data Structures

LAB-8

Name ____________________
Roll No ___________________
Date ______________________
Marks Obtained ____________
Signature___________________
Stack and Queue

Objective:
Develop Stack and Queue Using Generic Array in Java Programming
Language

Stack Development:

Following example shows how to implement stack by creating user

defined push() method for entering elements and pop() method for
retriving elements from the stack.

publicclassMyStack{
privateint maxSize;
privatelong[] stackArray;
privateint top;
publicMyStack(int s){
maxSize= s;
stackArray=newlong[maxSize];
top=-1;
}
publicvoid push(long j){
stackArray[++top]= j;
}
publiclong pop(){
return stackArray[top--];
}
publiclong peek(){
return stackArray[top];
}
publicboolean isEmpty(){
return(top ==-1);
}
publicboolean isFull(){
return(top == maxSize -1);
}
publicstaticvoid main(String[] args){
MyStack theStack =newMyStack(10);
theStack.push(10);
theStack.push(20);
theStack.push(30);
theStack.push(40);
theStack.push(50);
while(!theStack.isEmpty()){
long value = theStack.pop();
System.out.print(value);
System.out.print(" ");
}
System.out.println("");
}
}

Queue Development:

Following example shows how to implement a queue in an employee

structure.

import java.util.LinkedList;

classGenQueue<E>{
privateLinkedList<E> list =newLinkedList<E>();
publicvoid enqueue(E item){
list.addLast(item);
}
public E dequeue(){
return list.poll();
}
publicboolean hasItems(){
return!list.isEmpty();
}
publicint size(){
return list.size();
}
publicvoid addItems(GenQueue<?extends E> q){
while(q.hasItems())
list.addLast(q.dequeue());
}
}

publicclassGenQueueTest{
publicstaticvoid main(String[] args){
GenQueue<Employee> empList;
empList=newGenQueue<Employee>();
GenQueue<HourlyEmployee> hList;
hList=newGenQueue<HourlyEmployee>();
hList.enqueue(newHourlyEmployee("T","D"));
hList.enqueue(newHourlyEmployee("G","B"));
hList.enqueue(newHourlyEmployee("F","S"));
empList.addItems(hList);
System.out.println("The employees' names are:");
while(empList.hasItems()){
Employee emp =empList.dequeue();
System.out.println(emp.firstName +" "
+ emp.lastName);
}
}
}

classEmployee{
publicString lastName;
publicString firstName;
publicEmployee(){
}
publicEmployee(Stringlast,String first){
this.lastName =last;
this.firstName = first;
}
publicString toString(){
return firstName +" "+ lastName;
}
}

classHourlyEmployeeextendsEmployee{
publicdouble hourlyRate;
publicHourlyEmployee(Stringlast,String first){
super(last, first);
}
}
 Data Structures

LAB-9

Name ____________________
Roll No ___________________
Date ______________________
Marks Obtained ____________
Signature___________________
Linked List
Objective: Develop Basic (Singly) Linked List in Java.

Linked Lists are a very common way of storing arrays of data. The major benefit of
linked lists is that you do not specify a fixed size for your list. The more elements you
add to the chain, the bigger the chain gets.

public class LinkedList

{
// reference to the head node.
private Node head;
private int listCount;

// LinkedList constructor
public LinkedList()
{
// this is an empty list, so the reference to the head node
// is set to a new node with no data
head = new Node(null);
listCount = 0;
}

public void add(Object data)

// post: appends the specified element to the end of this list.
{
Node temp = newNode(data);
Node current = head;
// starting at the head node, crawl to the end of the list
while(current.getNext() != null)
{
current = current.getNext();
}
// the last node's "next" reference set to our new node
current.setNext(temp);
listCount++;// increment the number of elements variable
}

public void add(Object data, int index)

// post: inserts the specified element at the specified position in this list.
{
Node temp = newNode(data);
Node current = head;
// crawl to the requested index or the last element in the list,
// whichever comes first
for(int i = 1; i < index && current.getNext() != null; i++)
{
current = current.getNext();
}
 // set the new node's next-node reference to this node's next-node
reference
temp.setNext(current.getNext());
// now set this node's next-node reference to the new node
current.setNext(temp);
listCount++;// increment the number of elements variable
}

public Object get(int index)

// post: returns the element at the specified position in this list.
{
// index must be 1 or higher
if(index <= 0)
return null;

Node current = head.getNext();

for(int i = 1; i < index; i++)
{
if(current.getNext() == null)
return null;

current = current.getNext();
}
return current.getData();
}

public boolean remove(int index)

// post: removes the element at the specified position in this list.
{
// if the index is out of range, exit
if(index < 1 || index > size())
return false;

Node current = head;

for(int i = 1; i < index; i++)
{
if(current.getNext() == null)
return false;

current = current.getNext();
}
current.setNext(current.getNext().getNext());
listCount--; // decrement the number of elements variable
return true;
}

public int size()

// post: returns the number of elements in this list.
{
return listCount;
}

public String toString()

{
Node current = head.getNext();
String output = "";
while(current != null)
{
output += "[" + current.getData().toString() + "]";
current = current.getNext();
}
return output;
}

private class Node

{
// reference to the next node in the chain,
// or null if there isn't one.
 Node next;
// data carried by this node.
// could be of any type you need.
Object data;

// Node constructor
public Node(Object _data)
{
next = null;
data = _data;
}

// another Node constructor if we want to

// specify the node to point to.
public Node(Object _data, Node _next)
{
next = _next;
data = _data;
}

// these methods should be self-explanatory

public Object getData()
{
return data;
}

public void setData(Object _data)

{
data = _data;
}

public Node getNext()

{
return next;
}

public void setNext(Node _next)

{
next = _next;
}
}
}
 Data Structures

LAB-10

Name ____________________
Roll No ___________________
Date ______________________
Marks Obtained ____________
 Signature___________________

Linked List (Continue)

Objective:
Develop doubly and Circular Linked List in Java

Doubly Linked List:

A doubly linked list is a linked data structure that consists of a set of

sequentially linked records called nodes. Each node contains two fields, called links,
that are references to the previous and to the next node in the sequence of nodes.

Code Example:

publicclassDoublyLinkList<T>{

privatestaticclassNode<T>{
private T data;
privateNode next;
privateNode prev;

publicNode(T data){
this.data = data;
}

publicvoid displayNode(){
System.out.print(data +" ");
}

@Override
publicString toString(){
return data.toString();
}
}

publicNode first =null;

publicNode last =null;

publicvoid addFirst(T data){

Node newNode =newNode(data);

if(isEmpty()){
newNode.next =null;
newNode.prev =null;
first= newNode;
last= newNode;

}else{
first.prev = newNode;
newNode.next = first;
newNode.prev =null;
first= newNode;
}
}

publicboolean isEmpty(){
return(first ==null);
}

publicvoid displayList(){
Node current = first;
while(current !=null){
current.displayNode();
current= current.next;
}
System.out.println();
}

publicvoid removeFirst(){
if(!isEmpty()){
Node temp = first;

if(first.next ==null){
first=null;
last=null;
}else{
first= first.next;
first.prev =null;
}
System.out.println(temp.toString()+" is popped from the list");
}
}

publicvoid removeLast(){
Node temp = last;

if(!isEmpty()){

if(first.next ==null){
first=null;
last=null;
}else{
last= last.prev;
last.next =null;
}
}
System.out.println(temp.toString()+" is popped from the list");
}
}

Circular LinkedList:

In a circularly linked list, all nodes are linked in a continuous circle, without using
null. For lists with a front and a back (such as a queue), one stores a reference to
the last node in the list. The next node after the last node is the first node.

Code Example:

publicclassCircularLinkedList{
privateLink first;
privateLink current;

publicLink getCurrent(){
return current;
}

publicvoid setCurrent(int data){

publicvoid advance(){
current= current.next;
}

publicvoid insert(int data){

Link newLink =newLink(data);
if(first ==null){
first= current = newLink;
}else{
current.next = newLink;
}
current= newLink;
newLink.next = first;
}
...
}
 Data Structures

LAB-11

Name ____________________
Roll No ___________________
Date ______________________
Marks Obtained ____________
Signature___________________
Hash Table
Objective: Implement Basic Hash Table in Java

In the current article we show the very simple hash table example. It uses simple
hash function, collisions are resolved using linear probing (open addressing strategy)
and hash table has constant size. This example clearly shows the basics of hashing
technique.

Hash table

Underlying array has constant size to store 128 elements and each slot contains
key-value pair. Key is stored to distinguish between key-value pairs, which have the
same hash.

Hash function

Table allows only integers as values. Hash function to be used is the remainder of
division by 128. In the view of implementation, this hash function can be encoded
using remainder operator or using bitwise AND with 127.

Note. Power of two sized tables are often used in practice (for instance in Java).
When used, there is a special hash function, which is applied in addition to the main
one. This measure prevents collisions occuring for hash codes that do not differ in
lower bits.
Collision resolution strategy

Linear probing is applied to resolve collisions. In case the slot, indicated by hash
function, has already been occupied, algorithm tries to find an empty one by probing
consequent slots in the array.

Note. Linear probing is not the best techique to be used when table is of a constant
size. When load factor exceeds particular value (appr. 0.7), hash table performance
will decrease nonlinearly. Also, the number of stored key-value pairs is limited to the
size of the table (128).

This implementation suffers one bug. When there is no more place in the table, the
loop, searching for empty slot, will run infinitely. It won't happen in real hash table
based on open addressing, because it is most likely dynamic-sized. Also the
removal's implementation is omitted to maintain simplicity.

Code Example:
public class HashEntry {
private int key;
private int value;

HashEntry(int key, int value) {

this.key = key;
this.value = value;
}

public int getKey() {

return key;
}

public int getValue() {

return value;
}
}

public class HashMap {

private final static int TABLE_SIZE = 128;

HashEntry[] table;

HashMap() {
table = new HashEntry[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
table[i] = null;
}

public int get(int key) {

int hash = (key % TABLE_SIZE);
while (table[hash] != null && table[hash].getKey() != key)
hash = (hash + 1) % TABLE_SIZE;
if (table[hash] == null)
return -1;
else
return table[hash].getValue();
}
 public void put(int key, int value) {
int hash = (key % TABLE_SIZE);
while (table[hash] != null && table[hash].getKey() != key)
hash = (hash + 1) % TABLE_SIZE;
table[hash] = new HashEntry(key, value);
}
}

Data Structures

LAB-12

Name ____________________
Roll No ___________________
Date ______________________
Marks Obtained ____________
 Signature___________________

Hash Map
Objective: Implement Hash Map in Java using linked list and hash table.

Introduction:
HashMap maintains key and value pairs and often denoted as HashMap<Key, Value> or
HashMap<K, V>. HashMap implements Map interface. HashMap is similar to Hashtable
with two exceptions – HashMap methods are unsynchornized and it allows null key and
null values unlike Hashtable. It is used for maintaining key and value mapping.
It is not an ordered collection which means it does not return the keys and values in the
same order in which they have been inserted into the HashMap. It neither does any kind
of sorting to the stored keys and Values. You must need to import java.util.HashMap or
its super class in order to use the HashMap class and methods.

Hash Map Using Java:

Following steps will help you to develop your own hash map using java. Initially it is
not generic, but after completion of all step make it generic as an assignment.

STEP1:
o Create a simple data structure with key, value and which can also extend as
linked list
o line #2,#3: references to key and value
o line #4: link to itself (used when there is collision in the hashmap)
class Entry {

Employee key;
 String value;

Entry next;

Entry(Employee k, String v) {

key = k;

value = v;

public String getValue() {

return value;

public void setValue(String value) {

this.value = value;

public Employee getKey() {

return key;

STEP2:
o Couple of important utility methods
o getSupplementalHash(): Supplemental hash function used to defend against the
poor quality hash given by the user
o getBucketNumber(): It makes sure the bucket number falls within the size of the
hashmap based on the value of hash
private int getSupplementalHash(int h) {

// This function ensures that hashCodes that differ only by

// constant multiples at each bit position have a bounded

// number of collisions (approximately 8 at default load factor).

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}
private int getBucketNumber(int hash) {

return hash & (SIZE - 1);

STEP3:PUT Method
o line #3: get the user defined hashcode
o line #4: defend against the poor quality hash functions defined by the user (if
Employee.hashcode() is poor, this call will do a better job)
o line #8: get the bucket index
o line #12: If the control reaches into for loop, it means that it should either be a
duplicate or a collision
o line #14-15: Its a duplicate, it will be replaced with old one
o line #20: Its a collision, new pair will be appended to the list
o line #28: Its either a new_pair/collision, add it to the map
public void put(Employee key, String value) {

// get the hashcode and regenerate it to be optimum

int userHash = key.hashCode();

int hash = getSupplementalHash(userHash);

// compute the bucket number (0-15 based on our default size)

// this always results in a number between 0-15

int bucket = getBucketNumber(hash);

Entry existingElement = table[bucket];

for (; existingElement != null; existingElement =

existingElement.next) {

if (existingElement.key.equals(key)) {

System.out

.println("duplicate key value

pair, replacing existing key "

+ key + ", with

value " + value);

existingElement.value = value;

return;

} else {
 System.out.println("Collision detected for key "
+ key

+ ", adding element to the

existing bucket");

//

System.out.println("PUT adding key:" + key + ", value:" + value

+ " to the list");

Entry entryInOldBucket = new Entry(key, value);

entryInOldBucket.next = table[bucket];

table[bucket] = entryInOldBucket;

STEP4: GET Method

o line #3: defend against the poor quality hash functions defined by the user (if
Employee.hashcode() is poor, this call will do a better job)
o line #7: get the bucket index
o line #14: This loop is iterated as many times as the number of collisions for every key
o line #23: If nothing is found

public Entry get(Employee key) {

// get the hashcode and regenerate it to be optimum

int hash = getSupplementalHash(key.hashCode());

// compute the bucket number (0-15 based on our default size)

// this always results in a number between 0-15

int bucket = getBucketNumber(hash);

// get the element at the above bucket if it exists

 Entry existingElement = table[bucket];

// if bucket is found then traverse through the linked list and

// see if element is present

while (existingElement != null) {

System.out

.println("Traversing the list inside the

bucket for the key "

+
existingElement.getKey());

if (existingElement.key.equals(key)) {

return existingElement;

existingElement = existingElement.next;

// if nothing is found then return null

return null;

STEP5: Employee object as the key to our custom map (TESTING)

hashCode(): Make sure the hash code falls with 0-10 so that we can reproduce collision
easily.
equals(): based on id and name of the person
static class Employee {

private Integer id;

private String name;

Employee(Integer id, String name) {

this.id = id;

this.name = name;

@Override
 public int hashCode() {

// this ensures all hashcodes are between 0 and 15

return id % 10;

@Override

public boolean equals(Object obj) {

Employee otherEmp = (Employee) obj;

return this.name.equals(otherEmp.name);

@Override

public String toString() {

return this.id + "-" + name;

STEP6: Test Code

o line #13-14: Demonstrate duplicate key replacement in hashmap
o line #30-42 and #31-35: Demonstrate collision in hashmap
o line #44-49: Demonstrate collision along with duplication in hashmap
TMHashMap tmhm = new TMHashMap();

System.out.println("============== Adding Element

===================");

Employee e1 = new Employee(100, "Niranjan");

tmhm.put(e1, "dept1");

// duplicate

System.out.println("============== Adding Duplicate

=================");

Employee e1_dup = new Employee(100, "Niranjan");

 tmhm.put(e1_dup, "dept12");

// the above value "dept12" should replace the old value "dept1"

Entry e = tmhm.get(e1_dup);

System.out.println("GET element - " + e.getKey() + "::" +

e.getValue());

System.out.println("============== Adding Elements

==================");

Employee e2 = new Employee(102, "Sravan");

tmhm.put(e2, "dept3");

Employee e3 = new Employee(104, "Ananth");

tmhm.put(e3, "dept2");

Employee e4 = new Employee(106, "Rakesh");

tmhm.put(e4, "dept5");

Employee e5 = new Employee(108, "Shashi");

tmhm.put(e5, "dept2");

// collision with e2

System.out.println("============== Adding Collisions

=================");

Employee e2_collision = new Employee(112, "Chandu");

tmhm.put(e2_collision, "dept16");

e = tmhm.get(e2_collision);

System.out.println("GET element - " + e.getKey() + "::" +

e.getValue());

// collision with e3

Employee e3_collision = new Employee(114, "Santhosh");

tmhm.put(e3_collision, "dept9");

e = tmhm.get(e3_collision);

System.out.println("GET element - " + e.getKey() + "::" +

e.getValue());
 System.out

.println("============== Adding Duplicate in

Collision ===================");

Employee e3_collision_dupe = new Employee(124, "Santhosh");

tmhm.put(e3_collision_dupe, "dept91");

e = tmhm.get(e3_collision_dupe);

System.out.println("GET element - " + e.getKey() + "::" +

e.getValue());

OUTPUT: of this program

============== Adding Element ===================

PUT adding key:100-Niranjan, value:dept1 to the list

============== Adding Duplicate =================

duplicate key value pair, replacing existing key 100-Niranjan, with value dept12

Traversing the list inside the bucket for the key 100-Niranjan

GET element - 100-Niranjan::dept12

============== Adding Elements ==================

PUT adding key:102-Sravan, value:dept3 to the list

PUT adding key:104-Ananth, value:dept2 to the list

PUT adding key:106-Rakesh, value:dept5 to the list

PUT adding key:108-Shashi, value:dept2 to the list

============== Adding Collisions =================

Collision detected for key 112-Chandu, adding element to the existing bucket

PUT adding key:112-Chandu, value:dept16 to the list

Traversing the list inside the bucket for the key 112-Chandu

GET element - 112-Chandu::dept16

Collision detected for key 114-Santhosh, adding element to the existing bucket

PUT adding key:114-Santhosh, value:dept9 to the list

Traversing the list inside the bucket for the key 114-Santhosh

GET element - 114-Santhosh::dept9

============== Adding Duplicate in Collision ===================

duplicate key value pair, replacing existing key 124-Santhosh, with value dept91

Traversing the list inside the bucket for the key 114-Santhosh
GET element - 114-Santhosh::dept91

ata Structures

LAB-13

Name ____________________
Roll No ___________________
Date ______________________
Marks Obtained ____________
Signature___________________
Binary Search Tree
Objective:Develop Binary search tree in java using node class having left
and right reference variable.

Introduction:

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned
properties −

 The left sub-tree of a node has a key less than or equal to its parent node's key.

 The right sub-tree of a node has a key greater than or equal to its parent node's
key.

Search Operation
Whenever an element is to be searched, start searching from the root node.
Then if the data is less than the key value, search for the element in the left
subtree. Otherwise, search for the element in the right subtree. Follow the same
algorithm for each node.

Insert Operation
Whenever an element is to be inserted, first locate its proper location. Start
searching from the root node, then if the data is less than the key value, search
for the empty location in the left subtree and insert the data. Otherwise, search
for the empty location in the right subtree and insert the data.
Code:

publicclassBinarytree
{
privatestaticNode root;

publicBinarytree(int data)
{
root=newNode(data);
}

publicvoid add(Node parent,Node child,String orientation)

{
if(orientation=="left")
{
parent.setLeft(child);
}
elseif(orientation=="right")
{
parent.setRight(child);
}

publicstaticvoid main(String ar[])

{
Node n1=newNode(1);
Node n2=newNode(4);
Node n3=newNode(2);
Node n4=newNode(5);

Binarytree l1=newBinarytree(3);
l1.add(root,n1,"left");
l1.add(root,n2,"right");
l1.add(root,n3,"left");
l1.add(root,n4,"right");

}
}

classNode{
privateint key;
privateNode left;
privateNode right;
Node(int key){
this.key = key;
right=null;
left=null;
}

publicvoid setKey(int key){

this.key = key;
}

publicint getKey(){
return key;
}
publicvoid setLeft(Node left){
this.left = left;
}

publicNode getLeft(){
return left;
}

publicvoid setRight(Node right ){

this.right = right;
}

publicNode getRight(){
return right;
}

}
 Data Structures

LAB-14

Name ____________________
Roll No ___________________
Date ______________________
Marks Obtained ____________
Signature___________________
 Tree Traversal (In order)
Objective: Implement In order Tree Traversal in Java for BST.

Introduction:

In InOrder traversal, each node is processed between sub trees. In simpler

words, Visit left sub tree, node and then right sub tree.

Steps for InOrder traversal are:

 Traverse the left subtree in InOrder.

 Visit the node.
 Traverse the right subtree in InOrder.

There can be two ways of implementing it

 Recursive
 Iterative

The recursive solution is trivial.

publicclass Solution {
List<Integer> result = new ArrayList<Integer>();

public List<Integer> inorderTraversal(TreeNode root) {

if(root !=null){
helper(root);
}

return result;
}

publicvoid helper(TreeNode p){

if(p.left!=null)
helper(p.left);

result.add(p.val);

if(p.right!=null)
helper(p.right);
}
}

Iterative
The key to solve inorder traversal of binary tree includes the following:

1. The order of "inorder" is: left child -> parent -> right child
2. Use a stack to track nodes
3. Understand when to push node into the stack and when to pop node out
of the stack

//Definition for binary tree

publicclass TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}

publicclass Solution {
public ArrayList<Integer> inorderTraversal(TreeNode root) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
ArrayList<Integer> lst = new ArrayList<Integer>();

if(root == null)
return lst;

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

//define a pointer to track nodes
TreeNode p = root;

while(!stack.empty() || p != null){

// if it is not null, push to stack

//and go down the tree to left
if(p != null){
 stack.push(p);
p = p.left;

// if no left child
// pop stack, process the node
// then let p point to the right
}else{
TreeNode t = stack.pop();
lst.add(t.val);
p = t.right;
}
}

return lst;
}
}

Simple
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
if(root==null)
return result;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);

while(!stack.isEmpty()){
TreeNode top = stack.peek();
if(top.left!=null){
stack.push(top.left);
top.left=null;
}else{
result.add(top.val);
stack.pop();
if(top.right!=null){
stack.push(top.right);
}
}
}

return result;
}
 Data Structures

LAB-15

Name ____________________
Roll No ___________________
Date ______________________
Marks Obtained ____________
Signature___________________
Tree Traversal (Post order)
Objective:Implement post order Tree Traversal in Java for BST.

Introduction:
Suppose that you are given a binary tree like the one shown in the figure below. Write
some code in Java that will do a postorder traversal for any binary tree and print out the
nodes as they are encountered. So, for the binary tree in the figure below, the algorithm
will print the nodes in this order: 2, 5, 11, 6, 7, 4, 9, 5, 2 – where the very last node
visited is the root node

When trying to figure out what the algorithm for this problem should be, you should
take a close look at the way the nodes are traversed – there is a pattern in the way that
the nodes are traversed.

If you break the problem down into subtrees you can see that these are the operations
that are being performed recursively at each node:

1. Traverse the left subtree

2. Traverse the right subtree

3. Visit the root

This sounds simple enough. Let’s now start writing some actual code. But first, we must
have a Node class that represents each individual node in the tree, and that Node class
must also have some methods that would allow us to go to the left and right nodes. This
is what it would look like in Java:

public class Node {

private Node right;

private Node left;
private int nodeValue;

public Node ( )
{
// a Java constructor
}

public Node leftNode() {return left;}

public Node rightNode() {return right;}
public int getNodeValue() {return nodeValue;}

Given the Node class above, let’s write a recursive method that will actually do the
postorder traversal for us. In the code below, we also assume that we have a method
called printNodeValue which will print out the Node’s value for us.

void postOrder (Node root)

{

if(root == null) return;

postOrder( root.leftNode() );
postOrder( root.rightNode() );

root.printNodeValue();

The key to iterativepostorder traversal is the following:

1. The order of "Postorder" is: left child -> right child -> parent node.
2. Find the relation between the previously visited node and the current node
3. Use a stack to track nodes
As we go down the tree to the lft, check the previously visited node. If the current node
is the left or right child of the previous node, then keep going down the tree, and add
left/right node to stack when applicable. When there is no children for current node, i.e.,
the current node is a leaf, pop it from the stack. Then the previous node become to be
under the current node for next loop. You can using an example to walk through the
code.

//Definition for binary tree

publicclass TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}

publicclass Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {

ArrayList<Integer> lst = new ArrayList<Integer>();

if(root == null)
return lst;

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

stack.push(root);

TreeNode prev = null;

while(!stack.empty()){
TreeNode curr = stack.peek();

// go down the tree.

//check if current node is leaf, if so, process it and pop stack,
//otherwise, keep going down
if(prev == null || prev.left == curr || prev.right == curr){
//prev == null is the situation for the root node
if(curr.left != null){
stack.push(curr.left);
}elseif(curr.right != null){
stack.push(curr.right);
}else{
stack.pop();
lst.add(curr.val);
}

//go up the tree from left node

//need to check if there is a right child
//if yes, push it to stack
//otherwise, process parent and pop stack
}elseif(curr.left == prev){
if(curr.right != null){
stack.push(curr.right);
}else{
stack.pop();
lst.add(curr.val);
}

//go up the tree from right node

//after coming back from right node, process parent node and pop stack.
}elseif(curr.right == prev){
stack.pop();
lst.add(curr.val);
}
 prev = curr;
}

return lst;
}
}

Simple Post Order Traversal.

public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();

if(root==null) {
return res;
}

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

stack.push(root);

while(!stack.isEmpty()) {
TreeNode temp = stack.peek();
if(temp.left==null&& temp.right==null) {
TreeNode pop = stack.pop();
res.add(pop.val);
}
else {
if(temp.right!=null) {
stack.push(temp.right);
temp.right = null;
}

if(temp.left!=null) {
stack.push(temp.left);
temp.left = null;
}
}
}

return res;
}