Unit 1

Introduction to Data Structures

Data Structure is a way of collecting and organising data in such a way that we can
perform operations on these data in an effective way.

Classification of Data Structures:

Data structures can be broadly classified into:

1. Primitive Data Structure

2. Non Primitive Data Structure

1. Primitive Data Structure: The Primitive Data Structures are the Data
Structures that can be manipulated directly by machine instructions. They are
the basic fundamental data types. The C language provides the following
Primitive Data types: integer, character, float, double and pointers.

2. Non Primitive Data Structure: The Non Primitive Data Structures are those
that are not defined by the programming language but instead created by the
programmer. These are again classified into 2 types: a) Linear b) Non Linear

a) Linear Data Structures: Here the data elements are arranged in linear
fashion. These includes array, stack, queue and linked list.

Operations applied on linear data structure:

The following list of operations applied on linear data structures

1. Add an element
2. Delete an element
 3. Traverse
4. Sort the list of elements
5. Search for a data element.

b) Non Linear Data Structures: Here the data elements are arranged in
nonlinear fashion. These includes Tree and Graph.

Operations applied on non-linear data structures:

The following list of operations applied on non-linear data structures.

1. Add elements
2. Delete elements
3. Display the elements
4. Sort the list of elements
5. Search for a data element.

Difference between linear and non-linear data structure:

Linear Data Structure Non-Linear Data Structure

Every item is related to its previous and Every item is attached with many other
next item. items.

Data is arranged in linear sequence. Data is not arranged in sequence.

Examples: Array, Stack, Queue, Linked

Examples: Tree, Graph.
List.

Implementation is Easy. Implementation is Difficult.

Abstract Data Type (ADT):

 When an application requires special kind of data which is not available as built
in data type, then its programmers responsibility to implement his own kind of
data.
 The programmer has to specify how to store a value for data, what are
operations that can meaningfully manipulate variables of that kind of data,
amount of memory required to store a variable.
 The programmer has to decide all these things and accordingly implement
them.
 Programmers own data type is termed as abstract data type.
 It is also called as user defined data type.

Pointers
A pointer is a variable that can hold the address of another variable or address of
memory location.

If you have a variable var in your program, &var will give you its address in the memory,
where & is commonly called the reference operator.

Example:

#include <stdio.h>
int main()
{
int var = 5;
printf("Value: %d\n", var);
printf("Address: %u", &var); //Notice, the ampersand(&) before var.
return 0;
}
Output:

Value: 5

Address: 2686778

Pointer Variables:

In C, there is a special variable that stores just the address of another variable. It is
called Pointer variable or, simply, a pointer.

Declaration of Pointer

data_type* pointer_variable_name;

Example: int* p;

Above statement defines, p as pointer variable of type int.

Reference operator (&) and Dereference operator (*):

The referencing operator & is used to access the address of the variables. And using
differencing operator * we can access the value from the address.

Example to print the values using variables and their addresses:

#include <stdio.h>
int main()
{
int *p;
int var = 10;

/* Assigning the address of variable var to the pointer * p. The p can hold the
address of var because var is an integer type variable*/

p= &var;

printf("Value of variable var is: %d", var);

printf("\nValue of variable var is: %d", *p);
printf("\nAddress of variable var is: %p", &var);
printf("\nAddress of pointer p is: %p", &p);
return 0;
}

Output:
Value of variable var is: 10
Value of variable var is: 10
Address of variable var is: 0x7ffe0005dee4
Address of pointer p is: 0x7ffe0005dee8

The steps to be followed to use pointers:

1. Declare a data variable Ex: int x;

2. Declare a pointer variable Ex: int *p;
3. Initialize a pointer variable Ex: p=&x;
4. Access data using pointer variable Ex: y=*p;

Pointer Declaration: Pointer variables should be declared before they are used.
Syntax: data_type *identifier;

Example:

int *pi;

float *pf;

char *pc;

double *pd;

FILE *fb;

Initialization of pointer variables:

It is the process of assigning an address to the pointer variable. Consider the following
example.

1000 1001

3000 3001

The pointer P can be initialized as follows:

a=65;

p=&a;

After the initialization the variable a holds the value 65 and variable p holds the value
of address of a as illustrated below:

65
a

1000 1001

NULL Pointers

It is always a good practice to assign a NULL value to a pointer variable in case you
do not have an exact address to be assigned. This is done at the time of variable
declaration. A pointer that is assigned NULL is called a null pointer.

The NULL pointer is a constant with a value of zero defined in several standard
libraries. Consider the following program −

#include <stdio.h>

int main ()

int *ptr = NULL;

printf("The value of ptr is : %x\n", ptr );

return 0;

When the above code is compiled and executed, it produces the following result:
The value of ptr is 0

Pointers and Function

The mechanism in which pointer variable are used as function parameter is known
as call by reference.

Consider the example where 2 numbers are swapped. The function prototype for the
same is as follows.

void swap (int * p1, int * p2)

When the function is called, the addresses of the variables to be modified are
passed as arguments to the pointer parameters.

Thus to exchange the values of variables a and b this function is called as follows.

swap (&num1, &num2);

The complete program is as follows:

#include<stdio.h>

int main()

int num1 = 5, num2 = 10;

swap(&num1, &num2);

printf("Number1 = %d\n", num1);

printf("Number2 = %d", num2);

return 0;

void swap(int * p1, int * p2)

int temp;

temp = *p1;

*p1 = *p2;

*p2 = temp;

}
Output

Number1 = 10

Number2 = 5

Pointer and Arrays:

In c language pointers can be used to create and handle arrays. Some of the
operations that can be performed on arrays are:

 Traversing an array
 Accessing array element
 Reading an array
 Printing and array

When an array is declared, compiler allocates sufficient amount of memory to

contain all the elements of the array. Base address i.e address of the first
element of the array is also allocated by the compiler.

Suppose we declare an array arr,

int arr[5]={ 1, 2, 3, 4, 5 };

Assuming that the base address of arr is 1000 and each integer requires two bytes,
the five elements will be stored as follows

Here variable arr will give the base address, which is a constant pointer pointing to
the element, arr[0]. Therefore arr is containing the address of arr[0] i.e 1000. In short,
arr has two purpose- it is the name of an array and it acts as a pointer pointing
towards the first element in the array

We can declare a pointer of type int to point to the array arr.

int *p;

p = arr;

or p = &arr[0]; //both the statements are equivalent.

Now we can access every element of array arr using p++ to move from one element
to another.

Example program to find the largest of n numbers using pointers:

#include<stdio.h>

int main()

Int n,num,I,a[10];

int big;

printf("Enter the values of n: ");

scanf("%d",&n);

printf(“Enter the elements”):

for(i=0;i<n;i++)

scanf("%d",&a[i]);

big=*a[0];

pos=0;

for(i=0;i<=n-1;i++)

if(*a[i]>big)

big=*a[i];;

pos=i;

printf("Largest number is: %d",big);

printf(“position=%d”,i);

return 0;

C Program to compute sum of the array elements using pointers:

#include<stdio.h>
#include<stdlib.h>

void main()

int numArray[10];

int i, sum = 0;

int *ptr;

printf("\nEnter 10 elements : ");

for (i = 0; i < 10; i++)

scanf("%d", &numArray[i]);

ptr = numArray; /* a=&a[0] */

for (i = 0; i < 10; i++) {

sum = sum + *ptr;

ptr++;

printf("The sum of array elements : %d", sum);

Array of Pointers:

There may be a situation when we want to maintain an array, which can store
pointers to an int or char or any other data type available. Following is the
declaration of an array of pointers to an integer −

int *ptr[MAX];

It declares ptr as an array of MAX integer pointers. Thus, each element in ptr, holds
a pointer to an int value. The following example uses three integers, which are stored
in an array of pointers, as follows −

#include <stdio.h>

#include<stdlib.h>

const MAX = 3;

int main ()
{

int var[] = {10, 100, 200};

int i, *ptr[MAX];

for ( i = 0; i < MAX; i++)

ptr[i] = &var[i]; /* assign the address of integer. */

for ( i = 0; i < MAX; i++)

printf("Value of var[%d] = %d\n", i, *ptr[i] );

return 0;

Output:

We can also use an array of pointers to character to store a list of strings as follows:

#include <stdio.h>

const MAX = 4;

int main ()

char *names[] = {

"Zara Ali",

"Hina Ali",

"Nuha Ali",
 "Sara Ali"

};

int i = 0;

for (i = 0; i < MAX; i++)

printf("Value of names[%d]=%s\n",i,names[i]);

return 0;

Output:

Pointer Arithmetic

Similar to the way arithmetic operations are possible on normal variables, it is possible
to perform arithmetic operations on pointers as well. Various Arithmetic operations that
can be carried out are incrementing, decrementing, addition, subtraction and
comparison.

Incrementing a Pointer

We prefer using a pointer in our program instead of an array because the variable
pointer can be incremented, unlike the array name which cannot be incremented
because it is a constant pointer. The following program increments the variable pointer
to access each succeeding element of the array −

#include <stdio.h>

const MAX = 3;

int main ()

int var[] = {10, 100, 200};

int i, *ptr;
ptr = var;

for ( i = 0; i < MAX; i++) {

printf("Address of var[%d] = %d\n", i, ptr );

printf("Value of var[%d] = %d\n", i, *ptr );

ptr++;

return 0;

Decrementing a Pointer

The same considerations apply to decrementing a pointer, which decreases its value
by the number of bytes of its data type as shown below −

#include <stdio.h>

const MAX = 3;

int main ()

int var[] = {10, 100, 200};

int i, *ptr;

ptr = &var[MAX-1];

for ( i = MAX; i > 0; i--) {

printf("Address of var[%d] = %x\n", i-1, ptr );

printf("Value of var[%d] = %d\n", i-1, *ptr );

ptr--;

return 0;

Pointer Addition:

In C Programming we can add any integer number to Pointer variable. It is perfectly

legal in c programming to add integer to pointer variable.
In order to compute the final value, we need to use following formulae:

final value = (address) + (number * size of data type)

Consider the following example:

int *ptr , n;

ptr = &n ;

ptr = ptr + 3;

Increment Integer Pointer

#include<stdio.h>

int main()

int *ptr=(int *)1000;

ptr=ptr+3;

printf("New Value of ptr : %u",ptr);

return 0;

Pointer Subtraction:

In C Programming we can subtract any integer number to Pointer [Link] order to

compute the final value we need to use following formulae:

final value = (address) - (number * size of data type)

Pointers Comparison

The pointers can be compared with each other only if both the pointers are pointing to
similar type of data. i.e two pointers should point to char or both the pointers should
point to int etc.

Example: if(ptr2==ptr1)

Pointers are equal to each other.

Example: if(ptr2>ptr1)
Pointer ptr2 is far from ptr1

Character Pointer

The pointer to character and array of characters is called as character pointer. In C

character pointer can be used to access strings. A character pointer is created as
shown below:

char *a;

Character pointers can be initialized as shown below:

char *a= “Hello”;

In this case memory is created as shown below:

a H E L L O \0

2000 3000 3005

Pointer a

Pgm:

#include<stdio.h>

int main()

char *s=”Hello”;

printf(“%s”,s);

return 0;

Output:

Pointer to Pointer

A pointer to a pointer is a form of multiple indirection, or a chain of pointers. Normally,

a pointer contains the address of a variable. When we define a pointer to a pointer,
the first pointer contains the address of the second pointer, which points to the
location that contains the actual value as shown below.

A variable that is a pointer to a pointer must be declared as such. This is done by

placing an additional asterisk in front of its name. For example, the following
declaration declares a pointer to a pointer of type int :

int **var;

When a target value is indirectly pointed to by a pointer to a pointer, accessing that

value requires that the asterisk operator be applied twice, as is shown below in the
example −

#include <stdio.h>

int main ()

int var;

int *ptr;

int **pptr;

var=3000;

ptr=&var;

pptr=&ptr;

printf("Value of var = %d\n",var);

printf("Value available at *ptr = %d\n",*ptr);

printf("Value available at **pptr = %d\n",**pptr);

return 0;

Output:
Structure

Structure is used to store the information of one particular object but if we need to
store such 100 objects then Array of Structure is used.

Eg:

struct Bookinfo

char bname[20];

int pages;

float price;

}Book[100];

Explanation:

Here Book structure is used to Store the information of one Book.

In case if we need to store the Information of 100 books then Array of Structure is
used.

b1[0] stores the Information of 1st Book , b1[1] stores the information of 2nd Book and
So on We can store the information of 100 books.

Accessing Pages field of Second Book :

Book[1].pages

Example :

#include <stdio.h>

struct Bookinfo

char bname[20];

int pages;
float price;

}book[3];

int main(int argc, char *argv[])

int i;

for(i=0;i<3;i++)

printf("\nEnter the Name of Book : ");

gets(book[i].bname);

printf("\nEnter the Number of Pages : ");

scanf("%d",book[i].pages);

printf("\nEnter the Price of Book : ");

scanf("%f",book[i].price);

printf("\n--------- Book Details ------------ ");

for(i=0;i<3;i++)

printf("\nName of Book:%s",book[i].bname);

printf("\nNumber of Pages:%d",book[i].pages);

printf("\nPrice of Book:%f",book[i].price);

return 0;

Linear Data Structures- Stacks

Stack is a non-primitive linear data structure. It is an ordered list in which addition of

new data and deletion of existing data item is done from only one end known as top
of stack (TOP). Here the last added element will be the first to be removed from the
stack. That is the reason why stack is called Last in First Out (LIFO) type of list.
The initial value of TOP=-1 and final value of TOP=MAX-1

Array Representation of Stack:

Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow
condition.

Pop: Removes an item from the stack. The items are popped in the reversed order in
which they are pushed. If the stack is empty, then it is said to be an Underflow
condition.

Example:

Data to be inserted are as follows: consider the maximum size=5

10, 20, 30, 40, 50

Data is pushed on to the stack 10,20,30,40,50 respectively.

Pop operation is shown as below:

deleted item=50 deleted item=40

Step 1 Step 2

Deleted item=30 Deleted item=20

Step 3 Step 4
Step 5: Stack is empty

Values of stack and top:

Operation Explanation

top= -1 Indicates empty stack

top = top + 1 After push operation value of top is incremented by 1

top = top - 1 After pop operation value of top is decremented by 1

C function for push operation:

void push (int a[], int item)

if (top == (MAX-1))

status = 0;

else

++top;

stack [top] = item;

C function for pop operation:

int pop (int stack[])

int ret;

if (top == -1)

{ printf(“Stack is empty”);

else

{ s = a [top];

--top;

return s;

C function for display operation:

void display (int a[])

int i;

printf ("\nThe Stack is: ");

if (top == -1)

printf (" Stack is empty");

else

for (i=top; i>=0; i--)

printf (“%d”,a[i]);

printf ("\n");

Application of stack data structure:

1) Balancing symbols. To check proper opening and closing of parenthesis. For eg. in
your program there is mismatch of brackets. So stack can be used.

2) Infix to postfix/ prefix conversion. Using stack, we can efficiently convert from infix
to postfix, infix to prefix etc.

3) Redo-Undo functionality in a software. At many places like editors, Photoshop.

4) Forward and backward feature in web browsers.

5) Recursion: A function which calls itself is called recursion. Used in many algorithms
like tower of Hanoi, tree traversals etc can be implemented very efficiently using
recursion. It is very important facility available in variety of programming languages
such as C, C++ etc.

6) Stack can be used in back tracking problem, Knight tour problem, N queen problem
etc.

7) Other application stack can be used like to find whether string is palindrome or not,
check whether given expression is valid or not.

8) Stacks are also used in syntax parsing for many compilers. In graph algorithm like
topological sorting and strongly connected components.

Program for Stack in C [Push, Pop and Display]:

#include<stdio.h>

#include<stdlib.h>

#define MAX 5 //Maximum number of elements that can be stored

int top=-1,stack[MAX];

void push();

void pop();

void display();

void main()

{
 int ch;

while(1) //infinite loop, will end when choice will be 4

printf("\n*** Stack Menu ***");

printf("\n\[Link]\[Link]\[Link]\[Link]");

printf("\n\nEnter your choice(1-4):");

scanf("%d",&ch);

switch(ch)

case 1: push();

break;

case 2: pop();

break;

case 3: display();

break;

case 4: exit(0);

default: printf("\nWrong Choice!!");

void push()

int val;

if(top==MAX-1)

printf("\nStack is full!!");
 }

else

printf("\nEnter element to push:");

scanf("%d",&val);

top=top+1; //increment the top

stack[top]=val; //insert into stack

void pop()

if(top==-1)

printf("\nStack is empty!!");

else

printf("\nDeleted element is %d",stack[top]);

top=top-1;

void display()

int i;

if(top==-1)

{
 printf("\nStack is empty!!");

else

printf("\nStack is...\n");

for(i=top;i>=0;--i)

printf("%d\n",stack[i]);

Structure Representation of Stack:

Using Structure stack can be declared as follows:

struct stack

int data[MAX];

int top;

}s;

Push Function

void push(struct stack *s, int num)

{

if (stop==(MAX – 1))

printf(“Stack Overflow”);

else

s->top = s->top + 1;
sdata[stop] = num;
}

Pop Function

int Pop(struct stack *s)

{
int temp;
if(s->top==-1)
{
printf(“Stack Underflow”);
}
else
{
temp=s -> data[s->top];
s ->top--;
}
return temp;
}

Display Function

void display (struct stack *s, int data[])

int i;

printf ("\nThe Stack is: ");

if (s->top == -1)

printf (" Stack is empty");

else

for (i=s->top; i>=0; i--)

ss=s->item[i];

printf (“%d\n”,ss);

printf ("\n");

Expression:

An expression is a collection of operators and operands that represents a specific

value.
Expression Types:

Based on the operator position, expressions are divided into THREE types. They are
as follows:

1. Infix Expression
2. Postfix Expression
3. Prefix Expression

Infix Expression: In infix expression, operator is used in between operands.

The general structure of an Infix expression is as follows...

Operand1 Operator Operand2

Example: a+b

Postfix Expression: In postfix expression, operator is used after operands.

The general structure of Postfix expression is as follows...

Operand1 Operand2 Operator

Example: ab+

Prefix Expression: In prefix expression, operator is used before operands

The general structure of Prefix expression is as follows...

Operator Operand1 Operand2

Example: +ab

Operator precedence

The rule that determine the order in which different operators are evaluated are
called precedence of operators.

It determines which operator is performed first in an expression with more than one
operators with different precedence.

Operation Operators Precedence

Exponential ^ Highest
 Multiplication, Division *, / Next

Addition, subtraction +, - Last

Remember:

a) An arithmetic expression is evaluated from left to right.

b) Exponentiation operation (^) is evaluated from right to left

c) Parenthesized expression is evaluated first

Eg:

Solve 10 + 20 * 30

10 + 20 * 30 is calculated as 10 + (20 * 30) and not as (10 + 20) * 30

Operators Associativity:
The order in which the operators with same precedence are evaluated in an
expression is called associativity of the operators. It is used when two operators of
same precedence appear in an expression. Associativity can be either Left to Right
or Right to Left.
For example: ‘*’ and ‘/’ have same precedence and their associativity
is Left to Right, so the expression “100 / 10 * 10” is treated as “(100 / 10) * 10”.
Eg: Solve 100 + 200 / 10 - 3 * 10
What is left associative?

In an expression if 2 or more operators have the same priority and are evaluated
from left to right then it is called left associative.

What is right associative?

In an expression if 2 or more operators have the same priority and are evaluated
from right to left then it is called right associative.

Conversion of infix Expression to Postfix Expression:

Algorithm

1. Scan the infix expression from left to right.

2. If the scanned character is an operand, output it.

3. Else,

a) If the precedence of the scanned operator is greater than the precedence of the
operator in the stack (or the stack is empty), push it.
b) Else, Pop the operator from the stack until the precedence of the scanned
operator is less-equal to the precedence of the operator residing on the top of the
stack. Push the scanned operator to the stack.

4. If the scanned character is an ‘(‘, push it to the stack.

5. If the scanned character is an ‘)’, pop and output from the stack until an ‘(‘is
encountered.

6. Repeat steps 2-6 until infix expression is scanned.

7. Pop and output from the stack until it is not empty.

Eg: 1) Obtain the postfix expression for ((A+(B-C) *D) ^E+F) by substitution
method:

We can convert into postfix expression based on precedence and associativity

2) A+(B*C-(D/E-F)*G)*H

Stack Input Output

Empty A+(B*C-(D/E-F)*G)*H -

Empty +(B*C-(D/E-F)*G)*H A

+ (B*C-(D/E-F)*G)*H A

+( B*C-(D/E-F)*G)*H A

+( *C-(D/E-F)*G)*H AB

+(* C-(D/E-F)*G)*H AB

+(* -(D/E-F)*G)*H ABC

+(- (D/E-F)*G)*H ABC*

+(-( D/E-F)*G)*H ABC*

+(-( /E-F)*G)*H ABC*D

+(-(/ E-F)*G)*H ABC*D

 +(-(/ -F)*G)*H ABC*DE

+(-(- F)*G)*H ABC*DE/

+(-(- F)*G)*H ABC*DE/

+(-(- )*G)*H ABC*DE/F

+(- *G)*H ABC*DE/F-

+(-* G)*H ABC*DE/F-

+(-* )*H ABC*DE/F-G

+ *H ABC*DE/F-G*-

+* H ABC*DE/F-G*-

+* End ABC*DE/F-G*-H

Empty End ABC*DE/F-G*-H*+

Prefix notation also known as Polish notation

Postfix notation also known as Reverse Polish notation

Evaluation of Postfix Expression:

Procedure:

1) Create a stack to store operands (or values).

2) Scan the given expression and do following for every scanned element.
a) If the element is a number, push it into the stack
b) If the element is a operator, pop 2 operands from the stack and evaluate it
and push the result back to the stack
3) When the expression is ended, the number in the stack is the final answer

Example:
1) Let the given expression be “2 3 1 * + 9 -“.

We scan all elements one by one.

1) Scan ‘2’, it’s a number, so push it to stack. Stack contains ‘2’
2) Scan ‘3’, again a number, push it to stack, stack now contains ‘2 3’ (from bottom
to top)
3) Scan ‘1’, again a number, push it to stack, stack now contains ‘2 3 1’
4) Scan ‘*’, it’s an operator, pop two operands from stack, apply the * operator on
operands, we get 3*1 which results in 3. We push the result ‘3’ to stack. Stack now
becomes ‘2 3’.
5) Scan ‘+’, it’s an operator, pop two operands from stack, apply the + operator on
operands, we get 3 + 2 which results in 5. We push the result ‘5’ to stack. Stack now
becomes ‘5’.
6) Scan ‘9’, it’s a number, we push it to the stack. Stack now becomes ‘5 9’.
7) Scan ‘-‘, it’s an operator, pop two operands from stack, apply the – operator on
operands, we get 5 – 9 which results in -4. We push the result ‘-4’ to stack. Stack
now becomes ‘-4’.
8) There are no more elements to scan, we return the top element from stack (which
is the only element left in stack).
Algorithm for Evaluation of Postfix Expression
Initialize(Stack S)
x = ReadToken(); // Read Token
while(x)
{
if ( x is Operand )
Push ( x ) Onto Stack S.

if ( x is Operator )
{
Operand2 = Pop(Stack S);
Operand2 = Pop(Stack S);
Evaluate (Operand1,Operand2,Operator x);
}

x = ReadNextToken(); // Read Token

}

Recursion

A function that calls itself is known as a recursive function. And, this technique is
known as recursion. The recursion continues until some condition is met to prevent
it.

Recursive function to calculate factorial of a number:

int factorial(int i)

if(i <= 1) {

return 1;

return i * factorial(i - 1);

Recursive function to calculate Fibonacci of a number:

int fibonacci(int i)

if(i == 0)

return 0;
 }

if(i == 1)

return 1;

return fibonacci(i-1) + fibonacci(i-2);

Tower of Hanoi:

Tower of Hanoi is a mathematical puzzle which consists of three towers (pegs) and more than
one rings is as depicted −

These rings are of different sizes and stacked upon in an ascending order, i.e. the
smaller one sits over the larger one. There are other variations of the puzzle where
the number of disks increase, but the tower count remains the same.

Rules

The mission is to move all the disks to some another tower without violating the
sequence of arrangement. A few rules to be followed for Tower of Hanoi are −

 Only one disk can be moved among the towers at any given time.

 Only the "top" disk can be removed.

 No large disk can sit over a small disk.

Recursive function for tower of Hanoi problem:

Void tower(int n, int source, int temp, int destination)

if (n==0) return;

tower(n-1,source, destination, temp);

printf (“ Move disc %d from %c to %c\n”, n, source, destination);

tower(n-1,temp,source,destination);

Consider the number of discs=3

The steps are illustrated below:

Move disc 1 from A to C

Move disc 2 from A to B

Move disc 1 from C to B

Move disc 3 from A to C

Move disc 1 from B to A

Move disc 2 from B to C

Move disc 1 from A to C

Calculate power of a number program using recursion

#include <stdio.h>

//function for calculating power

long int getPower(int b,int p)

long int result=1;

if(p==0) return result;

result=b*(getPower(b,p-1)); //call function again

int main()

int base,power;

long int result;

printf("Enter value of base: ");

scanf("%d",&base);

printf("Enter value of power: ");

scanf("%d",&power);

result=getPower(base,power);

printf("%d to the power of %d is: %ld\n",base,power,result);

return 0;

Find gcd of a number using recursion in c program

#include<stdio.h>

int main(){

int n1,n2,gcd;

printf("\nEnter two numbers: ");

scanf("%d %d",&n1,&n2);

gcd=findgcd(n1,n2);
 printf("\nGCD of %d and %d is: %d",n1,n2,gcd);

return 0;

int findgcd(int x,int y){

while(x!=y){

if(x>y)

return findgcd(x-y,y);

else

return findgcd(x,y-x);

return x;

Count digits of a number program using recursion.

#include <stdio.h>

//function to count digits

int countDigits(int num)

static int count=0;

if(num>0)

count++;

countDigits(num/10);

else

return count;

}
}

int main()

int number;

int count=0;

printf("Enter a positive integer number: ");

scanf("%d",&number);

count=countDigits(number);

printf("Total digits in number %d is: %d\n",number,count);

return 0;

Sum of digits of a number program using recursion.

#include <stdio.h>

//function to calculate sum of all digits

int sumDigits(int num)

static int sum=0;

if(num>0)

sum+=(num%10); //add digit into sum

sumDigits(num/10);

else

return sum;
 }

int main()

int number,sum;

printf("Enter a positive integer number: ");

scanf("%d",&number);

sum=sumDigits(number);

printf("Sum of all digits are: %d\n",sum);

return 0;

Advantages and Disadvantages of Recursion

Recursion makes program elegant and cleaner. All algorithms can be defined
recursively which makes it easier to visualize and prove.

If the speed of the program is vital then, you should avoid using recursion.
Recursions use more memory and are generally slow. Instead, you can use loop.

UNIT 2

Linear Data structures- Queue

Queue

It is a linear structure where elements are inserted from one end and elements are
deleted from other end. The end at which new elements are added is called rear and
the end from which elements are deleted is called front. Using the approach, first
element inserted is the first element to be deleted out, hence queue can be called First
in First out (FIFO) data structure. A good example of queue is any queue of consumers
for a resource where the consumer that came first is served first.

The difference between stacks and queues is in removing. In a stack we remove the
item the most recently added; in a queue, we remove the item the least recently
added.

Different types of queue:

a) Linear queue (Ordinary queue)

b) Circular queue

c) Priority queue

a) Linear queue:

Here elements will be inserted from one end and elements are deleted from other end.
The end at which new elements are added is called rear and the end from which
elements are deleted is called front.

Eg: Consider the queue having the elements 10, 50 and 20.

10 50 20

0 1 2 3 4

front rear

Here the items are inserted into queue in the order 10, 50 and 20. The variable q is
used as an array to hold these elements. Item 10 is the first element inserted. So,
the variable first is used as index to the first element. Item 20 is the last element
inserted. So, the variable rear is used as index to the last element.

Operations on Queue:

Insertion:

Step 1:

QUEUE_SIZE = 5

10 20 30 40 50

0 1 2 3 4

front rear

We can observe that whenever rear value is equal to “QUEUE_SIZE -1” insertion is
not possible. The code for this can be written as:

if (rear==QUEUE_SIZE -1)

printf(“Queue is full\n”);
 return;

Step 2: If the condition QUEUE_SIZE – 1 is not satisfied, it means the queue is not
full and an element can be inserted at the rear end. Observe that item has to be after
30 at position 3. That is, before inserting an item, we have to increment rear by one.
This can be achieved by

rear = rear +1;

Item = 40

10 20 30

0 1 2 3 4

front rear

Step 3: Now the item can be inserted at rear position. This can be achieved by copying
item into q[rear] as: q[rear] = item;

Item = 40

10 20 30 40

0 1 2 3 4

front rear

C Function to insert an item at the rear end of queue:

void Insert_Rear()

if(rear==QUEUE_SIZE – 1) //check for overflow of queue

printf(“Queue overflow\n”);

return;

rear = rear +1;

q[rear] = item; //insert the item

Deletion:

In queue, an item is always removed from the front end of queue.

Step 1: To check whether queue is empty or not?

10 20 30

0 1 2 3 4

front rear

3 items are present in queue

front < rear

10 20 30

0 1 2 3 4

front

rear

front == rear

So we can see the above 2 figures that if front is less than or equal to rear some
elements are present. Otherwise, it that is front is greater than rear then queue is
empty. We can check for empty queue using the following statement:

if (front > rear) return -1 //Queue is empty

Step 2: When the above condition fails, we can delete an item from a front end of
queue. So for this, we have to access and return the first element and increment
value of front by 1 as:

return q[front++];

C function to delete an element from the front end of queue:

int delete_Front()
{

if(front> rear) return -1;

return q[front++];

Display:

Step 1: Check for empty queue:

if(front>rear)

printf(“Queue is empty”);

return;

Step 2: If elements are present in queue control comes out of the above if
statements. Assume that queue contains 3 elements:

20 25 10

-1 0 1 2 3 4

front rear

The contents of queue can be displayed as:

printf(“%d\n”,s[0]); Output: 20

printf(“%d\n”,s[1]); 25

printf(“%d\n”,s[2]); 10

In general we use printf(“%d\n”,s[i]);

Now the code takes the following form:

for(i=front;i<=rear;i++)

printf(“%d\n”,s[i]);

C function to display:
void display()

if(front>rear) //if queue is empty

printf(“queue is empty\n”);

return;

printf("\ncontents of queues are: "); //display contents of queue

for(i=front;i<=rear;i++)

printf("%d",q[i]);

Real world examples of Queue:

1. Simulation and operating system

2. Operating system maintains a queue of processes that are ready to execute

or that are ready to execute.

3. The holding area in computer system for communicating messages between

2 processes is usually called buffer which is implemented as a queue.

Drawback of ordinary Queue:

Consider the queue shown below:

The above situation arises when 5 elements say 10, 20,30,40,50 are inserted and
then deleting first 2 items 10 and 20. It is not possible to insert an item. Even if there
is space available insertion cannot be made. Because we have Queue Overflow
condition as QSIZE-1. This is the drawback of an ordinary queue.

Applications of Queue
1. Queues are widely used as waiting lists for a single shared resource like
printer, disk, CPU.
2. Queues are used in asynchronous transfer of data (where data is not being
transferred at the same rate between two processes) for eg. pipes, file IO,
sockets.
3. Queues are used as buffers in most of the applications like MP3 media player,
CD player, etc.
4. Queue are used to maintain the play list in media players in order to add and
remove the songs from the play-list.
5. Queues are used in operating systems for handling interrupts.

C Program to implement ordinary queue using global variables:

#include <stdio.h>
#include <stdlib.h>
#define que_size 5
int rear,front,item,q[10];
void insertq()
{
if (rear==que_size-1) //check for overflow of queue
printf("QUEUE OVERFLOW \n");
else
{
rear=rear+1; //increment rear and insert item
q[rear]=item;
}
}
int deleteq()
{
if(front>rear) //Queue is empty
return-1;
else
return(q[front++]);
}
void display()
{
int i;
if(front>rear) //check for empty queue
printf("QUEUE UNDERFLOW \n");
else
{
for(i=front;i<=rear;i++)
{
printf("%d\t",q[i]); //here contents of queue is displayed
}
printf("\n");
}
}
int main()
{
int ch, delitem;
front=0;
rear=-1;
while(1)
{
printf("[Link] [Link] [Link] [Link] \n");
printf("ENTER YOUR CHOICE \n");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("ENTER THE ITEM \n");
scanf("%d",&item);
insertq();
break;
case 2: delitem=deleteq();
if(delitem==-1)
 printf("QUEUE UNDERFLOW \n");
else
printf("DELETED ITEM = %d\n",delitem);
break;
case 3: display();
break;
case 4:exit(0);
default :printf("INVALID CHOICE !!! TRY AGAIN\n");
break;
}
}
return 0;
}
Output:
Representation of queue using structure

struct queue

int item[size];
int rear, front;

}q;

The initial value of rear and front when queue is empty is as follows.

Rear=-1 and front=0;

Size is the maximum size of the array used.

b) Circular Queue:

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’.

Queue operations work as follows:

 Two pointers called FRONT and REAR are used to keep track of the first and
last elements in the queue.
 When initializing the queue, we set the value of FRONT and REAR to -1.
 On enqueing an element, we circularly increase the value of REAR index and
place the new element in the position pointed to by REAR.
 On dequeing an element, we return the value pointed to by FRONT and
circularly increase the FRONT index.
 Before enqueing, we check if queue is already full.
 Before dequeing, we check if queue is already empty.
 When enqueing the first element, we set the value of FRONT to 0.
 When dequeing the last element, we reset the values of FRONT and REAR to
-1.

Example:
In a normal Queue, we can insert elements until queue becomes full. But once queue
becomes full, we cannot insert the next element even if there is a space in front of
queue. Whenever front is 0 and rear either -1 or Queue_Size – 1, queue is empty.
Whenever item is inserted, rear is incremented by 1. Whenever we have to delete the
elements, then we have to delete at front end.

 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:
1. Check whether queue is Empty means check (front==-1).
2. If it is empty then display Queue is empty. If queue is not empty then step
3
 3. 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.

Pictorial representation of circular queue:

When queue is empty, front =0 and rear =-1. But in circular queue just before index 0,
we have index 4. So instead of rear=-1 we can write rear=4 also. So empty queue is
represented by following initialization statements:

front=0;

rear=-1;

The above statements indicate empty queue can also be represented as:

front=0;

rear=4; //rear=4. In general rear=Que_Size-1

Eg: The contents of circular queue after performing each of the following operations:

a) Empty queue

b) Insert 10

c) Insert 20 and 30

d) Insert 40 and 50

e) Insert 60

f) Delete 2 items

g) Insert 60
h) Insert 80

Step 1: Empty queue: Whenever front is 0 and rear is either -1 or QUE_SIZE -1,
queue is empty. An empty queue can be represented as:

Step 2: Insert 10: After incrementing rear by 1, 10 is inserted as:

Step 3: Insert 20 and 30: Here we have to increment rear by 1 and insert 20. Again
increment rear by 1 and insert 30 as:

Step 4: Insert 40 and 50: Increment rear by 1 and insert 40. Again increment rear by
1 and insert 50 as:
Step 5: Insert 60: Queue is full. It is not possible to insert any element into queue. So,
contents of queue have not been changed here.

Step 6: Delete: An item has to be deleted always from the front end. So, 10 is deleted
and contents of queue after deleting 10 is:

Step 7: Delete: An item has to be deleted always from the front end. So 20 is deleted
and contents of queue after deleting 20 is:

Step 8: Inserting 60: Increment rear by 1, its value is 0 and insert 60 at 0th location
as:
Step 9: Inserting 70: Increment rear by 1 and insert 70 as:

Step 10: Insert 80: Queue is full. It is not possible to insert any element into queue.
So, contents of queue have not been changed.

InsertQ()

Step 1: Check for overflow: Before inserting an item, we check whether sufficient
space is available in the queue.

if(count==Queue_Size)

printf(“ Queue is full\n”);

return;

Step 2: Insert item: Increment rear by 1 and then take the mod operation and then
insert the item as shown below:

rear = (rear+1)%Queue_Size;

q[rear]=item;
Step 3: Update count:

As we insert an element an item, the count is incremented by 1. This indicates at any

point of time; the variable count contains the total number of items present in the
queue.

void InsertQ()

if(count==Que_Size)

printf(“Queue overflow”);

return;

rear=(rear+1)%Que_Size;

q[rear]=item;

count++;

DeleteQ():

Step 1: Check for underflow: Before deleting an element from queue, we check
whether sufficient queue is empty or not. This can be achieved using the statement:

if(count==0) return -1;

When the above condition fails, it means queue is not empty and return the element
present at the front end of queue.

Step 2: Access the first item: This is achieved by accessing the element using index
front and then updating front by adding 1 to it and then take mod value. The equivalent
statements can be written as:

item=q[front]; //access the item

front=(front+1)%Que_Size; //update front so that it contains index of next element

Step 3: Update count: As we delete an element from queue, decrement count by 1.

This is achieved using the following statement:

count--;

Step 4: Return the element which was at the front end using the statement:

return item;

C function to delete an item from the front end of circular queue:

int DeleteQ()

if(count==0) return -1;

item = q[front];

front = (front+1)%Que_Size;

count - =1; //decrement the count

return item;

DisplayQ():

Step 1: Check for underflow: This is achieved using the following statement:

if(count==0)

printf(“Queue is empty\n”);

return;

Step 2: Display: Display starts from the front index. After displaying q[front] we have
to update front by 1. (That is by incrementing front by 1 and then taking the modulus).
The procedure is repeated for count number of times. This is because, count contains
the number of items in queue. The code can be written as:

for (i=1,f=front;i<=count;i++)

printf(“%d\n”,q[f]);

f=(f+1)%Que_Size;

C function to display the contents of circular queue:

void display()

int i,f;

if(count==0)

printf(“Q is empty\n”);

return;

printf(“Contents of queue is\n”);

for(i=1,f=front;i<=count;i++)

printf(“%d\n”,q[f]);

f=(f+1)%Que_Size;

}
c) Priority Queue: A queue in which we are able to insert items or remove items from
any position based on some priority is often referred as Priority queue. Always an
element with highest priority is processed before processing any of the lower priority
elements. If the elements in the queue are of same priority, then the element which is
inserted first into the queue is processed.

The priority queue is classified into 2 groups:

Ascending priority queue:

In an ascending priority queue elements can be inserted in any order. But, while
deleting an element from the queue, only the smallest element is removed first.

Descending priority queue:

In descending priority queue also elements can be inserted in any order. But, while
deleting an element from the queue, only the largest element is deleted first.

How to implement priority queues?

There are various methods of implementing priority queue using arrays.

1) One method to implement an ascending priority queue where elements can be

inserted in any fashion and only the smallest element is removed. Here, an element is
inserted from rear end of the queue but an element with least value should be deleted.
After deleting the smallest number, store a very large value in that location, indicating
the absence of an item. The variable count can be used to keep track of number of
elements in the array.

The 3 functions useful for this purpose are:

insert_rear() – which inserts the item at the end of the queue.

remove_small() – which inserts the smallest item from the queue and at the same time
store maximum number in that location indicating an item has been deleted.

display() – which displays the content of the queue.

2) The second technique is to insert the item based on the priority. In this technique,
we assume the item to be inserted itself denotes the priority. So, the items with least
value can be considered as the items with highest priority and items with highest value
can be considered as the items with least priority. So, to implement priority queue we
insert the elements in queue in such a way that they are always ordered in ascending
order. With this technique the highest priority elements are at front end of the queue
and lowest priority elements are at rear end of the queue. So while we are deleting an
item, always delete from the front end so that highest priority element is deleted first.

C code for the function to insert an item at the correct place in priority queue:

void insert_item(int item, int q[], int *r)

int j;

if(*r==Queue_Size – 1) //Check for overflow

printf(“Q is full\n”);

return;

j=*r; // compare from this initial rear pointer

while(j>=0 && item <q[j]) //find appropriate position to allocate space for inserting an
item based on the priority

q[j+1]=q[j]; //Move the item at q[j] to its next position

j--;

q[j+1]=item; //insert an item at the appropriate position

*r=*r+1 //Update the rear pointer

}
 Linear Data Structures- Singly Linked List

Dynamic Memory Allocation

C is a structured language, it has some fixed rules for programming. One of it

includes changing the size of an array. An array is collection of items stored at
continuous memory locations.

As it can be seen that the length (size) of the array above made is 9. But what if
there is a requirement to change this length (size). For Example,

 If there is a situation where only 5 elements are needed to be entered in this

array. In this case, the remaining 4 indices are just wasting memory in this
array. So there is a requirement to lessen the length (size) of the array from 9 to
5.
 Take another situation. In this, there is an array of 9 elements with all 9 indices
filled. But there is a need to enter 3 more elements in this array. In this case 3
indices more are required. So the length (size) of the array needs to be
changed from 9 to 12.
This procedure is referred to as Dynamic Memory Allocation in C.
Therefore, C Dynamic Memory Allocation can be defined as a procedure in which the size
of a data structure (like Array) is changed during the runtime.

The process of allocating memory at runtime is known as dynamic memory allocation.

Library routines is known as "memory management functions" which are used for
allocating and freeing memory during execution of a program.

Now let us see the difference between static memory allocation and dynamic memory
allocation:
 static memory allocation dynamic memory allocation

memory is allocated at compile time. memory is allocated at run time.

memory can't be increased while memory can be increased while

executing program. executing program.

used in array. used in linked list.

C provides some functions to achieve these tasks. There are 4 library functions
provided by C defined under <stdlib.h> header file to assist dynamic memory
allocation in C programming. They are:
1. malloc()
2. calloc()
3. free()
4. realloc()
Function Description

malloc() allocates requested size of bytes and returns a void pointer pointing to
the first byte of the allocated space

calloc() allocates space for an array of elements, initialize them to zero and then
returns a void pointer to the memory

free releases previously allocated memory

realloc modify the size of previously allocated space

Malloc ()

malloc () function is used for allocating block of memory at runtime. This function
reserves a block of memory of given size and returns a pointer of type void. This
means that we can assign it to any type of pointer using typecasting. If it fails to allocate
enough space as specified, it returns a NULL pointer.

Syntax:

void* malloc(byte-size)

Example using malloc() :

int *x;

x = (int *)malloc(100*sizeof(int)); //Since the size of int is 4 bytes, this statement will allocate
400 bytes of memory. And, the pointer ptr holds the address of the first byte in the allocated
memory.

free(x);

calloc()

Calloc is also called “contiguous allocation”. calloc() is another memory allocation

function that is used for allocating memory at runtime. calloc function is normally used
for allocating memory to derived data types such as arrays and structures. If it fails to
allocate enough space as specified, it returns a NULL pointer.

Syntax:

void *calloc(number of items, element-size)

Example using calloc ():

ptr = (float*) calloc(25, sizeof(float)); //This statement allocates contiguous space in

memory for 25 elements each with the size of the float.
realloc()

realloc () changes memory size that is already allocated dynamically to a variable.

realloc in C is used to dynamically change the memory allocation of a previously allocated
memory. In other words, if the memory previously allocated with the help of malloc or calloc is
insufficient, realloc can be used to dynamically re-allocate memory. re-allocation of memory
maintains the already present value and new blocks will be initialized with default garbage
value.

Syntax:

ptr = realloc(ptr, newSize);

where ptr is reallocated with new size 'newSize'.

Example using realloc() :

int *x;

x=(int*)malloc(50 * sizeof(int));

x=(int*)realloc(x,100); //allocated a new memory to variable x

If space is insufficient, allocation fails and returns a NULL pointer.

free():

“free” method in C is used to dynamically de-allocate the memory. The memory allocated
using functions malloc() and calloc() is not de-allocated on their own. Hence the free() method
is used, whenever the dynamic memory allocation takes place. It helps to reduce wastage of
memory by freeing it.

Syntax: free(ptr);

Difference between malloc() and calloc()

calloc() malloc()

calloc() initializes the allocated memory malloc() initializes the allocated memory
with 0 value. with garbage values.

Number of arguments is 2 Number of argument is 1

Syntax: Syntax:

(cast_type *)calloc(blocks , (cast_type *)malloc(Size_in_bytes);

size_of_block);

Program to represent Dynamic Memory Allocation(using calloc())

#include <stdio.h>
#include <stdlib.h>

int main()

int i, n;

int *element;

printf("Enter total number of elements: ");

scanf("%d", &n);

element = (int*) calloc(n,sizeof(int)); //returns a void pointer(which is type-casted to

int*) pointing to the first block of the allocated space

if(element == NULL) //If it fails to allocate enough space as specified, it returns a

NULL pointer.

printf("[Link] enough space available");

exit(0);

for(i=0;i<n;i++) //storing elements from the user in the allocated space

scanf("%d",element+i); //storing elements from the user in the allocated space

for(i=1;i<n;i++)

if(*element > *(element+i))

*element = *(element+i);

printf("Smallest element is %d",*element);

return 0;

Output:

Enter total number of elements: 5

42153

Smallest element is 1

Linked list:

Definition: A linked list is a sequence of data structures which are connected together
via links. Linked List is a sequence of links which contains items. Each link contains a
connection to another link. A linked list is a non-primitive type of data structure in which
each element is dynamically allocated and in which elements point to each other to
define a linear relationship. If each node in the list has only one link, it is called singly
linked list. If it has two links one containing the address of the next node and other link
containing the address of the previous node it is called doubly linked list. Linked list
require more memory compared to array because along with value it stores pointer to
next node.

Elements of linked list are called nodes where each node in the singly list has 2 fields
namely:

 info – This field is used to store the data or information to be manipulated.

 link – This field contains address of the next node.
Linked list contains the connection link to the first Link called First. Each Link carries
a data field(s) and a Link Field called next. Last Link carries a Link as null to mark the
end of the list.

Advantages of Linked Lists over Arrays

1. A linked list is a dynamic data structure therefore, the primary advantage of linked
lists over arrays is that linked lists can grow or shrink in size during the execution of a
program i.e. runtime but arrays is a static data structure therefore, the size remain
fixed. In arrays we would need to allocate all the storage in starting.

2. There is no need to specify how many number of nodes required so linked list does
not waste memory space. We can allocate and de-allocate memory space at runtime.

3. The most important advantage is that the linked lists provide flexibility is allowing
the items to be rearranged efficiently. In linked list it is easier to insert or delete items
by rearranging the pointers but in arrays insertion and deletion requires large
movement of data.

Disadvantages of Linked Lists over Arrays

1. A linked list will use more memory storage than arrays with the same number of
elements is used because each time linked list has more memory for an additional
linked field or next pointer field.

2. Arrays elements can be randomly accessed by giving the appropriate index, while
linked list elements cannot randomly accessed.

3. Binary search cannot be applied in a linked list.

4. A linked list takes more time in traversing of elements.

Operations on singly linked list:

The following operations are performed on a Single Linked List:

 Insertion
 Deletion
 Display

Insertion: In a single linked list, the insertion operation can be performed in three
ways. They are as follows:

1. Inserting at Beginning of the list

2. Inserting at End of the list

3. Inserting at Specific location in the list

How to define self-referential structure?

It can be defined as:

struct node //structure definition of node

int info;

struct node *link;

};

typedef struct node *NODE;

Here in the above structure we can see that keyword typedef the type “struct node *”
can also be written as NODE. So wherever we use struct node * can be replaced with
NODE.

NODE first; or struct node * first;

How to create empty list:

An empty list can be created by assigning NULL to a self-referential structure variable.

Eg: For example, consider the code

struct node

int info;

struct node *link;

};

typedef struct node *NODE;

NODE first; //first is self-referential structure variable

first=NULL; //empty list by name first is created here

An empty list identified by the variable first is pictorially represented as:

NULL

first

Create a node:

How to create a node?

We can use malloc () function to allocate memory explicitly as and when required and
exact amount of memory space needed during execution. This can be done by:
x=(data_type *) malloc(size);

After doing the allocation, the function returns the address of 1st byte of allocated
memory. Since the address is returned, the return type is a void pointer. If the
specified memory is not available, then there will be condition called overflow of
memory. In such case functions returns NULL. So it is users responsibility to check
whether there is a sufficient memory.

if(x==NULL)

printf(“Insufficient memory\n”);

exit(0);

If x is not null, it means a node is successfully created and we can return the node by
the statement return x;

C function to get a new node from the availability list:

NODE getnode()

NODE x;

x=(NODE ) malloc (sizeof(struct node)); //allocate memory space

if(x==NULL) //free nodes does not exist

printf(“Out of memory\n”); //allocation failed terminate the program

exit(0);

return x; //allocation successful

}

Create a node with the specified item:

Step 1: get a node:

A node which is identified by variable first with 2 fields: info and link fields can be
created using getnode() function:

first = getnode();

first info

first link

Step 2: Store the item:

The data item 10 can be stored in the info field using the following statement:

firstinfo=10;

After executing above statement, the data item 10 is stored in info field of first

Step 3: Store NULL character:

After creating the node, if we donot want link field to contain address of any other
node, we can store \0(NULL) in link field as:

firstlink=NULL;

So by using above 3 steps we can create a node with specified data item as shown in
this figure:

Delete a node:

A node which is no longer used or required can be deleted using free() function as:

free(variable);

For eg: when above statement is executed, the memory space allocated for the node,
is deallocated and returned to OS so that it can be used by some other program. The
memory deallocated after executing:

free(first);

Operation on singly linked list:

1) Insert a node at the front end: Let us consider a linked list with 4 nodes. Here,
pointer variable first contains address of the first node of the list as:
Now let us try to insert the item 50 at the front end of the above list.

Step 1: Create a node using getnode() function as:

temp=getnode()

The pictorial representation is:

Step 2: Copy the item 50 into info field of temp using:

tempinfo=item;

The pictorial representation is:

Step 3: Copy the address of the first node of the list stored in pointer variable first into
link field of temp using:

templink=first;
Step 4: Now, a node temp has been already inserted and we can observe from figure
that temp is the first node. Let us return the address of the first node using:

return temp;

C function to insert an item at the front end of list:

NODE insert_front(int item, NODE first)

NODE temp;

temp=getnode(); //obtain a node from available list

tempinfo=item; //insert an item into new node

templink=first; //insert new node at the front of list

return temp; //return the new first node

Create a linked list:

Now let us see how to create linked list? So I is very simple call insert_front()
function.

first=insert_front(item,first);

If first is NULL and item is 10, then above statement is executed, a linked list with
only one node is created as:
If the above statement is executed for 2nd time with item 20, a new node is inserted
at the front end and there by number of nodes in the list is 2:

If the above statement is executed for 3rd time with item 30, a new node is inserted at
the front end and there by number of nodes in the list is 3:

How to find address of last node in the list?

Consider the following singly list where the variable first contains the address of first
node of the list.

We need to find the address of the last node. So we have to start from the first node.
Instead of updating first, let us use another variable say current. The variable current
should contain the address of the first node. So this is done by writing statement:

cur=first;
cur=curlink;

After executing the above statement, current contains address of next node as:

cur=curlink

If we execute the instruction cur=curlink again, cur contains address of next node
as:

If we execute the instruction cur=curlink again, cur contains address of next node
as:
Here we can see current link is NULL then it denoted as it is last node of the list. If
cur contains address of first node, keep updating current as long as link field of
current is not NULL as:

cur=curlink;  while(curlink!=NULL)

cur=curlink;

Now variable first contains address of the 1st node, we can find address of last node
as:

cur=first; //find the address of last node of the list

while(curlink!=NULL)

cur=curlink;

How to find last node and last but one in the list:

Consider the following list: If current contains address of the 1st node of the list, what
is the previous node? The previous node does not exit and so we say previous is
NULL.

The code can be written as:

prev=NULL;
cur=first;

Now we have to update current to get address of the last node. So the code can be
written as:

while(curlink!=NULL)

cur=curlink;

Now before updating cur inside the loop using cur=curlink. Let us copy cur to prev.
The code can be modified as:

while(curlink!=NULL)

prev=cur;

cur=curlink;

So after the loop, the variable contains address of the last node and the variable
prev contains the address of the prev node. To find address of last node and last but
one node as:

prev=NULL;

cur=first;

while(curlink!=NULL)

prev=cur;

cur=curlink;

}
After above code is executed we get pictorial representation as this way:

Display singly linked list:

Case 1: List is empty: If the list is empty, it is not possible to display the contents of
the list. The code for this is:

if(first==NULL)

printf(“List is empty\n”);

return;

Case 2: List is exiting: Consider the linked list with 4 nodes where the variable first
contains address of the first node of the list:

Initialization: We have to use another variable cur to point to the beginning of the
list. So this can be done by just copying first to cur as:

cur=first;
Display:

Now display the info field of cur node and update cur as:

printf(“%d”,curinfo); //output=20

cur=curlink; //cur=1008

Now display info field of cur node and update cur as:

printf(“%d”,curinfo); //output=30

cur=curlink; //cur=1048

Now display info field of cur node and update cur as:

printf(“%d”,curinfo); //output=10

cur=curlink; //cur=1026
Now display info field of cur node and update cur as:

printf(“%d”,curinfo); //output=60

cur=curlink; //cur=NULL

Finally, current is NULL so no more nodes to display. So these statements are

repeatedly executed as long as cur is not NULL. Once cur is NULL, the displaying of
node is finished.

printf(“%d”,curinfo);  while(cur!=NULL)

cur=curlink; {

printf(“%d”,curinfo);

cur=curlink;

C function to display the contents of linked list:

void display(NODE first)

NODE cur;

if(first==NULL)

printf(“List is empty\n”);

return;
}

printf(“the contents of singly linked list\n”);

cur=first;

while(cur!=NULL)

printf(“%d”,curinfo);

cur=curlink;

Delete a node from the front end:

A node from the front end of list can be deleted by considering various cases

Case 1: List is empty: If the list is empty, it is not possible to delete a node from the
list. In such we have to display list is empty and return NULL.

if(first==NULL) //check for empty list

printf(“List is empty\n”);

return;

Case 2: List is exiting: Consider the list with 5 nodes where the variable first
contains address of the first node of the list.
We know the address of first node, now we need to know the address of the second
node of the list. Because after deleting the first node, the second node will be the first
node of the list. So these of steps we should follow when we delete a node.

Step 1: We have to use pointer variable temp and store the address of first node of
the list by the following statement:

temp=first;

Here temp and first points to first node

Step 2: Update the pointer temp so that variable temp contains the address of the
second node. So this can be achieved by the following statement:

temp=templink;

Now temp points to second node

Step 3: Here variable first points to first node of the list and temp points to the
second node of the list. Now display info field of the first node that have to be deleted
and deallocate the memory by using these statements:

printf(“item deleted=%d\n”,firstinfo);

free(first);
After executing the above statement, the node pointed by first is deleted and is
returned to OS.

Step 4: Once the first node is deleted, we can observe that node temp is the first
node. So, return temp as the first node to the calling function using the statement:

return temp;

C function to delete an item from front end of the list:

NODE delete_front(NODE first)

NODE temp;

if(first==NULL) //check for empty list

printf(“List is empty cannot delete\n”);

return NULL; //we can replace NULL with first also

temp=first; //retain the address of the node to be deleted

temp=templink; //obtain address of the second node

printf(“item deleted=%d\n”,firstinfo); //access the first node

free(first); //delete the front node

return temp; //return address of first node

Insert a node at rear end:

Step 1: First create a node using getnode() function then insert the item say 50
using the following statements:

Step 2: If the list is empty, the above node can be returned as the first node of the
list. So this can be done by following statement:

if(first==NULL)

return temp;

Step 3: If the list is existing, we have to insert temp at the end of the list.

To insert at the end, we have to find address of the last node. So the code to find the
address of last node can be written as:

cur=first;

while(curlink!=NULL)

cur=curlink;

}
Step 4: Insert a node at the end: By looking the above list, we can easily insert
temp at the end of current. So this can be done by copying temp to curlink as:

curlink=temp;

Step 5: We can observe from the above list that first contains address of the first
node of the list. So we return first.

return first;

C code to insert an item at rear end of the list:

NODE insert_rear(int item, NODE first)

NODE temp; //points to newly created node

NODE cur; //To hold the address of last node

temp=getnode(); //obtain a new node and copy the item

tempinfo=item;

templink=NULL;
if(first==NULL) //if list is empty return new node as the first node

return temp;

cur=first; //if list exists, obtain address of last node

while(curlink!=NULL)

cur=curlink;

curlink=temp; //insert a node at the end

return first; //return address of first node

Delete a node from rear end:

Case 1: List is empty: If the list is empty, it is not possible to delete the contents of
the list. In such case we display appropriate message and return. The code is as
follows:

if(first==NULL) //check for empty list

printf(“List is empty cannot delete\n”);

return NULL;

Case 2: List contains only 1 node: Consider s list with single node as:
Note: If link field of first contains NULL, it indicates that there is only one node.

If only one node is present, it can be deleted using free() function. Then we return
NULL indicating list is empty. So the code for this is:

if(firstlink==NULL)

printf(“Item to be deleted is %d\n”,firstinfo);

free(first); //delete and return to OS

return NULL; //return empty list

Case 3: List contains more than one node: Consider the list with 5 nodes as:

Step 1: To delete the last node we should know the address of last node and last but
one node. For this, we have to use pointer variables, current and previous. Initially,
current points to the first node and previous points to NULL. So this can be written
as:

prev=NULL;

cur=first;
Step 2: Now update current and previous so that current contains address of last
node and previous contains address of last but one node. This can be achieved by
following statements:

while(curlink!=NULL)

prev=cur;

cur=curlink;

After executing above loop, the variable current contains address of last node and
previous contains address of last but one node as:

Step 3: To delete the last node pointed to by current, the function free() is used.

printf(“Item deleted=%d\n”,curinfo); //item deleted=60

free(cur);

After executing above statements, the last node is deleted and the list is:
Step 4: Once the last node is deleted, the node pointed to by previous should be the
last node. This is achieved by just copying NULL to link field of previous as:

prevlink=NULL; //node pointed to by previous is the last node

After executing the above statements, the list can be shown as:

Step 5: Finally return address of first node

return first; //return address of first node

C function to delete a node from rear end of the list:

NODE delete_rear(NODE first)

NODE cur,prev;

if(first==NULL) //check for empty list

printf(“List is empty cannot delete\n”);

return first;

}
if(firstlink==NULL)

printf(“Item to be deleted is %d\n”,firstinfo);

free(first); //return to availability list

return NULL; //list is empty so return NULL

//Obtain address of the last node and just previous to that

prev=NULL;

cur=first;

while(curlink!=NULL)

prev=cur;

cur=curlink;

printf(“Item deleted=%d\n”,curinfo);

free(cur); //delete the last node

prevlink=NULL; //make last but one node as the last node

return first; //return address of first node

Write a C code for Searching in singly linked list:

#include<stdio.h>

#include<stdlib.h>

void create(int);
void search();

struct node

int data;

struct node *next;

};

struct node *head;

void main ()

int choice,item,loc;

do

printf("\[Link]\[Link]\[Link]\[Link] your choice?");

scanf("%d",&choice);

switch(choice)

case 1: printf("\nEnter the item\n");

scanf("%d",&item);

create(item);

break;

case 2:search();

case 3: exit(0);

break;
 default: printf("\nPlease enter valid choice\n");

}while(choice != 3);

void create(int item)

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

if(ptr == NULL)

printf("\nOVERFLOW\n");

else

ptr->data = item;

ptr->next = head;

head = ptr;

printf("\nNode inserted\n");

void search()

{
struct node *ptr;

int item,i=0,flag;

ptr = head;

if(ptr == NULL)

printf("\nEmpty List\n");

else

printf("\nEnter item which you want to search?\n");

scanf("%d",&item);

while (ptr!=NULL)

if(ptr->data == item)

printf("item found at location %d ",i+1);

flag=0;

else

flag=1;

i++;
 ptr = ptr -> next;

if(flag==1)

printf("Item not found\n");

Circular linked list:

If link field of the last node contains starting address of first node. Such a list is called
circular list. In general, a circular list is a variation of ordinary linked list in which link
field of the last node contains address of the first node. This list is primarily used in
structures that allow access to nodes in the middle of the list without starting from the
first node.

The pictorial representation of a circular list is:

Advantages of circular list:

a) Every node is accessible from a given node by traversing successively using the
link field.

b) To delete a node current, the address of the first node is not necessary. Search
for the predecessor of node current, can be initiated from current itself.
c) Certain operations on circular list such as concatenation and splitting of list etc will
be more efficient.

The following 2 conventions can be used:

Approach 1

A pointer variable first can be used to designate the starting point of the list. Using
this approach, to get the address to get the address of last node, the entire list has to
be traversed from the first node.

Approach 2

In the second technique, a pointer variable last can be used to designate the last
node and the node that follow last, can be designated as the first node of the list.
The pictorial representation of the circular list is:

From the figure we can see that the variable last contains address of last node.
Using link field of last node that is lastlink, we can get address of the first node.

A circular list can be used as a stack or a queue. To implement these data structure,
we require of the following functions:

Insert_front: To insert an element at the front end of the list

Insert_rear: To insert an element at the rear end of the list

delete_front: To delete an element at the front end of the list

delete_rear: To delete an element at the rear end of the list

display: To display the contents of the list.

Insert at front end:

Consider a list with 4 nodes. Here, pointer last contains address of the last node of
the list. Let us try to insert an item at the front end of list.

Step 1: To insert an item 50 at the front of the list, obtain a free node using malloc()
function with the help of macro MALLOC() and insert the item using the statement:

MALLOC(temp,1,struct node); or temp=getnode();

tempinfo=item;

Step 2: Copy the address of the first node(i.e. lastlink) into link field of newly
obtained node temp and the statement is:

if(last!=NULL)

templink=lastlink;

else //if last is NULL, make temp itself as the last node

temp=last;

Step 3: Make temp as the first node. Establish a link between the node temp and the
last node. This is achieved by copying the address of the node temp into link field of
node last. The code can be written as:

lastlink=temp;
Step 4: Finally, we return address of the last node using the statement:

return last;

C function to insert an item at the front end of the list:

NODE insert_front(int item, NODE last)

NODE temp;

MALLOC(temp,1,struct node); //create a new node to be inserted

tempinfo=item;

if(last==NULL) //make temp as the first node

last=temp;

else

templink=lastlink; //insert at front end

lastlink=temp; //link last node to first node

return last; //return the last node

Insert a node at rear node:

Let us consider a list with 4 nodes. Here, pointer last contains address of the last
node of the list. Let us insert an item 80 at the end of the list.

Step 1: Obtain a node using the function malloc() or getnode().

MALLOC(temp,1,struct node); or temp=getnode();

tempinfo=item;
Step 2: Copy the address of the first node (i.e. lastlink) into link field of newly
obtained node temp and the statement is:

if(last!=NULL)

templink=lastlink; //copy the address of first node into link field of temp

else //if last is NULL, make temp itself as the last node

temp=last;

Step 3: Establish a link between the newly created node temp and the node last.
This is achieved by copying the address of the node temp into link field of node last.
The code for this is:

lastlink=temp;

Step 4: The new node is made as the last node using:

return temp;

C function to insert an item at rear end of the list:

NODE insert_rear(int item, NODE last)

NODE temp;
MALLOC(temp,1,struct node); //create a new node to be inserted

tempinfo=item;

if(last==NULL) //make temp as the first node

last=temp;

else

templink=lastlink; //insert at rear end

lastlink=temp; //link last node to first node

return temp; //make the new node as the last node

Delete a node from the front end:

Let us consider as a list with 5 nodes. Here, pointer last contains address of the last
node of the list. Let us delete an item at the front end of the list.

Step 1: In case if list is empty we cannot delete it So in this situation we can write
code as:

If list is empty:

if(last==NULL)

printf(“list is empty\n”);

return NULL;
}

In case we are deleting only one node, the list will be empty and we have to return
NULL. The code can be written as:

If there is only one node:

if(lastlink==last) //in case there is only node in the list

printf(“item deleted=%d\n”,lastinfo); //delete a node

free(last);

return NULL; //return empty list

If there is more than one node:

first=lastlink; //obtain the address of the first node

Step 2: Make second node as first node. So this can be done by copying firstlink
to lastlink. The code can be written as:

lastlink= firstlink; //link the last node and new first node

Step 3: Now remove the first node by using free(). But before removing the node,
display appropriate message. The code can be written as:

printf(“the item deleted is %d\n”,firstinfo);

free(first); //delete the old first node

Now the node first is deleted. These steps have been designed by assuming the list
is already existing.

C function to delete an item from the front end:

NODE delete_front(NODE last)

{
NODE temp,first;

if(last==NULL) //check for empty list

printf(“List is empty\n”);

return NULL;

if(lastlink==last) //delete if only one node

printf(“the item deleted is %d\n”,lastinfo); //delete 50 element

free(last);

return NULL;

first=lastlink; //obtain node to be deleted

lastlink=firstlink; //store new first node in link of last

printf(“item deleted is %d\n”,firstinfo); //delete the old first node

free(first); //delete the old first node

return last; //return always address of last node

Delete a node from rear end:

Let us consider a list with 5 nodes. Here, pointer last contains address of the last
node of the list. Now let us delete an item at the rear end of the list.
Step 1:

In case if list is empty we cannot delete it So in this situation we can write code as:

If list is empty:

if(last==NULL)

printf(“list is empty\n”);

return NULL;

In case we are deleting only one node, the list will be empty and we have to return
NULL. The code can be written as:

If there is only one node:

if(lastlink==last) //in case there is only node in the list

printf(“item deleted=%d\n”,lastinfo); //delete a node

free(last);

return NULL; //return empty list

}
Obtain the address of the predecessor of the node to be deleted. So this can be
done by traversing from the first node till the link field of a node contains address of
the last node. The code can be written as:

List with more than one node:

prev=lastlink;

while(prevlink!=last) //find address of last but one node by updating prev as

long as prevlink is not last.

prev=prevlink;

Step 2: The first node and the last but one node (i.e. prev) are linked. So this can be
written as:

prevlink=lastlink;

Step 3: Remove the last node using free(). But before removing a node display
appropriate message. The code can be written as:

printf(“item deleted=%d\n”,lastinfo);

free(last);

Step 4: Return prev itself as the first node of the result using the statement:

return prev;

C function to delete an item from rear end:

NODE delete_rear(NODE last)

NODE prev;

if(last==NULL) //check if list is empty

{

printf(“list is empty\n”);

return NULL;

if(lastlink==last) //delete if only one node

printf(“the item deleted is %d\n”,lastinfo);

free(last);

return NULL;

prev=lastlink; //obtain address of previous node

while(prevlink!=last)

prev=prevlink;

prevlink=lastlink; //prev node is made the last node

printf(“the item deleted is %d\n”,lastinfo);

free(last); //delete the old last node

return prev; //return the new last node

C function to display the contents of circular queue:

void display(NODE last)

{
NODE temp;

if(last==NULL) //check for empty list

printf(“list is empty\n”);

return;

printf(“contents of the list are\n”); //display till we get last node

temp=lastlink; //get the address of first node

while(temp!=last) //traverse till the end

printf(“%d”,tempinfo);

temp=templink;

printf(“%d\n”,tempinfo); //display last node

}
 Unit 3

Linear Data Structures- Doubly Linked List

Doubly Linked list:

Double linked list is a sequence of elements in which every element has links to its previous
element and next element in the sequence. A doubly linked list is a linear collection of nodes
where each node is divided into 3 parts:

a) info – This is a field where the information has to be stored.

b) llink – This is a pointer field which contains address of the left node or previous node in the
last

c) rlink – This is a pointer field which contains address of the first node or next node in the list.

Pictorial representation of doubly linked list:

Using this list, it is possible to traverse the list in forward and backward directions. Such a list
where each node has 2 links is also called a two-way list.

Operations on Double Linked List:

Insertion:

Inserting a node at the front end:

Step 1: Create a node:

This can be done using getnode() function and copying item 5 as:

temp=getnode ();

tempinfo=item;

templink=temprlink=NULL;
Step 2: Insert into empty list:

If the list is empty, the above created node itself should be returned as the first node. The
code can be written as:

if(first==NULL) return temp;

Step 2: Inserting into existing list:

Now I will consider the following list to see how a node temp can be inserted at the front end:

To insert temp at the front end of the list, copy first into rlink of temp and copy temp into
llink of first node using this code:

temprlink=first;

firstllink=temp;

Step 3: Return the first node:

After modification, always we have to return the address of the first node. In the above list,
temp is the first node and it can be returned using the statement:

return temp;
C function to insert an item at the front end of the list:

NODE insert_front(int item, NODE first)

NODE temp;

temp=getnode (); //obtain a node from OS

tempinfo=item; //insert an item into new node

templink=temprlink=NULL;

if(first==NULL) return temp; //insert a node for the first time

temprlink=first; //insert at the beginning of existing list

firstllink=temp;

return temp; //return address of new first node

Inserting a node at the rear end

Step 1: Create a node:

This can be done using getnode() function and copying item 50 as:

temp=getnode ();

tempinfo=item;

templink=temprlink=NULL;

Step 2: Insert into empty list:

If the list is empty, the above created node itself should be returned as the first node. The
code can be written as:

if(first==NULL) return temp;

Step 2: Find the address of last node:

Consider the following list and see how node temp can be inserted at rear end:

Let the variable first always contain address of the first node. Let me use another variable
current pointing to first node. This can be done as:

cur=first;

Now, the pictorial representation of linked list is:

Now keep updating current to point to the next node as long as rlink field of current is not
NULL. This can be written as:

while(currlink!=NULL)

cur=currlink;

Now after executing the above while loop, the variable cur contains address of the last node
of the list as:
Step 3: Insert node at the end:

rlink of cur should contain address of temp. This can be done as:

currlink=temp;

llink of temp should contain address of cur. This can be done as:

templlink=cur;

After executing the above 2 statement as:

Step 4: Return address of first node:

This can be done using statement as:

return first;

C function to insert an item at the rear end of the list:

NODE insert_front(int item, NODE first)

NODE temp;

temp=getnode (); //obtain a node from OS

tempinfo=item; //insert an item into new node

templink=temprlink=NULL;
if(first==NULL) return temp; //insert a node for the first time

cur=first; //get the address of first node

while(currlink!=NULL) //find address of last node

cur=currlink;

currlink=temp; //insert the node at the end

templlink=cur;

return first; //return address of the first node

Deletion:

Deleting a node from the front end of the list:

Step 1: List is empty:

If the list is empty, it is not possible to delete a node from the list. In such case, we have to
display the message “list is empty” and return NULL. The code can be written as:

if(first==NULL)

printf((“list is empty\n”);

return NULL;

Step 2: Delete if there is only one node:

A list having one node can be written as:

if(firstrlink==NULL)
{

printf(“item deleted=%d\n”,firstinfo);

free(first);

return NULL;

When control comes out of the above if statement, it means that the list has more than one
node and the list can be pictorially represented as:

Step 3: Obtain the address of the second node:

The address of second node can be obtained using the statement as:

second=firstrlink;

Step 4: Make second node as first node:

It is achieved by copying NULL to left link of second node. It can be written as:

secondllink=NULL;

Now first node is isolated and the linked list can be shown as:
Step 5: Delete the front node:

It is achieved using free() function. The code can be written as:

printf(“item deleted=%d\n”,firstinfo);

free(first);

After executing the code, list can be pictorially represented as:

Step 6: Return address of the new first node:

Now the variable second contains address of new first node and it can be returned using the
statement:

return second;

C function to delete an item from the front end of the list:

NODE delete_front(NODE first)

NODE second;

if(first==NULL) //check for empty list

printf(“List is empty cannot deleted\n”);

return NULL; //we can replace NULL with first also

if(firstrlink==NULL) //delete if there is only one node

printf(“item deleted=%d\n”,firstinfo);

free(first);

return NULL;

second=firstrlink; //get the address of second node

secondllink=NULL; //make second node as first node

printf(“item deleted=%d\n”,firstinfo);

free(first); //delete the first node

return second;

Deleting a node from rear end:

Step 1: List is empty:

If the list is empty, it is not possible to delete a node from the list. In such case, we have to
display the message “list is empty” and return NULL. The code can be written as:

if(first==NULL)

printf((“list is empty\n”);

return NULL;

}
Step 2: Delete if there is only one node:

A list having one node can be written as:

if(firstrlink==NULL)

printf(“item deleted=%d\n”,firstinfo);

free(first);

return NULL;

When control comes out of the above if statement, it means that the list has more than one
node and the list can be pictorially represented as:

To delete last node, we should know the address of the last node and last but one node. We
will see this in the coming steps

Step 3: Obtain the address of the first node and its predecessor:

This can be done using two pointer variable: cur and prev. Initially, cur points to the first
node and previous points to \0(NULL). This can be achieved using statement:

prev=NULL;

cur=first;
Step 4: Find the address of last node and last but one node:

This can be done by updating current and previous till current contains address of the last
node and previous contains address of the last but one node. This can be achieved by using:

while(curlink!=NULL)

prev=cur;

cur=curlink;

After executing the above loop the variable current contains address of the last node and
previous contains address of last but one node as:

Step 5:

The last node pointed to by current can be deleted as:

printf(“item deleted=%d\n”,curinfo); //item deleted=40

free(cur);

Step 4:

Once the last node is deleted, the node pointed to by prev should be the last node. This can be
achieved by copying NULL to rlink field of prev as:
The code can be written as:

prevrlink=NULL; //node pointed to by prev is the last node

Step 5:

Finally return address of the first node

return first; //return address of the first node

C function to delete an item from rear end of the list:

NODE delete_rear(NODE first)

NODE cur, prev;

if(first==NULL) //check for empty list

printf((“list is empty\n”);

return NULL;

if(firstlink==NULL) //only one node is present and delete it

printf(“item deleted=%d\n”,firstinfo);

free(first); //return to availability list

return NULL; //list is empty so return NULL

//obtain the address of last node and just previous to that

prev=NULL;

cur=first;

while(curlink!=NULL)

prev=cur;

cur=curlink;

printf(“item deleted=%d\n”,curinfo); //item deleted=40

free(cur); //delete a last node

prevrlink=NULL; //node pointed to by prev is the last node

return first; //return address of the first node

Display doubly linked list:

The function that is used to display normal linked list can be used to display the contents of
doubly linked list. Only change is that link field should be replaced by rlink. The C function
is:

void display(NODE first)

NODE cur;

int count=0;

if(first==NULL) //check for empty list

printf((“list is empty\n”);

return;

printf(“the contents of singly linked list\n”);

cur=first; //holds address of first node

while(cur!=NULL) //as long as no end of list

printf(“%d”,curinfo);

count++;

cur=currlink; //point to next node

printf(“number of nodes=%d\n”,count);

Circular doubly linked list:

We have seen that the left link of the leftmost node and right link of rightmost node points to
NULL.

The 2 variation of doubly linked list are:

a) circular doubly linked list

b) circular doubly linked list with a header node

A circular linked list is a variation of doubly linked list in which every node in the list has 3
fields:

Info: This is a field where the information has to be stored.

llink: This is a pointer field which contains address of the left node or previous node in the
list.

rlink: This is a pointer field which contains address of the right node or next node in the list.

And the llink of first node contains address of the last node whereas rlink of the list node
contains address of the first node.
Now we will see the advantage of circular linked list:

a) As in normal doubly linked list, we can traverse the doubly linked circular list in both
directions.

b) In normal doubly linked list, given the address of the first node we have to traverse till the
end to get the address of the last node. The left link of the first node gives the address of the
last node.

Insert a node at the front end:

Step 1: Create a node: This can be done using getnode() function and copying item 5 as:

temp=getnode();

tempinfo=item;

templlink=temprlink=temp;

Step 2: Insert into empty list: If the list is empty, the above created node itself should be
returned as the first node.

if(first==NULL) return temp;

If the above condition fails, it means that is already existing. The new node temp which has
to be inserted at the front end and the existing list can be pictorially represented as:

Now node temp can be inserted at front end using following steps:

Step 3: Obtain the address of the last node: The last node of the list can be obtained using
llink of the first node. The code can be written as:

last=firstllink; //get address of last node

Now the linked list can be pictorially represented as:

Step 4: Link the new node created with first node: This can be done by copying first into
rlink of temp and copying temp into llink of first node as:

The code can be written as:

temprlink=first;

firstllink=temp;

Step 4: Make new node created as the first node: This can be done by copying temp to
rlink of last node and copying last node into llink of new first node (i.e. templlink)
lastrlink= temp;

templlink=last;

Step 5: Return the first node: After modifying the list, always we have to return the address
of the first node. In the above list, temp is the first node and it can be returned using the
statement:

return temp;

C function to insert an item at front end:

NODE insert_front(int item node, NODE first)

NODE temp, last;

temp=getnode();

tempinfo=item;

templlink=temprlink=temp;

if(first==NULL) return temp; //create the node first time

last=firstllink; //get address of last node

temprlink=first; //link the first node with new node

firstllink=temp;

lastrlink= temp; //link the last node with new node

templlink=last;

return temp;
}

Insert a node at rear end:

Step 1: Create a node: This can be done using getnode() function and copying item 5 as:

temp=getnode();

tempinfo=item;

templlink=temprlink=temp;

Step 2: Insert into empty list: If the list is empty, the above created node itself should be
returned as the first node as:

if(first==NULL) return temp; //create the node first time

If the above condition fails, it means that is already existing. The new node temp which has
to be inserted at the front end and the existing list can be pictorially represented as:

Now node temp can be inserted at rear end using following steps:

Step 3: Obtain the address of the last node: The last node of the list can be obtained using
llink of the first node. The code can be written as:
last=firstllink; //get address of last node

Now the linked list can be pictorially represented as:

Step 4: Link the new node created with first node: This can be done by copying temp into
rlink of last and copying last into llink of temp node as:

lastrlink=temp;

templlink=last;

Step 4: Make new node created as the last node: This can be done by copying temp to llink
of first node and copying first node into rlink of temp node(i.e. temprlink) as:

firstllink=temp;

temprlink=first;

Step 5: Return the first node: After modifying the list, always we have to return the address
of the first node. This can be done using statement:

return temp;
C function to insert an item at the rear end of the list:

NODE insert_rear(int item, NODE first)

NODE temp, last;

temp=getnode();

tempinfo=item;

templlink=temprlink=temp;

if(first==NULL) return temp; //insert the node for the first time

last=firstllink; //get address of last node

lastrlink=temp; //link the last node with new node

templlink=last;

firstllink=temp; //link the first node with new node

temprlink=first;

return temp;

Delete a node from front end:

Step 1: List is empty: If the list is empty, it is not possible to delete a node from the list. In
such case, we display the message “List is empty” and return NULL. The code can be written
as:

if(first==NULL)

printf(“List is empty\n”);

return NULL;

}
Step 2: Delete if there is only one node: A list having one node can be written as:

if(firstrlink==first)

printf(“item deleted=%d\n”,firstinfo);

free(first);

return NULL;

When control comes out of the above if-statement, it means that the list has more than one
node and the list can be pictorially represented as:
Step 3: Obtain the address of the second node and the last node: The rlink of first node
gives the second node and llink of first node gives the last node as:

second=firstrlink;

last=firstllink;

Step 4: Make second node as first node: It is achieved by copying last to left link of second
node and copying second to rlink of last node as:

secondllink=last;

lastrlink=second;

Now first node is isolated and linked list look like:

Step 5: Delete the front end: Front node can be deleted using free() function.

printf(“item deleted=%d\n”,firstinfo);

free(first);

Step 6: Return address of the new first node: The variable second now contains address of
the new first node and it can be returned using the statement:

return second;

C function to delete an item from the front end of the list:

NODE delete_front(NODE first)

NODE second, last;

if(first==NULL) //check for empty list

{
printf(“list is empty cannot delete\n”);

return NULL; //we can replace NULL with first also

if(firstrlink==first) //delete if there is only one node

printf(“item deleted=%d\n”,firstinfo);

free(first);

return NULL;

second=firstrlink; //obtain the address of second node

last=firstllink; //obtain the address of last node

secondllink=last; //make second node as new first node

lastrlink=second;

printf(“item deleted=%d\n”,firstinfo); //delete the old first node

free(first);

return second; //return second node as first node

Delete a node from rear end:

Step 1: List is empty: If the list is empty, it is not possible to delete a node from the list. In
such case, we display the message “List is empty” and return NULL. The code can be written
as:

if(first==NULL)

printf(“List is empty\n”);

return NULL;

}
Step 2: Delete if there is only one node: A list having one node can be written as:

if(firstrlink==first)

printf(“item deleted=%d\n”,firstinfo);

free(first);

return NULL;

When control comes out of the above if-statement, it means that the list has more than one
node and the list can be pictorially represented as:
Step 3: Obtain the address of the last node and its predessor: The llink of first node gives
the last node and llink of last gives its predessor as:

last=firstllink;

prev=lastllink;

Step 4: Make last but one node as last node: It is achieved by copying first to right link of
prev and copying prev to llink of first node (as dotted lines) as:

prevrlink=first;

firstllink=prev;
Step 5: Delete the last node: Last node can be deleted using free() function.

printf(“item deleted=%d\n”,lastinfo);

free(last);

Step 6: Return address of the first node: The variable first contains address of the first
node and it can be returned using the statement as:

return first;

C function to delete an item from rear end of the list:

NODE delete_rear(NODE first)

NODE last, prev;

if(first==NULL) //check for empty list

printf(“List is empty\n”);

return NULL;

if(firstrlink==first) //only one node is present and delete it

{
printf(“item deleted=%d\n”,firstinfo);

free(first); //return to the availability list

return NULL; //list is empty so return NULL

last=firstllink; //obtain address of the last node

prev=lastllink; //obtain address of last but one node

prevrlink=first; //adjust pointers such that new last node and first node are linked

firstllink=prev;

printf(“item deleted=%d\n”,lastinfo);

free(last); //delete the old last node

return first; //return address of the first node

Display the contents of linked list:

void display(NODE first)

NODE cur, last;

if(first==NULL)

printf(“List is empty\n”);

return NULL;

printf(“the contents of singly linked list\n”);

cur=first;

last=firstllink;

while(cur!=last)

printf(“%d”,curinfo);
cur=currlink;

printf(“%d”,curinfo);

Circular doubly linked list with header node:

This list is primarily used in structures that allow access to nodes in both directions. An
empty circular doubly linked list with a header node can be represented as in this figure
below where llink and rlink of a header node points to itself.

The main advantage of using doubly linked circular with a header node is that while
designing a function we need not consider any extreme cases. Assume that list is existing and
write a function to insert an item at the front end. The function works for all other cases (i.e.
even if list is empty or if list has only one node or more than one node).

Insert a node at front end:

Consider a list
Step 1: Create a node and copy the item to be inserted: This can be pictorially
represented as:

temp=getnode();

tempinfo=item;

Step 2: Get address of the first node: The right link of header node gives the address of the
first node. Copying rlink of head to first as:

first=headrlink; //get the address of the first node

Step 3: Insert at front end: The node temp has to be inserted between head and first as:
templlink=head; //insert temp before head

headrlink=temp;

temprlink=first; //insert temp before first

firstllink=temp;

Step 3: Return the header node: Using header node, any node can be accessed. So, always
we return the address of header node. This can be done using the statement:

return head;

C function to insert a node at the front end:

NODE insert_front(int item, NODE head)

NODE temp, first;

temp=getnode();

tempinfo=item;

first=headrlink; //get the address of the first node

templlink=head; //insert temp before head

headrlink=temp;

temprlink=first; //insert temp before first

firstllink=temp;

return head;

Insert a node at rear end:

Consider a list
Step 1: Create a node and copy the item to be inserted: This can be pictorially

represented as:

temp=getnode();

tempinfo=item;

Step 2: Get address of the last node: The left link of header node gives the

address of the last node. Copying llink of head to last we get the list as:

last=headllink; //get the address of the last node

Step 3: Insert at the rear end: The node temp has to be inserted after last as:

lastrlink=temp;

templlink=last;

Since temp is the last node, rlink of temp should contain address of header node and llink of
header node should contain the address of last node i.e. temp. This can be pictorially
represented as:
temprlink=head;

headllink=temp;

Step 4: Return the header node: Using the header node, any node can be accessed. So
always we return the address of header node. This can be done using statement.

return head;

C function to insert a node at rear end:

NODE insert_rear(int item, NODE head)

NODE temp, last;

temp=getnode();

tempinfo=item;

last=headllink; //get the address of the last node

lastrlink=temp; //insert temp at the end

templlink=last;

temprlink=head; //make temp as the last node

headllink=temp;

return head;

Delete a node from front end:

Step 1: List is empty: If the list is empty, it is not possible to delete a node from the list. In
such case, we have to display the message “List is empty” and return head.
if(headrlink==head)

printf(“list is empty\n”);

return head;

If the above condition fails, it means that list is existing. Consider the following list:

We can delete an element from the front end using following steps:

Step 2: Get the first node: The right link of head contains address of the first node and copy
it into first as:

first=headrlink;

Step 3: Get the second node: The right link of first contains address of the second node and
copy it into second node as:
second=firstrlink;

Step 4: Isolate the first node: This can be done by connecting head and second node as:

headrlink=second;

secondllink=head;

Step 5: Remove the first node: The first node can be removed as shown in this figure:

printf(“item deleted=%d\n”,firstinfo);

free(first);

Step 6: Return the header node: Using the header node, any node can be accessed. So
always we return the address of header node. This can be done using the statement as:

return head;

C function to delete a node from the front end:

NODE delete_front(NODE head)

NODE first, second;

if(headrlink==head) //check for empty list

{
printf(“list is empty\n”);

return head;

first=headrlink; //obtain address of first node

second=firstrlink; //obtain address of second node

headrlink=second; //link header node as with second node

secondllink=head;

printf(“item deleted=%d\n”,firstinfo);

free(first); //delete the first node

return head; //return the address of last node

Delete a node from rear node:

Step 1: List is empty: If the list is empty, it is not possible to delete a node from the list. In
such case, we have to display the message “List is empty” and return head.

if(headrlink==head)

printf(“list is empty\n”);

return head;

}
If the above condition fails, it means that list is existing. Consider the following list:

We can delete an element from the front end using following steps:

Step 2: Get the last node: The llink of head contains address of the last node and copy it into
last as:

last=headllink;

Step 3: Get the last but one node: The left of last contains address of the last but one node
and copy it into prev as shown in this figure:

prev=lastllink;

Step 4: Isolate the last node: This can be done by connecting head and prev node as:

headllink=prev;

prevrlink=head;
Step 5: Remove the last node: This node can be removed as:

printf(“item deleted=%d\n”,lastinfo);

free(last);

Step 6: Return the header node: Using the header node, any node can be accessed. So,
always we return the address of header node. This can be done using the statement:

return head;

C function to delete a node from the rear end:

NODE delete_rear(NODE head)

NODE last, prev;

if(headrlink==head) //check for empty list

printf(“list is empty\n”);

return head;

last=headllink; //obtain address of last node

prev=lastllink; //obtain address of last but one node

headllink=prev; //isolate the last node

prevrlink=head;

printf(“item deleted=%d\n”,lastinfo); //delete the last node

free(last);

return head; //return the address of the last node

}
Display the contents of circular doubly linked list with header node:

void display(NODE head)

NODE cur;

if(headrlink==head) //check for empty list

printf(“list is empty\n”);

return head;

printf(“contents of doubly linked list\n”);

cur=headrlinnk;

while(cur!=head)

printf(“%d\n”,curinfo);

cur=currlink;

Application of linked list:

a) Evaluation of polynomials

b) Addition of polynomials

c) Multilinked data structure (Eg: sparse matrix)

d) Arithmetic operation on long positive numbers

e) In symbol table construction (compiler design)

Linked list representation of stack: We know that stack is a special type of data structure
where elements are inserted at one end and elements are deleted from the same end. That is,
if an element is inserted at front end, an element has to be deleted from the front end. If an
element is inserted at rear end, an element has to be deleted from rear end. Thus stack can be
implemented using the following functions:

a) insert_front()

b) delete_front()

c) display()

OR

a) insert_rear()

b) delete_rear()

c) display()

Linked list representation of Queue: We know that queue is a special type of data structure
where elements are inserted at one end and elements are deleted at the other end. It is a FIFO
data structure that is if an element is inserted at front end, an element has to be deleted from
rear end. If an element is inserted at rear end, an element has to be deleted from the front end.
So the queue can be implemented using the function:

insert_front()

delete_rear()

display()

OR

insert_rear()

delete_front()

display()

Trees

Definition:

A tree is a set of finite set of one or more nodes that shows parent child relation such that:

a) There is a special node called the root node

b) The remaining node are partitioned into disjoint subsets T1, T2, T3, T4……Tn, n>=0

where T1, T2, T3, T4……Tn which are all children of root node are themselves trees called
subtrees.

Eg: Consider the following tree. Let us identify the root node and various subtrees:
  Here there are 8 nodes: A, B, C, D, E, F, G, H
 A is root here.
 We normally draw the trees with root at the top. The node B, C, D are children of
node A and hence there are 3 subtree identified by B, C and D.
 The node A is parent of B, C and D whereas D is the parent of G and H.

Basic terminologies:

a) Root node: A first node written at the top is root node. Root node does not have the
parent. Here the node 100 is the root node.

b) Child: The node obtained from parent node is called child. A parent node can have zero or
more child nodes. Eg:

 50 and 60 are children of 100

 80 and 40 are children of 60
 70 is child of 50
 35 and 30 are children of 80
c) Siblings: 2 or more node having the same parent are called siblings. Eg:
  50 and 60 are siblings since they have same parent 100.
 80 and 40 are siblings since they have same parent 60.
 35 and 30 are siblings since they have same parent 80.
d) Ancestors: The nodes obtained in the path from the specified node x while moving
upwards towards the root node are called ancestors. Eg:

 100 is the ancestor of 50 and 60

 60 is the ancestor of 35, 30, 80 and 40
 50 and 100 are the ancestors of 70
 60 and 100 are the ancestors of 80, 40, 35,30
 80, 60 and 100 are the ancestors of 35 and 30
e) Descendants: The node in the path below the parent are called descendants. In other
words, the nodes that are all reachable from a node x while moving downwards are all called
descendants of x. For eg:

 All the nodes below 100 are descendants of 100.

 All the nodes below 50 are descendants of 50 and so on.
f) Left descendants: The node that lie towards left subtree of node x are called left
descendants. Eg:

 50 and 70 are left descendant of 100

 80, 35 and 30 are the left descendant of 60
 35 and 80 are left descendant of 60
g) Right descendants: The node that lie towards right subtree of node x are called left
descendants. Eg:

 The right descendant of 100 are 60, 80, 40, 35 and 30

 The right descendant of 80 is 30
 The right descendant of 60 is 40
h) Left subtree: All the nodes that are all left descendant of a node x form the left subtree of
x. Eg:

 The left subtree of 100 are 50 and 70

 The left subtree of 60 are 80, 35 and 30
i) Right subtree: All the nodes that are all right descendant of a node x form the right subtree
of x. Eg:

 The right descendant of 100 are 60, 80, 40, 35 and 30

 The right descendant of 80 is 30
 The right descendant of 60 is 40
j) Parent: A node having left subtree or right subtree or both is said to be a parent node for
the left subtree and/or right subtree. Eg:
  The parent for 50 and 60 is 100.
 The parent for 70 is 50.
 The parent for 80 and 40 is 60.
 The parent for 35 and 30 is 80.
k) Degree: The number of subtrees of a node is called its degree. Eg:

 The node 100 has 2 subtrees. So degree of node 100 is 2.

 The node 50 has one subtree. So degree of node 50 is 1.
 The node 70 has no subtree. So degree of node 70 is 0.
l) Leaf: A node in a tree that has a degree of zero is called a leaf node. In other words, a node
with an empty left child and an empty right child is called leaf node. It is also called a
terminal node. Eg: 70, 35, 30 and 40 are the leaf nodes.

m) Internal nodes: The nodes except leaf node in a tree are called internal nodes. Eg: 100,
50, 60 and 80 are internal nodes.

n) External nodes: The NULL link of any node in a tree is an external node. Eg: rlink of 50,
rlink and llink of nodes 70, 35, 30 and 40 are all external nodes.

o) Level: The distance of a node from the root is called level of the node.

 The distance from root to itself is 0. So, level of root node is 0.

 The node 50 is at a distance of 1 node from root node. So its level is 1.
 The node 70 is at a distance of 2 nodes from root node. So its level is 2.
 The node 35 and 30 are at a distance of 3 nodes from the root node. So their levels are
3.
 The level of each node is known in example.
p) Height (depth): The height of the tree is defined as the maximum level of any leaf in the
tree. For eg: height of the tree is 4.

Representation of trees:

1) List representation: Now let us see how a tree is represented using lists.
  The root node comes first.
 It is immediate followed by a list of subtree of that node.
 It is recursively repeated for each subtree. Eg:

The above tree can be represented using list as:

We can see linked list representation that:

 Since there are 3 children for node A in the tree, there are 3 nodes to the right of A in
the list representation.
 A’s first child is B, 2nd child is C and 3rd child is D and they are shown using down
links in list representation.
 Since there are 2 children for node B in the tree, there are 2 nodes to the right of B in
the list representation.
 Since there is only 1child for C in the tree, there is only 1 node to the right of C in the
list representation.
 Since there are 3 children for node D in the tree, there are 3 nodes to the right of D in
the list representation.
2) Left-child Right-sibling representation:

Left-child Right-sibling representation of a given tree can be obtained as:

  The left pointer of a node in the tree will be the left child in this representation.
 The remaining children of node in the tree are inserted horizontally to the left child in
the representation. Eg: Consider this tree:

The left-child Right-sibling representation of a tree can be written as:

We can observe from above representation that:

 A’s left child is B in the tree. So A’s left child is B in the representation.
 A’s remaining children such as C and D in the tree are inserted horizontally to node B
in the representation.
 B’s left child is E in the tree. So, B’s left child is E in the representation.
 B’s remaining children such as F in the tree are inserted horizontally to node E in the
representation.
 Similarly, D’s left child is H in the tree. So, D’s left child is H in the representation.
 D’s remaining children such as I and J in the tree are inserted horizontally to H in the
representation.
Degree of a node: In a tree data structure, the total number of children of a node is called as
DEGREE of that Node. In simple words, the Degree of a node is total number of children it
has. The highest degree of a node among all the nodes in a tree is called as 'Degree of Tree'.
Eg: Degree of B is 3, A is 2 and of F is 0

Height: In a tree data structure, the total number of edges from leaf node to a particular node
in the longest path is called as HEIGHT of that Node. In a tree, height of the root node is said
to be height of the tree. In a tree, height of all leaf nodes is '0'.

Depth: In a tree data structure, the total number of edges from root node to a particular node
is called as DEPTH of that Node. In a tree, the total number of edges from root node to a leaf
node in the longest path is said to be Depth of the tree. In simple words, the highest depth of
any leaf node in a tree is said to be depth of that tree. In a tree, depth of the root node is '0'.

Why Tree?

Unlike Array and Linked List, which are linear data structures, tree is hierarchical (or non-
linear) data structure.

1) One reason to use trees might be because you want to store information that naturally forms
a hierarchy. For example, the file system on a computer: file system
2) If we organize keys in form of a tree

3) We can insert/delete keys in moderate time.

Advantages of Trees

Trees are so useful and frequently used, because they have some very serious advantages:

a) Trees reflect structural relationships in the data.

b) Trees are used to represent hierarchies.

c) Trees provide an efficient insertion and searching.

d) Trees are very flexible data, allowing to move subtrees around with minimum effort.

Properties of binary tree:

1) The maximum number of nodes on level i of a binary tree=2i for i>=0

The number of nodes at level 0=1=20

The number of nodes at level 1=1=21

The number of nodes at level 2=1=22

The number of nodes at level 3=1=23

……………………………………………………

The number of nodes at level i=2i

2) The maximum number of nodes in a binary tree of depth k=2k-1

3) The number of leaf node is equal to number of nodes of degree 2.

Types of binary tree:

a) Strictly binary tree

b) Full binary tree

c) Skewed binary tree

d) Complete binary tree

a) Strictly binary tree: A binary tree having 2i nodes in any given level i is called strictly
binary tree. Here, every node other than the leaf node has 2 children. A binary tree in which
every node has either two or zero number of children is called Strictly Binary Tree. Strictly
binary tree is also called as Full Binary Tree or Proper Binary Tree or 2-Tree.

Here the number of nodes at level 0 = 20= 1

Here the number of nodes at level 0 = 21= 2

Here the number of nodes at level 0 = 22= 4

b) Full binary tree: A Binary Tree is a full binary tree if every node has 0 or 2 children. The
following are the examples of a full binary tree. We can also say a full binary tree is a binary
tree in which all nodes except leaf nodes have two children.

In a Full Binary Tree, number of leaf nodes is the number of internal nodes plus 1

L=I+1

Where L = Number of leaf nodes, I = Number of internal nodes

c) Skewed tree: A skewed tree is a tree consists of only left subtree or only right subtree. A
tree with only left subtree is called left skewed binary tree and a tree with only right subtree is
called right skewed binary tree.

d) Complete binary tree: A complete binary tree is a binary tree in which every level, except
possibly the last level is completely filled. If the node in the last level are not completely filled,
then all the nodes in that level should be filled only from left to right. For example, all trees
shown below are complete binary trees.
The tree shown below is not complete binary tree since the node in the last level are not filled
from left to right. There is an empty left child for node 5 in figure d) and there is an empty right
child for node 5 in figure e). All the nodes should be as left as possible.

Binary tree representation:

a) Linked list representation (uses dynamic allocation technique)

In a linked list representation, a node in a tree has 3 fields:

a) Info – which contains the actual information

b) llink – which contains address of the left subtree

c) rlink – contains address of the right subtree.

So, a node can be represented using self-referential structure as:

struct node

int info;

struct node *llink;

struct node *rlink;

};

typedef struct node * NODE;

The pictorial representation of a typical node in a binary tree is:

The pictorial representation of above node can be written as:

A pointer variable root can be used to point to the root node always. If the tree is empty, the
pointer variable root points to NULL indicating the tree is empty. The pointer variable root
can be declared and initialized as:

NODE root=NULL;

Or

struct node * root=NULL;

Memory can be allocated or deallocated using the C function malloc() or calloc()

b) Array representation (uses static allocation technique): A tree can be represented using
an array, which is called sequential representation.
  Here in this figure the node is numbered sequentially from 0.
 The node with position 0 is considered as root node.
 If an index i is 0, it gives the position of the root node.
 Given the position of any other node I, 2i+1 gives the position of the left child and
2i+2 gives the position of the root child.
 If i is the position of the left child, i+1 gives the position of right child
 If i is the position of the right child, i-1 gives the position of the left child.
 Given the position of any node i, the parent position is given by (i-1)/2. If I is odd, it
points to the left child otherwise, it points to the right child.
A tree can be represented using arrays in 2 different methods as:

Method 1: In this, some of the location may be used and some may not be used. For this, flag
field like used is used to indicate whether a memory location is used to represent a node or
not. If flag field used is 0, the corresponding memory location is not used and indicates the
absence of node at that position.

Each node contains 2 fields:

a) info – where information is stored.

b) used indicates the presence or the absence of a node.

The structure declaration for this is:

#define MAX_SIZE 200

struct node

int info;

int used;

};

typedef struct node NODE;

An array a of type NODE can be used to store different items and the declaration for this is:

NODE a[MAX_SIZE];

Method 2: An alternate representation is that, instead of using a separate flag field used to
check the presence of node by initializing each location of the array to 0 indicating the node
as not used. Non zero value in the location indicates the presence of the node.

Operation on binary tree:

a) Insertion

b) Searching

c) Deletion

d) Traversal

a) Insertion
Eg used to insert:

b) Searching:
Eg used for search:
c) Delete:
d) Traversal: Traversing is a method of visiting each node of a tree exactly once in a
systematic order. During traversal, we may print the info field of each node visited.

Different traversal technique of a binary tree:

a) Preorder traversal

b) Postorder traversal

c) Inorder traversal

a) Preorder traversal: It is recursively defined as:

1) Process the root Node [N]

2) Traverse the Left subtree in Preorder [L]

3) Traverse the Right subtree in Preorder [R]

Eg: Traverse the following tree using Preorder traversal:

Function to traverse the tree in Preorder:

void preorder(NODE root)

{

if(root==NULL) return;

printf(“%d”, root🡪info); //visit node

preorder(root🡪llink); //visit left subtree in preorder

preorder(root🡪rlink); //visit right subtree in preorder

b) Postorder traversal: It is recursively defined as:

1) Traverse the Left subtree in Preorder [L]

2) Traverse the Right subtree in Preorder [R]

3) Process the root Node [N]

Eg: Traverse the following tree using postorder traversal:

Function to traverse the tree in Postorder:

void postorder(NODE root)

if(root==NULL) return;

postorder(root🡪llink); //visit left subtree in preorder

postorder(root🡪rlink); //visit right subtree in preorder

printf(“%d”, root🡪info); //visit node

c) Inorder traversal: It is recursively defined as:

1) Traverse the Left subtree in Preorder [L]

2) Process the root Node [N]

3) Traverse the Right subtree in Preorder [R]

Eg: Traverse the following tree using inorder traversal:

Function to traverse the tree in Inorder:

void inorder(NODE root)

if(root==NULL) return;

inorder (root🡪llink); //visit left subtree in preorder

printf(“%d”, root🡪info); //visit node

inorder (root🡪rlink); //visit right subtree in preorder

C function to print the tree in the tree form:

void display(NODE root, int level)

{

int i;

if(root==NULL) return;

display(root🡪rlink, level +1);

for(i=0;i<level;i++) printf(“ “);

printf(“%d\n”,root🡪info);

display(root🡪llink,level+1);

Eg 1: Given a binary tree. What is preorder, inorder and postorder traversal?

Preorder traversal: 100, 20, 10, 30, 200, 150, 300

Inorder traversal: 10, 20, 30, 100, 150, 200, 300

Postorder traversal: 10, 30, 20, 150, 300, 200, 100

Eg 2: The preorder traversal sequence of a binary search tree is: 30, 20, 10, 15, 25, 23, 39,
35, 42. What is the postorder traversal sequence of the same tree?

We draw a binary search tree using these traversal results.

The binary search tree so obtained is as shown:

Postorder Traversal: 15, 10, 23, 25, 20, 35, 42, 39, 30.

Binary search tree:

A binary search tree is a tree in which for each node say x in the tree, elements in the left
subtree are less than info (x) and elements in the right subtree are greater than info (x). Every
node in the tree should satisfy this condition, if left subtree or right subtree exists. A binary
search tree can be empty.

Eg for binary search tree:

Traversal of a binary search tree is same as binary tree.

Construct a Binary Search Tree (BST):

When elements are given in a sequence,

a) Always consider the first element as the root node.

b) Consider the given elements and insert them in the Binary Search Tree one by one.

Eg: Construct a Binary Search Tree (BST) for the following sequence of numbers:
50, 70, 60, 20, 90, 10, 40, 100
Insert 50:

Insert 70: As 70 > 50, so insert 70 to the right of 50.

Insert 60: As 60 > 50, so insert 60 to the right of 50. As 60 < 70, so insert 60 to the left of 70.

Insert 20: As 20 < 50, so insert 20 to the left of 50.

Insert 90: As 90 > 50, so insert 90 to the right of 50. As 90 > 70, so insert 90 to the right of
70.

Insert 10: As 10 < 50, so insert 10 to the left of 50. As 10 < 20, so insert 10 to the left of 20.

Insert 40: As 40 < 50, so insert 40 to the left of 50. As 40 > 20, so insert 40 to the right of 20.
Insert 100: As 100 > 50, so insert 100 to the right of 50. As 100 > 70, so insert 100 to the
right of 70. As 100 > 90, so insert 100 to the right of 90.

Eg 1: Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially

empty binary search tree. The binary search tree uses the usual ordering on natural numbers.
What is the inorder traversal sequence of the resultant tree?
Inorder Traversal: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Eg 2: The preorder traversal sequence of a binary search tree is: 30, 20, 10, 15, 25, 23, 39,
35, 42. What is the postorder traversal sequence of the same tree? Left, right, root

Postorder Traversal: 15, 10, 23, 25, 20, 35, 42, 39, 30

Other common operations on binary search tree:

a) Insertion

b) traversal

a) Insertion:
Step 1: The item read from the keyboard must be stored in a node. This is achieved using
malloc() function with the help of getnode() function.

temp=getnode();

tempinfo=item;

templlink=NULL;

temprlink=NULL;

Step 2: If tree does not exist, then return the above node itself as the root node.

if(root==NULL) return temp;

Step 3: If tree already exists, root will not be NULL. In such case, we have to insert the node
created in step 1 at the appropriate place. We k now that in BST, items towards left subtree of
a node x will be less than info (x) and the items in the right subtree are greater or equal to
info (x).

Consider BST. Let temp with info of 140 is the node to be inserted.

Now we have to find appropriate position to insert. Let us assume that the variable root always
points to the root node of the tree. Since search starts from the root, we use 2 pointers cur and
prev to find the appropriate position in the tree. The pointer variable prev always points to
parent of cur node. Initially cur points to root node and prev points to NULL as:

prev=NULL;

cur=root;

Now as long as the item is less than info (cur), keep updating pointer variable cur towards left
using the statement:
cur=curllink;

Otherwise update cur towards right using the statement:

cur=currlink;

Before updating cur towards left or right, save its address in prev so that the pointer variable
prev always points to the parent node of cur. Now, the code can be written as:

prev=cur;

if(item<curinfo)

cur=curllink;

else

cur=currlink;

Note that when we update cur towards left or right, it may become NULL. In such case, we
have found the appropriate position to insert and stop updating cur. So, the code can be
repeatedly executed as long as cur is not NULL.

while (cur! =NULL)

prev=cur;

if(item<curinfo)

cur=curllink;

else

cur=currlink;

Once cur points to NULL, insert the node temp towards left (prev) if item is less than info
(prev), otherwise insert towards right. This can be done using the statement:

if(item<previnfo)

prevllink=temp;

else

prevrlink=temp;

Finally, we return the address of the root node using the statement as:
return root;

To insert an item into a binary search tree (duplicate elements):

NODE insert(int item, NODE root)

NODE temp, cur, prev;

temp=getnode(); //create a node and copy appropriate data

tempinfo=item;

templlink=NULL;

temprlink=NULL;

if(root==NULL) return temp; //insert a node for the first time

prev=NULL; //find the position to insert

cur=root;

while(cur!=NULL)

prev=cur; //obtain parent position

if(item<curinfo);
cur=curllink; //obtain left child position

else

cur=currlink; //obtain right child position

if(item<previnfo) //if node to be inserted < parent

prevllink=temp; //insert towards left of the parent

else

prevrlink=temp; //else insert towards right of the parent

return root; //return the root of the tree

}
Note: In the above function, observe that if an item is less than the node, it is inserted towards
left. Otherwise, it is inserted towards right. So, duplicate items are also inserted towards right.
So, to avoid duplicate elements, we check whether the item is same as info of a node. If so,
donot insert. The code can be written as:

prev=cur;

if(item==curinfo)

printf(“Duplicate items not allowed\n”);

free(temp);

return root;

if(item<curinfo)

cur=curllink; //obtain left child position

else

cur=currlink; //obtain right child position

To insert an item into a binary search tree (No duplicate items):

NODE insert(int item, NODE root)

NODE temp, cur, prev;

temp=getnode(); //create a node and copy appropriate data

tempinfo=item;

templlink=NULL;

temprlink=NULL;

if(root==NULL) return temp; //insert a node for the first time

prev=NULL; //find the position to insert

cur=root;

while(cur!=NULL)
{

prev=cur; //obtain parent position

if(item==curinfo) //donot insert duplicate item

printf(“duplicate items not allowed\n”);

free(temp);

return root;

if(item<curinfo)

cur=curllink; //obtain left child position

else

cur=currlink; //obtain right child position

if(item<previnfo) //if node to be inserted < parent

prevllink=temp; //insert towards left of the parent

else

prevrlink=temp; //else insert towards right of the parent

return root; // return the root of the tree

Unit 4

Non Linear data structure – tree data structure 2

Expression tree:

A sequence of operators and operands that reduces to a single value is called an expression.

Now let us see what is an expression tree?

An expression tree is a binary tree that satisfy the following properties:

a) Any leaf is an operand.

b) The root and internal nodes are operators

c) The subtree represents sub expressions with root of the subtree as an operator.
Steps to make expression tree:

Now let us see how an infix expression can be written using expression tree?

Eg: 1) a+b

2) a+ b –c

Step 1:

Step 2:
Step 3:

3) a + b * c $ e ^ f

Step 1:

Step 2:
Step 3:

Step 4:

4) a $ b * c – d ^ e

Step 1:
Step 2:

Step 3:

Step 4:

5) ((a * b ^ c) – (d + e)) * (f ^ k – h)
Step 1:

Step 2:

Step 3:

Step 4:
Step 5:

Step 6:

Create a binary tree for the postfix expression:

Now let us see what is the procedure to obtain an expression tree from the postfix expression?
The procedure to be followed while creating an expression tree using postfix expression as:

a) Scan the symbol from the left to right.

b) Create a node for the scanned symbol.

c) If the symbol is an operand push the corresponding node onto the stack.
d) If the symbol is an operator, pop one node from the stack and attach to the right of the
corresponding node with an operator. The first popped node represents the right operand. Pop
one more node from the stack and attach to the left. Push the node corresponding to the
operator on to the stack.

e) Repeat through step 1 for each symbol in the postfix expression. Finally, when scanning of
all the symbol from the postfix expression is over, address of the root node of the expression
tree is on top of the stack.

Function to create an expression tree for the postfix expression:

NODE creat_tree(charpostfix[])

NODE temp, st[20];

int i, k;

char symbol;

for(i=k=0;(symbol=postfix[i]!= ‘\0’;i++)

temp=getnode(); //obtain a node for each operator

tempinfo=symbol;

templlink=temprlink=NULL;

if(isalnum(symbol))

st[k++]=temp; //push the operand node on to the stack

else

temprlink=st[--k]; //obtain 2nd operand from stack

templlink=st[--k]; //obtain 1st operand from stack

st[k++]=temp; //push operator node on to stack

return st[--k]; //Return the root of the expression tree

}
Evaluation of expression: Now let us see “How to evaluate the expression?” In the
expression trees, whenever an operator is encountered, evaluate the expression in the left
subtree and evaluate the expression in the right subtree and perform the operation.

The recursive definition to evaluate the expression represented by an expression tree is:

Eval(root)= Eval(rootllink op Eval(rootrlink) if rootinfo is operator

Rootinfo – ‘0’ if rootinfo is operand

Creation of a binary search tree and traversal techniques:

C program to create a tree and traverse the tree array representation:

#include<stdio.h>

#include<process.h>

# define MAX_SIZE 100

typedef int NODE;

/*function to insert an item*/

void insert(int item, NODE a[])

int i;

i=0; //root node

while(i<MAX_SIZE && a[i]!=0) //obtain position where to insert

if(item<a[i])

i=2*i+1; //move towards to left link

else

i=2*i+2; //move towards to right link

a[i]=item; //insert the item

}
void inorder(NODE a[], int i)

if(a[i]==0) return;

inorder(a,2*i+1); //traverse left subtree

printf(“%d”,a[i]); //visits the node

inorder(a,2*i+2); //traverse right subtree

void preorder(NODE a[], int i)

if(a[i]==0) return;

printf(“%d”,a[i]); //visits the node

preorder(a,2*i+1); //traverse left subtree

preorder(a,2*i+2); //traverse right subtree

void postorder(NODE a[], int i)

if(a[i]==0) return;

postorder(a,2*i+1); //traverse left subtree

postorder(a,2*i+2); //traverse right subtree

printf(“%d”,a[i]); //visits the node

void main()

NODE a[MAX_SIZE];

int item, choice, i;

for(i=0; i< MAX_SIZE; i++) a[i] =0;

for(;;)
{

printf(“1-insert, 2- inorder\n”);

printf(“3-preorder, 4- postorder\n”);

printf(“5-Exit\n”);

printf(“enter the choice\n”);

scanf(“%d”,&choice);

switch(choice)

case 1: printf(“enter the item to be inserted\n”);

scanf(“%d”,&temp);

insert(item,a);

break;

case 2: if(a[i]==0)

printf(“tree is empty\n”);

else

printf(“the inorder traversal is\n”);

inorder(a,0);

break;

default: exit(0);

}
}

Advantages and disadvantages:

The sequential representation is simple and it saves space if the tree is complete or almost
complete as there is no need to have fields such as left-link, right-link etc. If the tree is not
complete or not almost complete binary tree, too much space may be wasted. The index i used
to move downward while doing some operation should not exceed the array bound i.e.
MAX_SIZE. This is advantageous only when the number of items in the tree is known in
advance.

The linked representation is useful most of the time during repeated deletion or manipulations,
which can be easily done by adjusting the links and where the number of items in the tree is
unpredictable.

Expression tree:

Eg 1): a + (b * c) + d * (e + f)

2) (a+b)*c+7

3) ((5 + z) / -8) * (4 ^ 2)
4) (((2+3)*9)+7)

Threaded binary tree:

Now let us see “what are the disadvantages of binary trees?” The various disadvantages of the
binary tree are:

a) In a binary tree, more than 50% of link fields have \0 (null) values and more memory space
is wasted by storing \0 (null) values.

b) Traversing a tree with binary tree is time consuming. This is because, the traversal of a tree
either uses implicit stack (un case of recursive programs) or explicit stack (in case of iterative
programs). Whatever it is stack is must. Most of the time is spent in pushing and popping
activities during traversing.

c) Computations of predecessor and successor of given nodes is time consuming.

d) In binary tree, only downward movements are possible.

All these disadvantages can be overcome using threaded binary tree.

Definition of Threaded binary tree:

In a binary tree, more than 50% of link fields have \0 (null) values and more space is wasted.
By the presence of \0 (null) values. These link fields which contains \0 characters can be
replaced by address of some nodes in the tree which facilitate upward movement in the tree.
These extra links which contains address of some nodes (pointers) are called threads and the
tree is termed as threaded binary tree. A threaded binary tree is a binary tree which contains
threads (i.e. address of some nodes) which facilitate upward movement in the tree.

Types of threaded binary tree:

This is based on the traversal technique.

3 types of threaded binary tree:

a) In thread binary tree

b) Post-threaded binary tree

c) Pre-threaded binary tree

a) In thread binary tree: In a binary tree, if llink (left link) of any node contains \0 (null) and
if it is replaced by address of the inorder predecessor, then the resulting tree is called left-in
threaded binary tree. In a binary tree, if rlink (right link) of a node is NULL and if it is replaced
by address of inorder successor, the resulting tree is called right in- threaded binary tree. An
in-threaded binary tree or inorder threading of a binary tree is the once which is both left in-
threaded and right in-threaded.

Eg: Consider a binary tree with header node:

In the above binary tree, if the right link of a node is NULL and if it is replaced by the address
of the inorder successor as shown using dotted lines, then the tree is said to be right in threaded
binary tree.

How to implement right in-threaded binary tree in C language?

To implement a right in- threaded an extra field rthread is used. If rthread is 1 the corresponding
right link represents a thread and if rthread is 0 the right link represents an ordinary link
connecting the right subtree. Thus a node can be defined as:

struct node

int info;

struct node *llink; //pointer to the left subtree

struct node *rlink; //pointer to the right subtree

int rthread; //1 indicates the presence of a thread & 0 indicates absence of thread

};

typedef struct node * NODE;

In a binary tree, if the left field is NULL and it is replaced by the inorder predecessor, then
the tree is said to be left in-threaded binary tree. Here also an extra field lthread is used where
1 indicates the presence of a thread and 0 indicates ordinary link connecting the left subtree.

Left in-threaded binary tree:

In-thread binary tree (inorder threading of binary tree):

Thus a node can be defined as:

struct node

int info;

struct node *llink; //pointer to the left subtree

struct node *rlink; //pointer to the right subtree

int lthread; //1 indicates the presence of a thread and 0 indicates absence of a thread

};

typedef struct node * NODE;

An inorder threading of a binary tree or in-threaded binary tree is one which is left in-
threaded and right in-threaded. Here two extra fields lthread and rthread as:

struct node

int info;

struct node

int info;

struct node *llink; //pointer to the left subtree

struct node *rlink; //pointer to the right subtree

int lthread; //1 indicates a thread else ordinary link

int rthread;

};

Inorder successor for right in-thread:

Consider the right in-threaded binary tree. Given a node X, if rthread is 1, which indicates the
presence of thread, its rlink gives the address of the inorder successor. If rthread is 0, rlink
contains the address of the right subtree. Leftmost node in the right subtree is the inorder
successor.

Function to find inorder successor:

NODE inorder_successor(NODE x)

NODE temp;

temp=xrlink;

if(rthread==1) return temp;

while(templlink!=NULL) //obtain leftmost node in the right subtree

temp=templlink;

return temp;

b) What is pre-threaded binary tree:

In a binary tree, if llink (left link) of any node contains \0 (null) and if it is replaced by address
of the preorder predecessor, then the resulting tree is called left-pre threaded binary tree. In a
binary tree, if rlink (right link) of a node is NULL and if it is replaced by address of preorder
successor, the resulting tree is called right pre-threaded binary tree. A pre-threaded binary tree
or preorder threading of a binary tree is the once which is both left pre-threaded and pre-
threaded.

c) What is post-threaded binary tree:

In a binary tree, if llink (left link) of any node contains \0 (null) and if it is replaced by address
of the postorder predecessor, then the resulting tree is called left post-threaded binary tree. In
a binary tree, if rlink (right link) of a node is NULL and if it is replaced by address of postorder
successor, the resulting tree is called right post-threaded binary tree. A post-threaded binary
tree or postorder threading of a binary tree is the one which both left post-threaded and right
post-threaded.

B- tree:
The B-Trees are specialized m-way search tree. This can be widely used for disc access. A B-
tree of order m, can have maximum m-1 keys and m children. This can store large number of
elements in a single node. So the height is relatively small. This is one great advantage of B-
Trees.
A B-tree of order m is a multiway search tree of order m such that:
a) All leaves are on the bottom level.
b) All internal nodes (except the root node) have at least ceil (m / 2) (nonempty) children.
c) The root node can have as few as 2 children if it is an internal node, and can obviously
have no children if the root node is a leaf (that is, the whole tree consists only of the root
node).
d) Each leaf node must contain at least ceil (m / 2) - 1 keys.

Note that ceil(x) is the so-called ceiling function. It's value is the smallest integer that is greater
than or equal to x. Thus ceil (3) = 3, ceil (3.35) = 4, ceil(1.98) = 2, ceil(5.01) = 6, ceil(7) = 7,
etc.

Eg of B-Tree:
The following is an example of a B-tree of order 5. This means that (other than the root node)
all internal nodes have at least ceil (5 / 2) = ceil (2.5) = 3 children (and hence at least 2 keys).
Of course, the maximum number of children that a node can have is 5 (so that 4 is the maximum
number of keys). According to condition 4, each leaf node must contain at least 2 keys. In
practice B-trees usually have orders a lot bigger than 5.

Why B-tree
The need for B-tree arose with the rise in the need for lesser time in accessing the physical
storage media like a hard disk. The secondary storage devices are slower with a larger capacity.
There was a need for such types of data structures that minimize the disk accesses. Other data
structures such as a binary search tree, AVL tree, red-black tree, etc can store only one key in
one node. If you have to store a large number of keys, then the height of such trees becomes
very large and the access time increases. However, B-tree can store many keys in a single node
and can have multiple child nodes. This decreases the height significantly allowing faster disk
accesses.
Construct a B-tree for the following:
1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45 Construct a B-tree of order 5
The first four items go into the root:

To put the fifth item in the root would violate condition 5. Therefore, when 25 arrives, pick the
middle key to make a new root.

6, 14, 28 get added to the leaf nodes:

Adding 17 to the right leaf node would over-fill it, so we take the middle key, promote it (to
the root) and split the leaf.

7, 52, 16, 48 get added to the leaf nodes

 Add 68
Adding 68 causes us to split the right most leaf, promoting 48 to the root, and adding 3 causes
us to split the left most leaf, promoting 3 to the root; 26, 29, 53, 55 then go into the leaves.

Adding 45 causes a split of and promoting 28 to the root then

causes the root to split.

2) Example for m= 5
Def: B Tree of order 5 is an 5-way tree such that
1. All leaf nodes are at the same level.
2. All non-leaf nodes (except the root) have atmost 5 and at least (m/2 children) 2 children.
3. The number of keys is one less than the number of children for non-leaf nodes and atmost
(m-1) 4 and atleast (m/2) 2 for leaf nodes.
4. The root may have as few as 2 children unless the tree is the root alone.
Operations:
Searching:
Searching in B Trees is similar to that in Binary search tree. For example, if we search for an
item 49 in the following B Tree. The process will something like following:
1. Compare item 49 with root node 78. since 49 < 78 hence, move to its left sub-tree.
2. Since, 40<49<56, traverse right sub-tree of 40.
3. 49>45, move to right. Compare 49.
4. match found, return.
Searching in a B tree depends upon the height of the tree.

Inserting
Insertions are done at the leaf node level. The following algorithm needs to be followed in
order to insert an item into B Tree.
1. Traverse the B Tree in order to find the appropriate leaf node at which the node can
be inserted.
2. If the leaf node contains less than m-1 keys, then insert the element in the increasing
order.
3. Else, if the leaf node contains m-1 keys, then follow the following steps.
o Insert the new element in the increasing order of elements.
o Split the node into the two nodes at the median.
o Push the median element upto its parent node.
o If the parent node also contains m-1 number of keys, then split it too by
following the same steps.
Example:
1) Tree of minimum degree ‘t’ as 3 and a sequence of integers 10, 20, 30, 40, 50, 60, 70, 80 and
90 in an initially empty B-Tree.
Initially root is NULL. Let us first insert 10.

Let us now insert 20, 30, 40 and 50. They all will be inserted in root because the maximum
number of keys a node can accommodate is 2*t – 1 which is 5.
Let us now insert 60. Since root node is full, it will first split into two, then 60 will be inserted
into the appropriate child.

Let us now insert 70 and 80. These new keys will be inserted into the appropriate leaf without
any split.

Let us now insert 90. This insertion will cause a split. The middle key will go up to the parent.

Eg: 2) Insert the node 8 into the B Tree of order 5 shown in the following image.

8 will be inserted to the right of 5, therefore insert 8.

The node, now contain 5 keys which is greater than (5 -1 = 4) keys. Therefore, split the node
from the median i.e. 8 and push it up to its parent node shown as follows.
Deletion: Deletion is also performed at the leaf nodes. The node which is to be deleted can
either be a leaf node or an internal node. Following algorithm needs to be followed in order to
delete a node from a B tree.
1. Locate the leaf node.
2. If there are more than m/2 keys in the leaf node, then delete the desired key from the
node.
3. If the leaf node doesn't contain m/2 keys, then complete the keys by taking the
element from eight or left sibling.
o If the left sibling contains more than m/2 elements, then push its largest
element up to its parent and move the intervening element down to the node
where the key is deleted.
o If the right sibling contains more than m/2 elements, then push its smallest
element up to the parent and move intervening element down to the node
where the key is deleted.
4. If neither of the sibling contain more than m/2 elements, then create a new leaf node
by joining two leaf nodes and the intervening element of the parent node.
5. If parent is left with less than m/2 nodes then, apply the above process on the parent
too.
If the node which is to be deleted is an internal node, then replace the node with its in-order
successor or predecessor. Since, successor or predecessor will always be on the leaf node
hence, the process will be similar as the node is being deleted from the leaf node.

Eg 1: Delete the node 53 from the B Tree of order 5 shown in the following figure.

53 is present in the right child of element 49. Delete it.

Now, 57 is the only element which is left in the node, the minimum number of elements that
must be present in a B tree of order 5, is 2. it is less than that, the elements in its left and right
sub-tree are also not sufficient therefore, merge it with the left sibling and intervening element
of parent i.e. 49.
The final B tree is shown as follows.
Application of B tree
B tree is used to index the data and provides fast access to the actual data stored on the disks
since, the access to value stored in a large database that is stored on a disk is a very time
consuming process.

B+ Tree: B+ Tree is an extension of B Tree which allows efficient insertion, deletion and
search operations. In B Tree, Keys and records both can be stored in the internal as well as
leaf nodes. Whereas, in B+ tree, records (data) can only be stored on the leaf nodes while
internal nodes can only store the key values. The leaf nodes of a B+ tree are linked together
in the form of a singly linked lists to make the search queries more efficient.

B+ Tree are used to store the large amount of data which cannot be stored in the main memory.
Due to the fact that, size of main memory is always limited, the internal nodes (keys to access
records) of the B+ tree are stored in the main memory whereas, leaf nodes are stored in the
secondary memory. The internal nodes of B+ tree are often called index nodes.

A B+ tree of order 3 as:

Advantages of B+ Tree
1. Records can be fetched in equal number of disk accesses.
2. Height of the tree remains balanced and less as compare to B tree.
3. We can access the data stored in a B+ tree sequentially as well as directly.
4. Keys are used for indexing.
5. Faster search queries as the data is stored only on the leaf nodes.

B Tree VS B+ Tree
Insertion in B+ Tree:

Step 1: Insert the new node as a leaf node

Step 2: If the leaf doesn't have required space, split the node and copy the middle node to the
next index node.

Step 3: If the index node doesn't have required space, split the node and copy the middle
element to the next index page.

Example: Insert the value 195 into the B+ tree of order 5 shown in the following figure.

195 will be inserted in the right sub-tree of 120 after 190. Insert it at the desired position.

The node contains greater than the maximum number of elements i.e. 4, therefore split it and
place the median node up to the parent.

Now, the index node contains 6 children and 5 keys which violates the B+ tree properties,
therefore we need to split it, shown as follows.
Deletion in B+ Tree

Step 1: Delete the key and data from the leaves.

Step 2: if the leaf node contains less than minimum number of elements, merge down the
node with its sibling and delete the key in between them.

Step 3: if the index node contains less than minimum number of elements, merge the node
with the sibling and move down the key in between them.

Example: Delete the key 200 from the B+ Tree shown in the following figure.

200 is present in the right sub-tree of 190, after 195. delete it.

Merge the two nodes by using 195, 190, 154 and 129.

Now, element 120 is the single element present in the node which is violating the B+ Tree
properties. Therefore, we need to merge it by using 60, 78, 108 and 120.
Now, the height of B+ tree will be decreased by 1.
 Properties of a B+ Tree
1. All leaves are at the same level.
2. The root has at least two children.
3. Each node except root can have a maximum of m children and at least m/2 children.
4. Each node can contain a maximum of m - 1 keys and a minimum of ⌈m/2⌉ - 1 keys.

B+ Tree Applications
 Multilevel Indexing
 Faster operations on the tree (insertion, deletion, search)
 Database indexing
Construct B+ tree:
The elements to be inserted are 5,15, 25, 35, 45. Order 3

Insert 5

Insert 15

Insert 25

Insert 35

Insert 45
Searching on a B+ Tree
Some of the steps to be followed to search for data in a B+ Tree of order m. Let the data to be
searched be k.
1. Start from the root node. Compare k with the keys at the root node [k1, k2, k3, ......km - 1].
2. If k < k1, go to the left child of the root node.
3. Else if k ==k1, compare k2. If k < k2, k lies between k1 and k2. So, search in the left child
of k2.
4. If k > k2, go for k3, k4......km-1 as in steps 2 and 3.
5. Repeat the above steps until a leaf node is reached.
6. If k exists in the leaf node, return true else return false.
Searching Example on a B+ Tree
Search k = 45 on the following B+ tree.

1. Compare k with the root node.

k is not found at the root

2. Since k > 25, go to the right child

Go to right of the root

3. Compare k with 35. Since k > 30, compare k with 45

k not found

4. Since k ≥ 45, so go to the right child

5. k is found.

Insertion in B+ Tree:

Step 1: Insert the new node as a leaf node

Step 2: If the leaf doesn't have required space, split the node and copy the middle node to the
next index node.

Step 3: If the index node doesn't have required space, split the node and copy the middle
element to the next index page.
Example: Insert the value 195 into the B+ tree of order 5 shown in the following figure.

195 will be inserted in the right sub-tree of 120 after 190. Insert it at the desired position.

The node contains greater than the maximum number of elements i.e. 4, therefore split it and
place the median node up to the parent.

Now, the index node contains 6 children and 5 keys which violates the B+ tree properties,
therefore we need to split it, shown as follows.

Deletion in B+ Tree

Step 1: Delete the key and data from the leaves.

Step 2: if the leaf node contains less than minimum number of elements, merge down the
node with its sibling and delete the key in between them.

Step 3: if the index node contains less than minimum number of elements, merge the node
with the sibling and move down the key in between them.
Example: Delete the key 200 from the B+ Tree shown in the following figure.

200 is present in the right sub-tree of 190, after 195. delete it.
Merge the two nodes by using 195, 190, 154 and 129.

Now, element 120 is the single element present in the node which is violating the B+ Tree
properties. Therefore, we need to merge it by using 60, 78, 108 and 120.
Now, the height of B+ tree will be decreased by 1.

AVL tree:
AVL tree is a height-balanced binary search tree. That means, an AVL tree is also a binary
search tree but it is a balanced tree. A binary tree is said to be balanced if, the difference
between the heights of left and right subtrees of every node in the tree is either -1, 0 or +1. In
other words, a binary tree is said to be balanced if the height of left and right children of every
node differ by either -1, 0 or +1. In an AVL tree, every node maintains an extra information
known as balance factor. The AVL tree was introduced in the year 1962 by G.M. Adelson-
Velsky and E.M. Landis.

An AVL tree is defined as:

An AVL tree is a balanced binary search tree. In an AVL tree, balance factor of every node is
either -1, 0 or +1

Balance factor of a node is the difference between the heights of the left and right subtrees of
that node. The balance factor of a node is calculated either height of left subtree - height of
right subtree (OR) height of right subtree - height of left subtree.

Balance factor = height of LeftSubtree – height of RightSubtree

Example of AVL Tree:

The above tree is a binary search tree and every node is satisfying balance factor condition. So
this tree is said to be an AVL tree.

Every AVL Tree is a binary search tree but every Binary Search Tree need not be AVL
tree

AVL Tree Rotations

In AVL tree, after performing operations like insertion and deletion we need to check the
balance factor of every node in the tree. If every node satisfies the balance factor condition,
then we conclude the operation otherwise we must make it balanced. Whenever the tree
becomes imbalanced due to any operation we use rotation operations to make the tree balanced.
Rotation operations are used to make the tree balanced.
Rotation is the process of moving nodes either to left or to right to make the tree balanced.

Why AVL Tree?

Let us consider the 2 scenarios that are given below. Both have the same elements arranged in
2 different ways.

When we consider case (a) - the Unbalanced Binary Search Tree:

  If we want to locate 10, it will require 2 tests. That is checking whether the first node
is 10 and then checking whether the second node is 10.
 If we want to locate 50, it requires 6 tests checking each node until you find 50
 Hence, the maximum search effort for this tree data structure is equal to the number of
elements in the tree, otherwise called as Order of n, or simply represented as O(n).
 Thus performance in the worst case scenario, is closer to the sequential search
algorithms such as List.
 In order to make searches faster, we need to balance the unbalanced Binary Search tree
(BST).

Now consider the case (b) - AVL tree:

 If we want to locate a value which is far from the root, say 8, we start by comparing
with the root value 28.
 Since 8 < 28, then we next search the left subtree node and compare 8 with 10.
 Since 8 < 10, then we search the left subtree node 8.
 Since 8 is found, this search needs only 3 tests.
 So the maximum search effort for this tree is O(log n).
 When we compare these 2 samples, we see that even in the worst case scenario, search
effort was reduced from 6 to 3.

Single Left Rotation (LL Rotation)

In LL Rotation, every node moves one position to left from the current position.
Single Right Rotation (RR Rotation)
In RR Rotation, every node moves one position to right from the current position. To
understand RR Rotation, let us consider the following insertion operation in AVL Tree.

Left Right Rotation (LR Rotation)

The LR Rotation is a sequence of single left rotation followed by a single right rotation. In LR
Rotation, at first, every node moves one position to the left and one position to right from the
current position. To understand LR Rotation, let us consider the following insertion operation
in AVL Tree.

Right Left Rotation (RL Rotation)

The RL Rotation is sequence of single right rotation followed by single left rotation. In RL
Rotation, at first every node moves one position to right and one position to left from the current
position. To understand RL Rotation, let us consider the following insertion operation in AVL
Tree.

Rotations:
RL rotation:
 Note:
 AVL trees are self-balancing binary search trees.
 In AVL trees, balancing factor of each node is either 0 or 1 or -1

To insert an element in the AVL tree, follow the following steps:

 Insert the element in the AVL tree in the same way the insertion is performed in BST.
 After insertion, check the balance factor of each node of the resulting tree.

Now following 2 cases are possible:

Case 1:
 After the insertion, the balance factor of each node is either 0 or 1 or -1.
 In this case, the tree is considered to be balanced.
 Conclude the operation.
 Insert the next element if any.

Case 2:
 After the insertion, the balance factor of at least one node is not 0 or 1 or -1.
 In this case, the tree is considered to be imbalanced.
 Perform the suitable rotation to balance the tree.
 After the tree is balanced, insert the next element if any.

Rule 1:
After inserting an element in the existing AVL tree,
 Balance factor of only those nodes will be affected that lies on the path from the newly
inserted node to the root node.

Rule 2:
 To check whether the AVL tree is still balanced or not after the insertion,
 There is no need to check the balance factor of every node.
 Check the balance factor of only those nodes that lies on the path from the newly
inserted node to the root node.

Rule 3: After inserting an element in the AVL tree,

 If tree becomes imbalanced, then there exists one particular node in the tree by
balancing which the entire tree becomes balanced automatically.
 To re balance the tree, balance that particular node.

To find that particular node,

 Traverse the path from the newly inserted node to the root node.
 Check the balance factor of each node that is encountered while traversing the path.
  The first encountered imbalanced node will be the node that needs to be balanced.

To balance that node,

 Count three nodes in the direction of leaf node.
 Then, use the concept of AVL tree rotations to re balance the tree.

Construct AVL Tree for the following sequence of numbers:

50, 20, 60, 10, 8, 15, 32, 46, 11, 48
Step-01: Insert 50

Step 2: Insert 20
As 20 < 50, so insert 20 in 50’s left sub tree.

Step 3: Insert 60
 As 60 > 50, so insert 60 in 50’s right sub tree.

Step-04: Insert 10
 As 10 < 50, so insert 10 in 50’s left sub tree.
 As 10 < 20, so insert 10 in 20’s left sub tree.
 Step-05: Insert 8
 As 8 < 50, so insert 8 in 50’s left sub tree.
 As 8 < 20, so insert 8 in 20’s left sub tree.
 As 8 < 10, so insert 8 in 10’s left sub tree.

To balance the tree,

 Find the first imbalanced node on the path from the newly inserted node (node 8) to the
root node.
 The first imbalanced node is node 20.
 Now, count three nodes from node 20 in the direction of leaf node.
 Then, use AVL tree rotation to balance the tree.
 Step-06: Insert 15
 As 15 < 50, so insert 15 in 50’s left sub tree.
 As 15 > 10, so insert 15 in 10’s right sub tree.
 As 15 < 20, so insert 15 in 20’s left sub tree.

To balance the tree,

 Find the first imbalanced node on the path from the newly inserted node (node 15) to the
root node.
 The first imbalanced node is node 50.
 Now, count three nodes from node 50 in the direction of leaf node.
 Then, use AVL tree rotation to balance the tree.
 Step 7: Insert 32
 As 32 > 20, so insert 32 in 20’s right sub tree.
 As 32 < 50, so insert 32 in 50’s left sub tree.

Step-08: Insert 46
 As 46 > 20, so insert 46 in 20’s right sub tree.
 As 46 < 50, so insert 46 in 50’s left sub tree.
 As 46 > 32, so insert 46 in 32’s right sub tree.
 Step 9: Insert 11
 As 11 < 20, so insert 11 in 20’s left sub tree.
 As 11 > 10, so insert 11 in 10’s right sub tree.
 As 11 < 15, so insert 11 in 15’s left sub tree.

Step 10: Insert 48

 As 48 > 20, so insert 48 in 20’s right sub tree.
 As 48 < 50, so insert 48 in 50’s left sub tree.
 As 48 > 32, so insert 48 in 32’s right sub tree.
 As 48 > 46, so insert 48 in 46’s right sub tree.
 To balance the tree,
 Find the first imbalanced node on the path from the newly inserted node (node 48) to the
root node.
 The first imbalanced node is node 32.
 Now, count three nodes from node 32 in the direction of leaf node.
 Then, use AVL tree rotation to balance the tree.
Operations on an AVL Tree

a) Search

b) Insertion

c) Deletion

Search Operation in AVL Tree:

Step 1 - Read the search element from the user.

Step 2 - Compare the search element with the value of root node in the tree.

Step 3 - If both are matched, then display "Given node is found!!!" and terminate the function

Step 4 - If both are not matched, then check whether search element is smaller or larger than
that node value.

Step 5 - If search element is smaller, then continue the search process in left subtree.

Step 6 - If search element is larger, then continue the search process in right subtree.

Step 7 - Repeat the same until we find the exact element or until the search element is
compared with the leaf node.

Step 8 - If we reach to the node having the value equal to the search value, then display
"Element is found" and terminate the function.

Step 9 - If we reach to the leaf node and if it is also not matched with the search element, then
display "Element is not found" and terminate the function.
Insertion Operation in AVL Tree:

Step 1 - Insert the new element into the tree using Binary Search Tree insertion logic.

Step 2 - After insertion, check the Balance Factor of every node.

Step 3 - If the Balance Factor of every node is 0 or 1 or -1 then go for next operation.

Step 4 - If the Balance Factor of any node is other than 0 or 1 or -1 then that tree is said to be
imbalanced. In this case, perform suitable Rotation to make it balanced and go for next
operation.

Eg: Construct an AVL Tree by inserting numbers from 1 to 8.

Deletion Operation in AVL Tree:
The deletion operation in AVL Tree is similar to deletion operation in BST. But after every
deletion operation, we need to check with the Balance Factor condition. If the tree is balanced
after deletion go for next operation otherwise perform suitable rotation to make the tree
Balanced.

Eg: Let's delete key sequence [6,5,4] from the below AVL tree and see how the height
balance is maintained throughout.

Delete key 6:

Delete key 5:

Delete key 4:
At this point, there is a height imbalance at node 3 with the left -left case. We do
a right rotation at node 3.
Data structures Unit 5

Nonlinear Data Structures- Graphs

Graph Terminologies

Graph: - A graph is data structure that consists of following two components.

 A finite set of vertices also called as nodes.
 A finite set of ordered pair of the form (u, v) called as edge.
(or)
A graph G=(V, E) is a collection of two sets
V and E, where V Finite number of vertices

E Finite number of Edges,

Edge is a pair (v, w),
where v, w ∈ V.
A walk is an alternating sequence of vertices and connecting edges.

A walk can end on the same vertex on which it began or on a different vertex. A walk can
travel over any edge and any vertex any number of times.

A path is a walk that does not include any vertex twice, except that its first vertex might be
the same as its last.

Two paths from U and V

A trail is a walk that does not pass over the same edge twice. A trail might visit the same
vertex twice, but only if it comes and goes from a different edge each time.

A Trail from U and V

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 1

Data structures Unit 5

A cycle is a path that begins and ends on the same vertex.

A circuit is a trail that begins and ends on the same vertex.

Connected Graph and Disconnected Graph

A graph is said to be connected if there is a path between every pair of vertex. From every
vertex to any other vertex, there should be some path to traverse. That is called the
connectivity of a graph. A graph that is not connected is said to be disconnected.

Example 1: In the following graph, it is possible to travel from one vertex to any other vertex.
For example, one can traverse from vertex ‘a’ to vertex ‘e’ using the path ‘a-b-e

Example 2
In the following example, traversing from vertex ‘a’ to vertex ‘f’ is not possible because
there is no path between them directly or indirectly. Hence it is a disconnected graph.

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 2

Data structures Unit 5

It is easy to see that a disconnected graph consists of two or more connected graphs. Each of
these connected sub graphs is called a component. Figure 2.7 shows a disconnected graph
with two components

A disconnected graph with two components

Euler Graphs

Euler path – a (possibly cyclic) path that crosses each edge exactly once

Euler circuit - an Euler path that starts and ends on the same node

Euler circuit

 A connected graph has an Euler circuit if and only if each of its vertices is of even
degree ›
 At every vertex, need one edge to get in and one edge to get out (or one to get out and
one to get back in)
 A connected graph has an Euler path but not an Euler circuit if and only if it has
exactly two vertices of odd degree
 the first and last vertices are distinct
 remember that an Euler circuit is also an Euler path

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 3

Data structures Unit 5

Hamiltonian Circuits

Euler circuit › A cycle that goes through each edge exactly once

Hamiltonian circuit › A cycle that goes through each vertex exactly once

For example, a Hamiltonian Cycle in the following graph is {0, 1, 2, 4, 3, 0}. There are more
Hamiltonian Cycles in the graph like {0, 3, 4, 2, 1, 0}

(0)--(1)--(2)
| /\ |
| / \ |
|/ \|
(3)-------(4)

And the following graph doesn’t contain any Hamiltonian Cycle.

(0)--(1)--(2)
| /\ |
| / \ |
|/ \|
(3) (4)

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 4

Data structures Unit 5

Directed Graph:

In representing of graph there is a

directions are shown on the edges
then that graph is called Directed
graph.

That is,
A graph G=(V, E) is a directed graph ,Edge is a
pair (v, w), where v, w ∈ V, and the
pair is ordered. Means vertex ‘w’ is
adjacent to v.

Directed graph is also called digraph.

Undirected Graph:
In graph vertices are not ordered is
called undirected graph. Means in
which (graph) there is no direction
(arrow head) on any line (edge).

A graph G=(V, E) is a directed graph ,Edge is a pair

(v, w), where v, w ∈ V, and the pair is
not ordered. Means vertex ‘w’ is
adjacent to ‘v’, and vertex ‘v’ is
adjacent to ‘w’

Representation of Graphs

The following two are the most commonly used representations of a graph.
1. Adjacency Matrix

2. Adjacency List

Adjacency Matrix

An Adjacency Matrix A[V][V] is a 2D array of size V × V where V is the number of vertices

in a undirected graph. If there is an edge between Vx to Vy then the value of A[Vx][Vy]=1
and A[Vy][Vx]=1, otherwise the value will be zero. And for a directed graph, if there is an
edge between Vx to Vy, then the value of A[Vx][Vy]=1, otherwise the value will be zero.

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 5

Data structures Unit 5

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 6

Data structures Unit 5

Adjacency List

In the adjacency list, an array (A[V]) of linked lists is used to represent the,graph G with V
number of vertices. An entry A[Vx] represents the linked list of vertices adjacent to the Vx-th
vertex. The adjacency list of the undirected graph is as shown in the figure below −

Which graph representation is best?

The graph representation to be used depends on the following factors:
 Nature of the problem
 Algorithm used for solving
 Type of the input
 Number of vertices and edges

Which graph representation is best?

If the graph is sparse (having few edges) , adjacency list can be used which uses less space
If the graph is dense, adjacency matrix has to be used.

Weighted Graph
Edge may be weight to show that there is a cost to go from one vertex to another.

Example: In graph of roads (edges) that connect one city to another (vertices), the weight on
the edge might represent the distance between the two cities (vertices)

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 7

Data structures Unit 5

Weighted Graph Adjacency matrix representation

Graph Traversals

The process of visiting each node of a graph systematically in some order is called
graph traversal.
1. Breadth First Search
2. Depth First Search

Breadth First Search

Breadth first search is a graph traversal algorithm that starts traversing the graph from root
node and explores all the neighbouring nodes.

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 8

Data structures Unit 5

Then, it selects the nearest node and explore all the unexplored nodes. The algorithm follows
the same process for each of the nearest node until it finds the goal.

Traverse the graph using BFS

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 9

Data structures Unit 5

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 10

Data structures Unit 5

Traverse the following graph using BFS

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 11

Data structures Unit 5

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 12

Data structures Unit 5

DFS Traversal is : Considering 0 as the starting vertex 0,1,2,3,4

Traverse the graph using BFS

BFS Traversal is as follows

a,b,c,d,e,f,g

BFS Algorithm

create a queue Q

mark v as visited and put v into Q

while Q is non-empty

remove the front element of Q

mark and enqueue all (unvisited)

neighbours of u

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 13

Data structures Unit 5

Depth First Search

Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses stack.

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 14

Data structures Unit 5

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 15

Data structures Unit 5

We use the following steps to implement DFS traversal…

Step 1 - Define a Stack of size total number of vertices in the graph.

Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push it on to the
Stack.

Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at the top of
stack and push it on to the stack.

Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex which is at the
top of the stack.

Step 5 - When there is no new vertex to visit then use back tracking and pop one vertex from
the stack.

Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.

Step 7 - When stack becomes Empty, then produce final spanning tree by removing unused
edges from the graph

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 16

Data structures Unit 5

Traverse the following graph using DFS

Consider Starting Vertex as A

Insert A on to Stack
Output: A

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 17

Data structures Unit 5

Operations on Graph

1. Insertion and Deletion of Edges

2. Insertion and Deletion of Vertices

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 18

Data structures Unit 5

Prathyakshini, ISE Dept, NMAMIT,Nitte Page 19