||Jai Sri Gurudev ||

BGSKH Education Trust (R.) – A unit of Sri Adichunchanagiri Shikshana Trust(R.)

BGS College of Engineering and Technology (BGSCET)

Mahalakshmipuram, West of Chord Road, Bengaluru-560086
(Approved by AICTE, New Delhi and Affiliated to VTU, Belagavi)
___________________________________________________________________

DATA STRCTURE AND

APPLICATIONS
Notes

For Third Semester B.E [VTU/CBCS, 2023-2024 Syllabus]

Subject Code: B C S 3 0 4
Structures

The variables that are used to store the data are called members of the structure or fields
of the structure. In the above structure, roll_no, name and fees are members of the
structure.

Ex: struct {
char name[10];
int age;
1
 float salary;
} Person;
The above example creates a structure and variable name is Person and that has three fields:
name = a name that is a characterarray
age = an integer value representing the age of the person
salary = a float value representing the salary of the individual

Assign values to fields

To assign values to the fields, use . (dot) as the structure member operator. This operator is
used to select a particular member of the structure

Ex: strcpy(Person.name,“james”);
Person.age =10;
Person.salary = 35000;

Type-Defined Structure
The structure definition associated with keyword typedef is called Type-Defined Structure.
Syntax 1: typedef struct
{
data_type member 1;
data_type member 2;
………………………
………………………
data_type member n;
}Type_name
Where,
• typedef is the keyword used at the beginning of the definition and by using typedef
user defined data type can beobtained.
• struct is the keyword which tells structure is defined to the complier
• The members are declare with their data_type
• Type_name is not a variable, it is user defined data_type.

2
 Structure Operation
The various operations can be performed on structures and structure members.

1. Structure Equality Check:

Here, the equality or inequality check of two structure variable of same type or dissimilar type
is not allowed
typedef struct{
char name[10];
int age;
float salary;
}humanBeing;
humanBeing person1, person2;

if (person1 = = person2) is invalid.

The valid function is shown below
#define FALSE 0
#define TRUE 1
3
 if (humansEqual(person1,person2))
printf("The two human beings are the same\n");
else
printf("The two human beings are not the same\n");

int humansEqual(humanBeing person1, humanBeing person2)

{ /* return TRUE if person1 and person2 are the same human being otherwise
return FALSE */
if (strcmp(person1.name, person2.name))
return FALSE;
if (person1.age != person2.age)
return FALSE;
if (person1.salary != person2.salary)
return FALSE;
return TRUE;
}
Program: Function to check equality of structures
2. Assignment operation on Structure variables:
person1 = person2
The above statement means that the value of every field of the structure of person 2 is
assigned as the value of the corresponding field of person 1, but this is invalid statement.

Valid Statements is given below:

strcpy(person1.name, person2.name);
person1.age = person2.age;
person1.salary = person2.salary;
Structure within a structure:
There is possibility to embed a structure within a structure. There are 2 ways to embed
structure.

1. The structures are defined separately and a variable of structure type is declared inside the
definition of another structure. The accessing of the variable of a structure type that are nested
inside another structure in the same way as accessing other member of that structure

4
Example: The following example shows two structures, where both the structure are defined
separately.
typedef struct {
int month;
int day;
int year;
}date;

typedef struct {
char name[10];
int age;
float salary;
date dob;

} humanBeing;
humanBeing person1;

A person born on February 11, 1944, would have the values for the date struct set as:
person1.dob.month = 2;
person1.dob.day = 11;
person1.dob.year = 1944;

5
SELF-REFERENTIAL STRUCTURES
A self-referential structure is one in which one or more of its components is a pointer to itself. Self-
referential structures usually require dynamic storage management routines (malloc and free) to
explicitly obtain and release memory.

Consider as an example:
typedef struct {
char data;
struct list *link ;
} list;

Each instance of the structure list will have two components data and link.
• Data: is a single character,
• Link: link is a pointer to a list structure. The value of link is either
the address inmemory of an instance of list or the null pointer.

Consider these statements, which create three structures and

assign values to their respective fields
List item1, item2, item3;
item1.data=’a’;
item1.data=’b’;
item1.data=’c’;
item1.link= item2.link= item3.link=NULL;
 Structures item1, item2 and item3 each contain the data item a, b, and c respectively, and the null
pointer. These structures can be attached together by replacing the null link field in item 2 with
one that points to item 3 and by replacing the null link field in item 1 with one that points to item
2.

item1.link = &item2;
item2.1ink = &item3;

Union Declaration:
A union declaration is similar to a structure, but the fields of a union must share their memoryspace. This
means that only one field of the union is "active" at any given time.

union{
char name;
int age;
float salary;
}u;

The major difference between a union and a structure is that unlike structure members which are
stored in separate memory locations, all the members of union must share the same memory space.
This means that only one field of the union is "active" at any given time.
Example:
#include <stdio.h>
union job {
char name[32];
float salary;
int worker_no;
}u;

int main( ){
printf("Enter name:\n");
scanf("%s", &u.name);
printf("Enter salary: \n");
scanf("%f", &u.salary);
printf("Displaying\n Name :%s\n",u.name);
printf("Salary: %.1f",u.salary);
return 0;
}
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
 Question Bank
Subject: Data Structure and Applications Class: AIDS
Subject code: BCS304 Faculty: Mrs. Jyothi R

Course Outcomes
CO 1. Explain different data structures and their applications.
CO 2. Apply Arrays, Stacks and Queue data structures to solve the given problems.
CO 3. Use the concept of linked list in problem solving.
CO 4. Develop solutions using trees and graphs to model the real-world problem.
CO 5. Explain the advanced Data Structures concepts such as Hashing Techniques and Optimal
Binary Search Trees
MODULE 1

Sl. Questions CO
No.
Topic: Introduction
1. Define Data structures. Classify the data structures with examples. And explain CO1
the operations of Data structures

Topic: Pointers
2 Define Pointers and Pointer Variable. How to declare and initialize pointers in C, CO1
explain with examples,
3 Can we have multiple pointers to a Variable? How pointers can be dangerous CO1
Topic: Dynamic Memory Allocation
4
Explain four dynamic memory allocation functions with S ynt ax a nd CO1
examples
Topic: Arrays
5 What is array? Give Abstract data type (ADT) for array. How array are CO2
declarations and implemented in C
6 Write a basic C program to demonstrate the basic operations of Array CO2
7 Write a C program to read and display two dimensional array by using Dynamic CO2
memory allocation
Topic: Structures and Unions
8 What is structure? Explain various operations that can be performed on structures. CO1

9 How does a structure differ from a union? Explain with example. CO1
10 How to declare user defined datatype using structures with an example CO1
program.
11 What is self-referential structures? Explain with example. CO1
Topic: Polynomials
 12 What is a polynomial? Apply ADT to represent two polynomials and write a CO1
function to add the polynomials.
13 Write addition of polynomial using arrays of structures. CO1
A(x)= 3x23 + 3x4 + 4x2 + 15.
B(x)= x5 + 20x3+ 2.
Solve by explaining all 3 cases.
Topic: Sparse Matrix

14 CO1
Define sparse matrix. E x p l a i n i t s representation with its ADT.
15 CO1
Write a function to read a sparse matrix and transpose a sparse matrix. Explain with
example.
Topic:
Strings
16 CO1
Define strings. Explain any four string handling functions supported by ‘C’ with
syntax and example
17 CO1
Write the ADT of strings
18 CO1
Define pattern Matching. Write the Knuth Morris Pratt pattern matching algorithm
and apply same pattern ‘abcdabcy’ in the text: ‘abcxabcdabxabcdabcdabcy’
19 CO1
Write a function to insert a string into another string at position ‘i’ and explain with
example.
20 CO1
Explain nfind string matching algorithm and find a pattern “aab” in the string
“ababbbaabaa”.
Topic:
Stacks
21 CO2
Give Abstract datatype(ADT) of Stack
22 CO2
Define Stack. Explain the different operations that can be performed on stack with
suitable ‘C’ functions and explain
23 CO2
Convert the following infix expression into postfix expression using stack 1. A + (
B*C-(D/E^F)*G)*H
2. ( ( H * ( ( ( ( A + ( ( B + C ) * D ) ) * F ) * G ) * E ) ) + J )
3. A * ( B + D ) / E – F * ( G + H / K )
24 CO2
Write an algorithm to evaluate a postfix expression. Trace the algorithm for the
expression showing the stack contents
6 5 1 – 4 * 2 3 ^ / +.
546+*493/+*
 Question Bank
Subject: Data Structure and Applications Class: AIDS
Subject code: BCS304 Faculty: Mrs. Jyothi R

Course Outcomes
CO 1. Explain different data structures and their applications.
CO 2. Apply Arrays, Stacks and Queue data structures to solve the given problems.
CO 3. Use the concept of linked list in problem solving.
CO 4. Develop solutions using trees and graphs to model the real-world problem.
CO 5. Explain the advanced Data Structures concepts such as Hashing Techniques and Optimal
Binary Search Trees
MODULE 2

Sl. Questions CO
No.
Topic: Queues, Circular Queues, Using Dynamic Arrays, Multiple Stacks and queues
1. Define Queue. Write QINSERT, QDELETE and QDISPLAY procedures for CO2
queues using arrays
2 Develop a C function to implement insertion, deletion and display operations of CO2
circular queue
3 Explain the ADT of Queue with its functions CO2
4 Implement circular queue using dynamic arrays CO2

5 Write C program to demonstrate multiple stacks and queues CO2

Topic: Singly Linked, Lists and Chains, Representing Chains in C, Linked Stacks and
Queues, Polynomials
6 Differentiate between array and Linked list CO3

7 Develop a C functions to implement using Single linked list CO3

1)Insert and Delete node from front
2) Insert and Delete node from rear end
3)Display/ printing the contents
8 Develop a C program to implement all Stack operations using Linked list CO3
9 Develop a C program to implement all Queue operations using Linked list CO3
10 Write C function to add two polynomials using Single linked list CO3

11 Write C function to add two polynomials using Circular linked list CO3
C program for Sparse Matrix Representation using Linked list

#include<stdio.h>
#include<stdlib.h>
#define R 4
#define C 5

// Node to represent row - list

struct row_list
{
int row_number;
struct row_list *link_down;
struct value_list *link_right;
};

// Node to represent triples

struct value_list
{
int column_index;
int value;
struct value_list *next;
};

// Function to create node for non - zero elements

void create_value_node(int data, int j, struct row_list **z)
{
struct value_list *temp, *d;

// Create new node dynamically

temp = (struct value_list*)malloc(sizeof(struct value_list));
temp->column_index = j+1;
temp->value = data;
temp->next = NULL;

// Connect with row list

if ((*z)->link_right==NULL)
(*z)->link_right = temp;
else
{
// d points to data list node
d = (*z)->link_right;
while(d->next != NULL)
d = d->next;
d->next = temp;
}
}
// Function to create row list
void create_row_list(struct row_list **start, int row,
int column, int Sparse_Matrix[R][C])
{
// For every row, node is created
for (int i = 0; i < row; i++)
{
struct row_list *z, *r;

// Create new node dynamically

z = (struct row_list*)malloc(sizeof(struct row_list));
z->row_number = i+1;
z->link_down = NULL;
z->link_right = NULL;
if (i==0)
*start = z;
else
{
r = *start;
while (r->link_down != NULL)
r = r->link_down;
r->link_down = z;
}

// Firstly node for row is created,

// and then traversing is done in that row
for (int j = 0; j < 5; j++)
{
if (Sparse_Matrix[i][j] != 0)
{
create_value_node(Sparse_Matrix[i][j], j, &z);
}
}
}
}

//Function display data of LIL

void print_LIL(struct row_list *start)
{
struct row_list *r;
struct value_list *z;
r = start;

// Traversing row list

while (r != NULL)
{
if (r->link_right != NULL)
{
 printf("row=%d \n", r->row_number);
z = r->link_right;

// Traversing data list

while (z != NULL)
{
printf("column=%d value=%d \n",
z->column_index, z->value);
z = z->next;
}
}
r = r->link_down;
}
}

//Driver of the program

int main()
{
// Assume 4x5 sparse matrix
int Sparse_Matrix[R][C] =
{
{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }
};

// Start with the empty List of lists

struct row_list* start = NULL;

//Function creating List of Lists

create_row_list(&start, R, C, Sparse_Matrix);

// Display data of List of lists

print_LIL(start);
return 0;
}
 Menu Driven Program in C to implement all the operations
of Doubly linked list

#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
struct node *next;
int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void insertion_specified();
void deletion_beginning();
void deletion_last();
void deletion_specified();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n========================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random locatio
n\n4.Delete from Beginning\n 5.Delete from last\n6.Delete the node after the giv
en data\n7.Search\n8.Show\n9.Exit\n");
 printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1: insertion_beginning(); break;
case 2: insertion_last(); break;
case 3: insertion_specified(); break;
case 4: deletion_beginning(); break;
case 5: deletion_last(); break;
case 6: deletion_specified(); break;
case 7: search(); break;
case 8: display(); break;
case 9: exit(0); break;
default: printf("Please enter valid choice..");
}
}
}
void insertion_beginning()
{
struct node *ptr;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter Item value");
scanf("%d",&item);
 if(head==NULL)
{
ptr->next = NULL;
ptr->prev=NULL;
ptr->data=item;
head=ptr;
}
else
{
ptr->data=item;
ptr->prev=NULL;
ptr->next = head;
head->prev=ptr;
head=ptr;
}
printf("\nNode inserted\n");
}
}
void insertion_last()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
 printf("\nEnter value");
scanf("%d",&item);
ptr->data=item;
if(head == NULL)
{
ptr->next = NULL;
ptr->prev = NULL;
head = ptr;
}
else
{
temp = head;
while(temp->next!=NULL)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
ptr->next = NULL;
}
}
printf("\nnode inserted\n");
}
void insertion_specified()
{
struct node *ptr,*temp;
int item,loc,i;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
 printf("\n OVERFLOW");
}
else
{
temp=head;
printf("Enter the location");
scanf("%d",&loc);
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\n There are less than %d elements", loc);
return;
}
}
printf("Enter value");
scanf("%d",&item);
ptr->data = item;
ptr->next = temp->next;
ptr -> prev = temp;
temp->next = ptr;
temp->next->prev=ptr;
printf("\nnode inserted\n");
}
}
void deletion_beginning()
{
struct node *ptr;
if(head == NULL)
 {
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
head = head -> next;
head -> prev = NULL;
free(ptr);
printf("\nnode deleted\n");
}
}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
 }
else
{
ptr = head;
if(ptr->next != NULL)
{
ptr = ptr -> next;
}
ptr -> prev -> next = NULL;
free(ptr);
printf("\nnode deleted\n");
}
}
void deletion_specified()
{
struct node *ptr, *temp;
int val;
printf("\n Enter the data after which the node is to be deleted : ");
scanf("%d", &val);
ptr = head;
while(ptr -> data != val)
ptr = ptr -> next;
if(ptr -> next == NULL)
{
printf("\nCan't delete\n");
}
else if(ptr -> next -> next == NULL)
{
ptr ->next = NULL;
}
 else
{
temp = ptr -> next;
ptr -> next = temp -> next;
temp -> next -> prev = ptr;
free(temp);
printf("\nnode deleted\n");
}
}
void display()
{
struct node *ptr;
printf("\n printing values...\n");
ptr = head;
while(ptr != NULL)
{
printf("%d\n",ptr->data);
ptr=ptr->next;
}
}
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("\nitem found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("\nItem not found\n");
}
}
}
 C program to implement all the operations on Circular
Doubly linked list

include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
struct node *next;
int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void deletion_beginning();
void deletion_last();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===========================================
====\n");
printf("\n1.Insert in Beginning\n2.Insert at last\n3.Delete from Beginning\n4.
Delete from last\n5.Search\n6.Show\n7.Exit\n");
printf("\nEnter your choice?\n");
 scanf("\n%d",&choice);
switch(choice)
{
case 1: insertion_beginning(); break;
case 2: insertion_last(); break;
case 3: deletion_beginning(); break;
case 4: deletion_last(); break;
case 5: search(); break;
case 6: display(); break;
case 7: exit(0); break;
default: printf("Please enter valid choice..");
}
}
}
void insertion_beginning()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter Item value");
scanf("%d",&item);
ptr->data=item;
if(head==NULL)
{
 head = ptr;
ptr -> next = head;
ptr -> prev = head;
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;
ptr -> prev = temp;
head -> prev = ptr;
ptr -> next = head;
head = ptr;
}
printf("\nNode inserted\n");
}
}
void insertion_last()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
 {
printf("\nEnter value");
scanf("%d",&item);
ptr->data=item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
ptr -> prev = head;
}
else
{
temp = head;
while(temp->next !=head)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
head -> prev = ptr;
ptr -> next = head;
}
}
printf("\nnode inserted\n");
}

void deletion_beginning()
{
struct node *temp;
if(head == NULL)
 {
printf("\n UNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = head -> next;
head -> next -> prev = temp;
free(head);
head = temp -> next;
}
}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == head)
 {
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
if(ptr->next != head)
{
ptr = ptr -> next;
}
ptr -> prev -> next = head;
head -> prev = ptr -> prev;
free(ptr);
printf("\nnode deleted\n");
}
}

void display()
{
struct node *ptr;
ptr=head;
if(head == NULL)
{
printf("\nnothing to print");
}
else
{
printf("\n printing values ... \n");
 while(ptr -> next != head)
{

printf("%d\n", ptr -> data);

ptr = ptr -> next;
}
printf("%d\n", ptr -> data);
}

void search()
{
struct node *ptr;
int item,i=0,flag=1;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
if(head ->data == item)
{
printf("item found at location %d",i+1);
flag=0;
}
 else
{
while (ptr->next != head)
{
if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
}
if(flag != 0)
{
printf("Item not found\n");
}
}

}
BGSCET
Data Structures and Applications (BCS34)

MODULE 3: TREES

DEFINITION
A tree is a finite set of one or more nodes such that
 There is a specially designated node called root.
 The remaining nodes are partitioned into n >= 0 disjoint set T1,…,Tn, where each of
these sets is a tree. T1,…,Tn are called the subtrees of the root.

Every node in the tree is the root of some subtree

TERMINOLOGY
 Node: The item of information plus the branches to other nodes
 Degree: The number of subtrees of a node
 Degree of a tree: The maximum of the degree of the nodes in the tree.
 Terminal nodes (or leaf): nodes that have degree zero or node with no successor
 Nonterminal nodes: nodes that don’t belong to terminal nodes.
 Parent and Children: Suppose N is a node in T with left successor S1 and right
successor S2, then N is called the Parent (or father) of S1 and S2. Here, S1 is called
left child (or Son) and S2 is called right child (or Son) of N.
 Siblings: Children of the same parent are said to be siblings.
 Edge: A line drawn from node N of a T to a successor is called an edge
 Path: A sequence of consecutive edges from node N to a node M is called a path.
 Ancestors of a node: All the nodes along the path from the root to that node.
 The level of a node: defined by letting the root be at level zero. If a node is at level l,
then it children are at level l+1.
 Height (or depth): The maximum level of any node in the tree
BGSCET
Data Structures and Applications (BCS34)
Example

A is the root node

B is the parent of E and F
C and D are the sibling of B
E and F are the children of B
K, L, F, G, M, I, J are external nodes, or leaves
A, B, C, D, E, H are internal nodes
The level of E is 3
The height (depth) of the tree is 4
The degree of node B is 2
The degree of the tree is 3
The ancestors of node M is A, D, H
The descendants of node D is H, I, J, M

Representation of Trees

There are several ways to represent a given tree such as:

Figure (A)

1. List Representation
2. Left Child- Right Sibling Representation
3. Representation as a Degree-Two tree
BGSCET
Data Structures and Applications (BCS34)

List Representation:

The tree can be represented as a List. The tree of figure (A) could be written as the list.
(A (B (E (K, L), F), C (G), D (H (M), I, J) ) )

 The information in the root node comes first.

 The root node is followed by a list of the subtrees of that node.

Tree node is represented by a memory node that has fields for the data and pointers to the tree
node's children

Since the degree of each tree node may be different, so memory nodes with a varying number
of pointer fields are used.
For a tree of degree k, the node structure can be represented as below figure. Each child field
is used to point to a subtree.

Left Child-Right Sibling Representation

The below figure show the node structure used in the left child-right sibling representation

To convert the tree of Figure (A) into this representation:

1. First note that every node has at most one leftmost child
2. At most one closest right sibling.
BGSCET
Data Structures and Applications (BCS34)
Ex:
 In Figure (A), the leftmost child of A is B, and the leftmost child of D is H.
 The closest right sibling of B is C, and the closest right sibling of H is I.
 Choose the nodes based on how the tree is drawn. The left child field of each node points
to its leftmost child (if any), and the right sibling field points to its closest right sibling
(if any).
Figure (D) shows the tree of Figure (A) redrawn using the left child-right sibling representation.

Figure (D): Left child-right sibling representation of tree of figure (A)

Representation as a Degree-Two Tree

To obtain the degree-two tree representation of a tree, simply rotate the right-sibling pointers
in a left child-right sibling tree clockwise by 45 degrees. This gives us the degree-two tree
displayed in Figure (E).

Figure (E): degree-two representation

In the degree-two representation, a node has two children as the left and right children.
BGSCET
Data Structures and Applications (BCS34)

BINARY TREES
Definition: A binary tree T is defined as a finite set of nodes such that,
 T is empty or
 T consists of a root and two disjoint binary trees called the left subtree and the right
subtree.

Figure: Binary Tree

Different kinds of Binary Tree

1. Skewed Tree
A skewed tree is a tree, skewed to the left or skews to the right.
or
It is a tree consisting of only left subtree or only right subtree.
 A tree with only left subtrees is called Left Skewed Binary Tree.
 A tree with only right subtrees is called Right Skewed Binary Tree.

2. Complete Binary Tree

A binary tree T is said to complete if all its levels, except possibly the last level, have the
maximum number node 2i, i ≥ 0 and if all the nodes at the last level appears as far left as
possible.

Figure (a): Skewed binary tree Figure (b): Complete binary tree
BGSCET
Data Structures and Applications (BCS34)

3. Full Binary Tree

A full binary tree of depth ‘k’ is a binary tree of depth k having 2k – 1 nodes, k ≥ 1.

Figure: Full binary tree of level 4 with sequential node number

4. Extended Binary Trees or 2-trees

An extended binary tree is a transformation of any binary tree into a complete binary tree.
This transformation consists of replacing every null subtree of the original tree with
“special nodes.” The nodes from the original tree are then internal nodes, while the special
nodes are external nodes.
For instance, consider the following binary tree.

The following tree is its extended binary tree. The circles represent internal nodes, and square
represent external nodes.
Every internal node in the extended tree has exactly two children, and every external node is
a leaf. The result is a complete binary tree.
BGSCET
Data Structures and Applications (BCS34)

PROPERTIES OF BINARY TREES

Lemma 1: [Maximum number of nodes]:

(1) The maximum number of nodes on level i of a binary tree is 2 i-1, i ≥ 1.
(2) The maximum number of nodes in a binary tree of depth k is 2k -1, k ≥ 1.

Proof:
(1) The proof is by induction on i.
Induction Base: The root is the only node on level i = 1. Hence, the maximum number of nodes
on level i =1 is 2i-1 = 20 = 1.
Induction Hypothesis: Let i be an arbitrary positive integer greater than 1. Assume that the
maximum number of nodes on level i -1is 2i-2
Induction Step: The maximum number of nodes on level i -1 is 2i-2 by the induction hypothesis.
Since each node in a binary tree has a maximum degree of 2, the maximum number of nodes
on level i is two times the maximum number of nodes on level i-1, or 2i-1

(2) The maximum number of nodes in a binary tree of depth k is

k k
∑ (maximum number of nodes on level i) = ∑ 2i-1 = 2k-1
i=0 i=0

Lemma 2: [Relation between number of leaf nodes and degree-2 nodes]:

For any nonempty binary tree, T, if n0 is the number of leaf nodes and n2 the number of nodes
of degree 2, then n0 = n2 + 1.

Proof: Let n1 be the number of nodes of degree one and n the total number of nodes.
Since all nodes in T are at most of degree two, we have
n = n0 + n1+ n2 (1)
Count the number of branches in a binary tree. If B is the number of branches, then
n =B + 1.
All branches stem from a node of degree one or two. Thus,
B =n 1+ 2n2.
Hence, we obtain
n = B + 1= n 1+ 2n2 + 1 (2)

Subtracting Eq. (2) from Eq. (1) and rearranging terms, we get

n0 = n2 +1
BGSCET
Data Structures and Applications (BCS34)

Consider the figure:

Here, For Figure (b) n2=4, n0= n2+1= 4+1=5

Therefore, the total number of leaf node=5

BINARY TREE REPRESENTATION

The storage representation of binary trees can be classified as
1. Array representation
2. Linked representation.

Array representation:
 A tree can be represented using an array, which is called sequential representation.
 The nodes are numbered from 1 to n, and one dimensional array can be used to store
the nodes.
 Position 0 of this array is left empty and the node numbered i is mapped to position i of
the array.

Below figure shows the array representation for both the trees of figure (a).
BGSCET
Data Structures and Applications (BCS34)

 For complete binary tree the array representation is ideal, as no space is wasted.
 For the skewed tree less than half the array is utilized.

Linked representation:
The problems in array representation are:
 It is good for complete binary trees, but more memory is wasted for skewed and many
other binary trees.
 The insertion and deletion of nodes from the middle of a tree require the movement of
many nodes to reflect the change in level number of these nodes.

These problems can be easily overcome by linked representation

Each node has three fields,

 LeftChild - which contains the address of left subtree
 RightChild - which contains the address of right subtree.
 Data - which contains the actual information

C Code for node:

typedef struct node *treepointer;

typedef struct {
int data;
treepointer leftChild, rightChild;
}node;
BGSCET
Data Structures and Applications (BCS34)

Figure: Node representation

Linked representation of the binary tree

BGSCET
Data Structures and Applications (BCS34)

BINARY TREE TRAVERSALS

Visiting each node in a tree exactly once is called tree traversal

The different methods of traversing a binary tree are:

1. Preorder
2. Inorder
3. Postorder
4. Iterative inorder Traversal
5. Level-Order traversal

1. Inorder: Inorder traversal calls for moving down the tree toward the left until you cannot go
further. Then visit the node, move one node to the right and continue. If no move can be done,
then go back one more node.

Let ptr is the pointer which contains the location of the node N currently being scanned.
L(N) denotes the leftchild of node N and R(N) is the right child of node N

Recursion function:
The inorder traversal of a binary tree can be recursively defined as

 Traverse the left subtree in inorder.

 Visit the root.
 Traverse the right subtree in inorder.

void inorder(treepointerptr)
{
if (ptr)
{
inorder (ptr→leftchild);
printf (“%d”,ptr→data);
inorder (ptr→rightchild);
}
}
BGSCET
Data Structures and Applications (BCS34)

2. Preorder: Preorder is the procedure of visiting a node, traverse left and continue. When you
cannot continue, move right and begin again or move back until you can move right and resume.

Recursion function:
The Preorder traversal of a binary tree can be recursively defined as
 Visit the root
 Traverse the left subtree in preorder.
 Traverse the right subtree in preorder

void preorder (treepointerptr)

{
if (ptr)
{
printf (“%d”,ptr→data)
preorder (ptr→leftchild);
preorder (ptr→rightchild);
}
}

3. Postorder: Postorder traversal calls for moving down the tree towards the left until you can
go no further. Then move to the right node and then visit the node and continue.
Recursion function:
The Postorder traversal of a binary tree can be recursively defined as
 Traverse the left subtree in postorder.
 Traverse the right subtree in postorder.
 Visit the root

void postorder(treepointerptr)
{
if (ptr)
{
postorder (ptr→leftchild);
postorder (ptr→rightchild);
printf (“%d”,ptr→data);
}
}
BGSCET
Data Structures and Applications (BCS34)
4. Iterative inorder Traversal:
Iterative inorder traversal explicitly make use of stack function.
The left nodes are pushed into stack until a null node is reached, the node is then removed from
the stack and displayed, and the node’s right child is stacked until a null node is reached. The
traversal then continues with the left child. The traversal is complete when the stack is empty.

5. Level-Order traversal:
Visiting the nodes using the ordering suggested by the node numbering is called level
ordering traversing.
The nodes in a tree are numbered starting with the root on level 1 and so on.
Firstly visit the root, then the root’s left child, followed by the root’s right child. Thus
continuing in this manner, visiting the nodes at each new level from the leftmost node to the
rightmost node.

Level order traversal: 1 2 3 4 5

Initially in the code for level order add the root to the queue. The function operates by
deleting the node at the front of the queue, printing the nodes data field and adding the nodes
left and right children to the queue.
BGSCET
Data Structures and Applications (15CS33)

Function for level order traversal of a binary tree:

ADDITIONAL BINARY TREE OPERATIONS

1. Copying a Binary tree

This operations will perform a copying of one binary tree to another.

C function to copy a binary tree:

treepointer copy(treepointer original)

{ if(original)
{ MALLOC(temp,sizeof(*temp));
temp→leftchild=copy(original→leftchild);
temp→rightchild=copy(original→rightchild);
temp→data=original→data;
return temp;
}
return NULL;
}

2. Testing Equality
This operation will determin the equivalance of two binary tree. Equivalance binary tree have
the same strucutre and the same information in the corresponding nodes.
BGSCET
Data Structures and Applications (15CS33)

C function for testing equality of a binary tree:

int equal(treepointer first,treepointer second)
{
return((!first && !second) || (first && second && (first→data==second→data)
&& equal(first→leftchild,second→leftchild) && equal(first→rightchild,
second→rightchild))
}

This function will return TRUE if two trees are equivalent and FALSE if they are not.

3. The Satisfiability problem

 Consider the formula that is constructed by set of variables: x1, x2, …, xn and operators
(and), (or), ¬ (not).
 The variables can hold only of two possible values, true or false.
 The expression can form using these variables and operators is defined by the
following rules.
 A variable is an expression
 If x and y are expressions, then ¬x, xy, xy are expressions
 Parentheses can be used to alter the normal order of evaluation (¬ >  > )

Example: x1  (x2  ¬ x3) If x1 and x3 are false and x2 is true

= false  (true  ¬false)
= false  true
= true

The satisfiablity problem for formulas of the propositional calculus asks if there is an
assignment of values to the variable that causes the value of the expression to be true.

Let’s assume the formula in a binary tree

(x1  ¬x2)  (¬ x1  x3)  ¬x3

BGSCET
Data Structures and Applications (15CS33)

The inorder traversal of this tree is

x1  ¬x2  ¬ x1  x3  ¬x3

The algorithm to determine satisfiablity is to let (x1, x2, x3) takes on all the possible
combination of true and false values to check the formula for each combination.

For n value of an expression, there are 2n possible combinations of true and false
For example n=3, the eight combinations are (t,t,t), (t,t,f), (t,f,t), (t,f,f), (f,t,t), (f,t,f), (f,f,t),
(f,f,f).
The algorithm will take O(g 2n), where g is the time to substitute values for x1, x2,… xn and
evaluate the expression.

Node structure:
For the purpose of evaluation algorithm, assume each node has four fields:

Define this node structure in C as:

Satisfiability function: The first version of Satisfiability algorithm

BGSCET
Data Structures and Applications (15CS33)

THREADED BINARY TREE

The limitations of binary tree are:

 In binary tree, there are n+1 null links out of 2n total links.
 Traversing a tree with binary tree is time consuming.
These limitations can be overcome by threaded binary tree.

In the linked representation of any binary tree, there are more null links than actual pointers.
These null links are replaced by the pointers, called threads, which points to other nodes in the
tree.

To construct the threads use the following rules:

1. Assume that ptr represents a node. If ptr→leftChild is null, then replace the null link
with a pointer to the inorder predecessor of ptr.
2. If ptr →rightChild is null, replace the null link with a pointer to the inorder successor of
ptr.
Ex: Consider the binary tree as shown in below figure:

Figure A: Binary Tree

There should be no loose threads in threaded binary tree. But in Figure B two threads have
been left dangling: one in the left child of H, the other in the right child of G.

Figure B: Threaded tree corresponding to Figure A

In above figure the new threads are drawn in broken lines. This tree has 9 node and 10 0 -links
which has been replaced by threads.
BGSCET
Data Structures and Applications (15CS33)

When trees are represented in memory, it should be able to distinguish between threads and
pointers. This can be done by adding two additional fields to node structure, ie., leftThread
and rightThread
 If ptr→leftThread = TRUE, then ptr→leftChild contains a thread,
otherwise it contains a pointer to the left child.
 If ptr→rightThread = TRUE, then ptr→rightChild contains a thread,
otherwise it contains a pointer to the right child.

Node Structure:
The node structure is given in C declaration

typedef struct threadTree *threadPointer

typedef struct{
short int leftThread;
threadPointer leftChild;
char data;
threadPointer rightChild;
short int rightThread;
}threadTree;

The complete memory representation for the tree of figure is shown in Figure C
BGSCET
Data Structures and Applications (15CS33)

The variable root points to the header node of the tree, while root →leftChild points to the
start of the first node of the actual tree. This is true for all threaded trees. Here the problem of
the loose threads is handled by pointing to the head node called root.

Inorder Traversal of a Threaded Binary Tree

 By using the threads, an inorder traversal can be performed without making use of a
stack.
 For any node, ptr, in a threaded binary tree, if ptr→rightThread =TRUE, the inorder
successor of ptr is ptr →rightChild by definition of the threads. Otherwise we obtain
the inorder successor of ptr by following a path of left-child links from the right-
child of ptr until we reach a node with leftThread = TRUE.
 The function insucc ( ) finds the inorder successor of any node in a threaded tree
without using a stack.

threadedpointer insucc(threadedPointer tree)

{ /* find the inorder successor of tree in a threaded binary tree */
threadedpointer temp;
temp = tree→rightChild;
if (!tree→rightThread)
while (!temp→leftThread)
temp = temp→leftChild;
return temp;
Program: Finding inorder successor of a node

To perform inorder traversal make repeated calls to insucc ( ) function

void tinorder (threadedpointer tree)

{
Threadedpointer temp = tree;
for(; ;){
temp = insucc(temp);
if (temp == tree) break;
printf(“%3c”, temp→data
}
}
Program: Inorder traversal of a threaded binary tree
BGSCET
Data Structures and Applications (15CS33)

Inserting a Node into a Threaded Binary Tree

In this case, the insertion of r as the right child of a node s is studied.
The cases for insertion are:
 If s has an empty right subtree, then the insertion is simple and diagrammed in Figure
 If the right subtree of s is not empty, then this right subtree is made the right subtree of
r after insertion. When this is done, r becomes the inorder predecessor of a node that has
a leftThread == true field, and consequently there is a thread which has to be updated
to point to r. The node containing this thread was previously the inorder successor of s.

void insertRight(threadedPointer Sf threadedPointer r)

{ /* insert r as the right child of s */
threadedpointer temp;
r→rightChild = parent→rightChild;
r→rightThread = parent→rightThread;
r→leftChild = parent;
r→leftThread = TRUE;
s→rightChild = child;
s→rightThread = FALSE;
if (!r→rightThread) {
temp = insucc(r);
temp→leftChild = r;
}
}
 Question Bank
Subject: Data Structure and Applications Class: AIDS
Subject code: BCS304 Faculty: Mrs. Jyothi R

Course Outcomes
CO 1. Explain different data structures and their applications.
CO 2. Apply Arrays, Stacks and Queue data structures to solve the given problems.
CO 3. Use the concept of linked list in problem solving.
CO 4. Develop solutions using trees and graphs to model the real-world problem.
CO 5. Explain the advanced Data Structures concepts such as Hashing Techniques and Optimal
Binary Search Trees
MODULE 3

Sl. Questions CO
No.
Topic: LINKED LISTS: Additional List Operations, Sparse Matrices, Doubly Linked List
1. Develop a C function to Invert/Reverse a Single linked list using example CO3
2 Develop a C function to Concatenate single linked list CO3

3 Show diagrammatic linked representation for the following sparse matrix CO3

0 1 2 0 0 3 0 4 0 0 4 0 0 3 0 0 0
3 0 3 0 0 5 7 0 6 5 0 0 0 5 0 0 6
0 0 0 0 0 0 0 0 0 3 0 1 0 0 0 0 0
0 2 6 0 0 0 0 0 0 2 4 0 0 8
0 0 9 0
4 Differentiate Single Linked List(SLL) and Double Linked List(DLL) CO3
5 Write C program to develop Double linked list with following functions CO3
1)Insert a node at front end of the list
2)Delete a node from front end of the list
3)Display
6 Write C program to develop Double linked list with following functions CO3
1)Insert a node at rear end of the list
2)Delete a node from rear end of the list
3)Searching a node with given key value
7 Write C program to develop Double linked list with following functions CO3
1)Insert a node at specific location of the list
2)Delete a node from specific location of the list
8 Write a C program to represent and add two polynomials using singly circular CO3
linked list
Topic: TREES: Introduction, Binary Trees, Binary Tree Traversals, Threaded Binary Trees
9 Define Tree. With the examples explain the terminologies of tree. CO4
10 Explain the representation of trees CO4
11 What is Binary tree and explain its properties with proof CO4

12 CO4
Taking a binary tree as example show the representation of binary tree with both
array and linked list ways.
13 CO4
Write a C functions for of binary tree.

14 CO4
Consider a following tree T write Inorder, Preorde and Postorder traversals along
with its functions.
A
B C
D E G H
J K

15 CO4
Explain five types of Binary tree
16 CO4
Explain the Threaded Binary trees along with function for insertion and inorder
traversal
 UNIT 5 - GRAPHS

The Graph ADT Introduction

Definition
Graph representation
Elementary graph operations BFS, DFS
Introduction to Graphs

Graph is a non linear data structure; A map is a well-known example of a graph. In a map various connections are
made between the cities. The cities are connected via roads, railway lines and aerial network. We can assume that
the graph is the interconnection of cities by roads. Euler used graph theory to solve Seven Bridges of Königsberg
problem. Is there a possible way to traverse every bridge exactly once – Euler Tour

Figure: Section of the river Pregal in Koenigsberg and Euler's graph.

Defining the degree of a vertex to be the number of edges incident to it, Euler showed that there is a walk starting
at any vertex, going through each edge exactly once and terminating at the start vertex iff the degree of each,
vertex is even. A walk which does this is called Eulerian. There is no Eulerian walk for the Koenigsberg bridge
problem as all four vertices are of odd degree.

A graph contains a set of points known as nodes (or vertices) and set of links known as edges (or Arcs) which
connects the vertices.

A graph is defined as Graph is a collection of vertices and arcs which connects vertices in the graph. A graph G is
represented as G = ( V , E ), where V is set of vertices and E is set of edges.

Example: graph G can be defined as G = ( V , E ) Where V = {A,B,C,D,E} and

E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}. This is a graph with 5 vertices and 6 edges.

Graph Terminology

1.Vertex : An individual data element of a graph is called as Vertex. Vertex is also known as node. In above
example graph, A, B, C, D & E are known as vertices.

2.Edge : An edge is a connecting link between two vertices. Edge is also known as Arc. An edge is represented as
(starting Vertex, ending Vertex).

In above graph, the link between vertices A and B is represented as (A,B).

Edges are three types:

1.Undirected Edge - An undirected edge is a bidirectional edge. If there is an undirected edge between vertices A
and B then edge (A , B) is equal to edge (B , A).

2.Directed Edge - A directed edge is a unidirectional edge. If there is a directed edge between vertices A and B
then edge (A , B) is not equal to edge (B , A).

1
3.Weighted Edge - A weighted edge is an edge with cost on it.

Types of Graphs

1.Undirected Graph

A graph with only undirected edges is said to be undirected graph.

2.Directed Graph

A graph with only directed edges is said to be directed graph.

3.Complete Graph

A graph in which any V node is adjacent to all other nodes present in the graph is known as a complete graph. An
undirected graph contains the edges that are equal to edges = n(n-1)/2 where n is the number of vertices present in
the graph. The following figure shows a complete graph.

4.Regular Graph

Regular graph is the graph in which nodes are adjacent to each other, i.e., each node is accessible from any other
node.

5.Cycle Graph

A graph having cycle is called cycle graph. In this case the first and last nodes are the same. A closed simple path
is a cycle.

2
6.Acyclic Graph

A graph without cycle is called acyclic graphs.

7. Weighted Graph

A graph is said to be weighted if there are some non negative value assigned to each edges of the graph. The
value is equal to the length between two vertices. Weighted graph is also called a network.

Outgoing Edge

A directed edge is said to be outgoing edge on its orign vertex.

Incoming Edge

A directed edge is said to be incoming edge on its destination vertex.

Degree

Total number of edges connected to a vertex is said to be degree of that vertex.

Indegree

Total number of incoming edges connected to a vertex is said to be indegree of that vertex.

Outdegree

Total number of outgoing edges connected to a vertex is said to be outdegree of that vertex.

Parallel edges or Multiple edges

If there are two undirected edges to have the same end vertices, and for two directed edges to have the same
origin and the same destination. Such edges are called parallel edges or multiple edges.

Self-loop

An edge (undirected or directed) is a self-loop if its two endpoints coincide.

Simple Graph

A graph is said to be simple if there are no parallel and self-loop edges.

3
Adjacent nodes

When there is an edge from one node to another then these nodes are called adjacent nodes.
Incidence

In an undirected graph the edge between v1 and v2 is incident on node v1 and v2.
Walk

A walk is defined as a finite alternating sequence of vertices and edges, beginning and ending with vertices, such
that each edge is incident with the vertices preceding and following it.
Closed walk

A walk which is to begin and end at the same vertex is called close walk. Otherwise it is an open walk.

If e1,e2,e3,and e4 be the edges of pair of vertices (v1,v2),(v2,v4),(v4,v3) and (v3,v1) respectively ,then v1 e1 v2
e2 v4 e3 v3 e4 v1 be its closed walk or circuit.

Path

A open walk in which no vertex appears more than once is called a path.

If e1 and e2 be the two edges between the pair of vertices (v1,v3) and (v1,v2) respectively, then v3 e1 v1 e2 v2 be
its path.
Length of a path

The number of edges in a path is called the length of that path. In the following, the length of the path is 3.

An open walk Graph

Circuit

A closed walk in which no vertex (except the initial and the final vertex) appears more than once is called a
circuit.
A circuit having three vertices and three edges.

4
Sub Graph

A graph S is said to be a sub graph of a graph G if all the vertices and all the edges of S are in G, and each edge of
S has the same end vertices in S as in G. A subgraph of G is a graph G’ such that V(G’)  V(G) and E(G’) 
E(G)

Connected Graph

A graph G is said to be connected if there is at least one path between every pair of vertices in G. Otherwise,G is
disconnected.

A connected graph G A disconnected graph G

This graph is disconnected because the vertex v1 is not connected with the other vertices of the graph.

Degree

In an undirected graph, the number of edges connected to a node is called the degree of that node or the degree of
a node is the number of edges incident on it.

In the above graph, degree of vertex v1 is 1, degree of vertex v2 is 3, degree of v3 and v4 is 2 in a connected
graph.

Indegree

The indegree of a node is the number of edges connecting to that node or in other words edges incident to it.

In the above graph,the indegree of vertices v1, v3 is 2, indegree of vertices v2, v5 is 1 and indegree of v4 is zero.
5
Outdegree

The outdegree of a node (or vertex) is the number of edges going outside from that node or in other words the

ADT of Graph:

Structure Graph is

objects: a nonempty set of vertices and a set of undirected edges, where each edge is a pair of vertices

functions: for all graph  Graph, v, v1 and v2  Vertices

Graph Create()::=return an empty graph

Graph InsertVertex(graph, v)::= return a graph with v inserted. v has no edge.

Graph InsertEdge(graph, v1,v2)::= return a graph with new edge between v1 and v2

Graph DeleteVertex(graph, v)::= return a graph in which v and all edges incident to it are removed

Graph DeleteEdge(graph, v1, v2)::=return a graph in which the edge (v1, v2) is removed

Boolean IsEmpty(graph)::= if (graph==empty graph) return TRUE else return FALSE

List Adjacent(graph,v)::= return a list of all vertices that are adjacent to v

Graph Representations

Graph data structure is represented using following representations

1. Adjacency Matrix

2. Adjacency List

3. Adjacency Multilists

1.Adjacency Matrix

In this representation, graph can be represented using a matrix of size total number of vertices by total number of
vertices; means if a graph with 4 vertices can be represented using a matrix of 4X4 size.

In this matrix, rows and columns both represent vertices.

This matrix is filled with either 1 or 0. Here, 1 represents there is an edge from row vertex to column vertex and 0
represents there is no edge from row vertex to column vertex.

Adjacency Matrix : let G = (V, E) with n vertices, n  1. The adjacency matrix of G is a 2-dimensional n  n
matrix, A, A(i, j) = 1 iff (vi, vj) E(G) (vi, vj for a diagraph), A(i, j) = 0 otherwise.

example : for undirected graph

For a Directed graph

6
The adjacency matrix for an undirected graph is symmetric; the adjacency matrix for a digraph need not be
symmetric.

Merits of Adjacency Matrix:

From the adjacency matrix, to determine the connection of vertices is easy

n 1
The degree of a vertex is  adj _ mat[i][ j ]
j 0

For a digraph, the row sum is the out_degree, while the column sum is the in_degree
n 1 n 1
ind (vi )   A[ j , i ] outd (vi )   A[i, j ]
j 0 j 0
The space needed to represent a graph using adjacency matrix is n2 bits. To identify the edges in a graph,
adjacency matrices will require at least O(n2) time.

2. Adjacency List

In this representation, every vertex of graph contains list of its adjacent vertices. The n rows of the adjacency
matrix are represented as n chains. The nodes in chain I represent the vertices that are adjacent to vertex i.

It can be represented in two forms. In one form, array is used to store n vertices and chain is used to store its
adjacencies. Example:

So that we can access the adjacency list for any vertex in O(1) time. Adjlist[i] is a pointer to to first node in the
adjacency list for vertex i. Structure is

#define MAX_VERTICES 50
typedef struct node *node_pointer;
typedef struct node {
int vertex;
struct node *link;
};
node_pointer graph[MAX_VERTICES];
int n=0; /* vertices currently in use */

Another type of representation is given below.

example: consider the following directed graph representation implemented using linked list

7
This representation can also be implemented using array

Sequential representation of adjacency list is

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 11 13 15 17 18 20 22 23 2 1 3 0 0 3 1 2 5 6 4 5 7 6

Graph

Instead of chains, we can use sequential representation into an integer array with size n+2e+1. For 0<=i<n,
Array[i] gives starting point of the list for vertex I, and array[n] is set to n+2e+1. The adjacent vertices of node I
are stored sequentially from array[i].

For an undirected graph with n vertices and e edges, linked adjacency list requires an array of size n and 2e chain
nodes. For a directed graph, the number of list nodes is only e. the out degree of any vertex may be determined by
counting the number of nodes in its adjacency list. To find in-degree of vertex v, we have to traverse complete
list.

To avoid this, inverse adjacency list is used which contain in-degree.

3.Adjacency Multilists

In the adjacency-list representation of an undirected graph each edge (u, v) is represented by two entries one on
the list for u and the other on tht list for v. As we shall see in some situations it is necessary to be able to determin
ie ~ nd enty for a particular edge and mark that edg as having been examined. This can be accomplished easily
if the adjacency lists are actually maintained as multilists (i.e., lists in which nodes may be shared among several
lists). For each edge there will be exactly one node but this node will be in two lists (i.e. the adjacency lists for
each of the two nodes to which it is incident).
For adjacency multilists, node structure is
typedef struct edge *edge_pointer;
typedef struct edge {
short int marked;
int vertex1, vertex2;
edge_pointer path1, path2;
};
edge_pointer graph[MAX_VERTICES];
8
Lists: vertex 0: N0->N1->N2, vertex 1: N0->N3->N4
vertex 2: N1->N3->N5, vertex 3: N2->N4->N5

Figure: Adjacency multilists for given graph

4. Weighted edges

In many applications the edges of a graph have weights assigned to them. These weights may represent the
distance from one vertex to another or the cost of going from one; vertex to an adjacent vertex In these
applications the adjacency matrix entries A [i][j] would keep this information too. When adjacency lists are used
the weight information may be kept in the list’nodes by including an additional field weight. A graph with
weighted edges is called a network.

ELEMENTARY GRAPH OPERATIONS

Given a graph G = (V E) and a vertex v in V(G) we wish to visit all vertices in G that are reachable from v (i.e.,
all vertices that are connected to v). We shall look at two ways of doing this: depth-first search and breadth-first
search. Although these methods work on both directed and undirected graphs the following discussion assumes
that the graphs are undirected.

Depth-First Search

 Begin the search by visiting the start vertex v

o If v has an unvisited neighbor, traverse it recursively
o Otherwise, backtrack
 Time complexity
o Adjacency list: O(|E|)
o Adjacency matrix: O(|V|2)

We begin by visiting the start vertex v. Next an unvisited vertex w adjacent to v is selected, and a depth-first
search from w is initiated. When a vertex u is reached such that all its adjacent vertices have been visited, we back
up to the last vertex visited that has an unvisited vertex w adjacent to it and initiate a depth-first search from w.
The search terminates when no unvisited vertex can be reached from any of the visited vertices.

DFS traversal of a graph, produces a spanning tree as final result. Spanning Tree is a graph without any loops.
We use Stack data structure with maximum size of total number of vertices in the graph to implement DFS

9
traversal of a graph.

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 adjacent vertex of the verex which is at top of the stack which is not visited and push
it on to the stack.

Step 4: Repeat step 3 until there are no new vertex to be visit from the vertex on top of the stack.

Step 5: When there is no new vertex to be 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

This function is best described recursively as in Program.

#define FALSE 0
#define TRUE 1
int visited[MAX_VERTICES];
void dfs(int v)
{
node_pointer w;
visited[v]= TRUE;
printf(“%d”, v);
for (w=graph[v]; w; w=w->link)
if (!visited[w->vertex])
dfs(w->vertex);
}
Consider the graph G of Figure 6.16(a), which is represented by its adjacency lists as in Figure 6.16(b). If a depth-
first search is initiated from vertex 0 then the vertices of G are visited in the following order: 0 1 3 7 4 5 2 6.
Since DFS(O) visits all vertices that can be reached from 0 the vertices visited, together with all edges in
G incident to these vertices form a connected component of G.

Figure: Graph and its adjacency list representation, DFS spanning tree

Analysis or DFS:
When G is represented by its adjacency lists, the vertices w adjacent to v can be determined by following a chain
of links. Since DFS examines each node in the adjacency lists at most once and there are 2e list nodes the time to
complete the search is O(e). If G is represented by its adjacency matrix then the time to determine all
vertices adjacent to v is O(n). Since at most n vertices are visited the total time is O(n2).
Breadth-First Search
In a breadth-first search, we begin by visiting the start vertex v. Next all unvisited vertices adjacent to v are
visited. Unvisited vertices adjacent to these newly visited vertices are then visited and so on. Algorithm BFS
(Program 6.2) gives the details.
typedef struct queue *queue_pointer;
typedef struct queue {
int vertex;

10
 queue_pointer link;
};
void addq(queue_pointer *,
queue_pointer *, int);
int deleteq(queue_pointer *);
void bfs(int v)
{
node_pointer w;
queue_pointer front, rear;
front = rear = NULL;
printf(“%d”, v);
visited[v] = TRUE;
addq(&front, &rear, v);
while (front) {
v= deleteq(&front);
for (w=graph[v]; w; w=w->link)
if (!visited[w->vertex]) {
printf(“%d”, w->vertex);
addq(&front, &rear, w->vertex);
visited[w->vertex] = TRUE;
}
}
}
Steps:
BFS traversal of a graph, produces a spanning tree as final result. Spanning Tree is a graph without any loops. We
use Queue data structure with maximum size of total number of vertices in the graph to implement BFS traversal
of a graph.

We use the following steps to implement BFS traversal...

Step 1: Define a Queue of size total number of vertices in the graph.
Step 2: Select any vertex as starting point for traversal. Visit that vertex and insert it into the Queue.
Step 3: Visit all the adjacent vertices of the vertex which is at front of the Queue which is not visited and insert
them into the Queue.
Step 4: When there is no new vertex to be visit from the vertex at front of the Queue then delete that vertex from
the Queue.
Step 5: Repeat step 3 and 4 until queue becomes empty.
Step 6: When queue becomes Empty, then produce final spanning tree by removing unused edges from the graph
Analysis Of BFS:
Each visited vertex enters the queue exactly once. So the while loop is iterated at most n times If an adjacency
matrix is used the loop takes O(n) time for each vertex visited. The total time is therefore, O(n2). If adjacency lists
are used the loop has a total cost of d0 + … + dn-1 = O(e), where d is the degree of vertex i. As in the case of DFS
all visited vertices together with all edges incident to them, form a connected component of G.
3.Connected Components
If G is an undirected graph, then one can determine whether or not it is connected by simply making a call to
either DFS or BFS and then determining if there is any unvisited vertex. The connected components of a graph
may be obtained by making repeated calls to either DFS(v) or BFS(v); where v is a vertex that has not yet been
visited. This leads to function Connected(Program 6.3), which determines the connected components of G. The
algorithm uses DFS (BFS may be used instead if desired). The computing time is not affected. Function
connected –Output outputs all vertices visited in the most recent invocation of DFS together with all edges
incident on these vertices.
void connected(void){
for (i=0; i<n; i++) {
if (!visited[i]) {
dfs(i);
printf(“\n”); } }}
Analysis of Components:
If G is represented by its adjacency lists, then the total time taken by dfs is O(e). Since the for loops take O(n)
time, the total time to generate all the Connected components is O(n+e). If adjacency matrices are used,then the
time required is O(n2)
11
12
13
http://m.kkhsou.in/EBIDYA/CSC/MODIFY_intro_graph.html

14
 Question Bank
Subject: Data Structure and Applications Class: AIDS
Subject code: BCS304 Faculty: Mrs. Jyothi R

Course Outcomes
CO 1. Explain different data structures and their applications.
CO 2. Apply Arrays, Stacks and Queue data structures to solve the given problems.
CO 3. Use the concept of linked list in problem solving.
CO 4. Develop solutions using trees and graphs to model the real-world problem.
CO 5. Explain the advanced Data Structures concepts such as Hashing Techniques and Optimal
Binary Search Trees
MODULE 4

Sl. Questions CO
No.
1. Draw a binary serach tree for the following input of elements CO4
40 10 79 90 12 54 11 9 50 and also write a Recursive Search function for
Binary Search tree
2. Construct a Binary tree by using the following in-order and preorder traversal CO4
Inorder: BCAEDGHFI
Preorder: ABCDEFGHI
3. Write a Recursive Search and Iterative Search function for Binary Search tree CO4
4. Write a function to perform Delete from BST and Insert an element into BST and CO4
explain with example
5. Construct a Binary tree by using the following in-order and preorder traversal CO4
Inorder: 42516738
Preorder: 45267831
6. Write a function to find CO4
i) Maximum element in BST
ii) Minimum element in BST
iii) Height of BST
iv) Count the no of nodes in BST
v) count the no of leaf nodes in BST
7. Write short notes on: CO4
i) Transforming a Forest into a Binary Tree
ii) Forest Traversals.
iii) Selection Tress
iv) Array and linked representation of binary trees
8. Construct a Binary tree by using the following in-order and preorder traversal CO4
Inorder: EACKFHDBG
Preorder: FAEKCDHGB also perform postorder traversal of the obtained tree
9. Draw a binary serach tree for the following input of elements CO4
14, 15, 4, 9, 7, 18, 3, 5, 16, 20 and also perform Inorder, Preorder and Postorder
Traversal
1 DATA STRUCTURES AND APPLICATIONS (BCS304)

MODULE-5
HASHING: Introduction, Static Hashing, Dynamic Hashing
PRIORITY QUEUES: Single and double ended Priority Queues, Leftist Trees
INTRODUCTION TO EFFICIENT BINARY SEARCH TREES: Optimal Binary Search Trees

HASHING:
We have already seen that the time required to access any element in the array irrespective of its
position is same. The physical location of ith item in the array can be calculated by multiplying
the size of each element of the array with i and adding to the base address as shown below:

Loc(Ai) = Base(A) + w*(i – lb)

Here,
i - is the index,
w - is the size of each element of the array and
lb - is the lower bound. Using this formula, the address of any item at any specified position i can
be obtained and from the address obtained, we can access the item. The similar idea is used in
hashing to store and retrieve the data.So, the hashing technique is essentially independent of n
where n is number of elements.

Definition:
A function can be used to provide a mapping between large original data and the smaller table
by transforming a key information into an index to the table. The index value returned by this
function is called hash value.
The function that transforms a data into hash value to a table is called hash function.

Definition:
The data can be stored in the form of a table using arrays with the help of hash function which
gives a hash value as an index to access any element in the table. This table on which insertion,
deletion and retrieve operations takes place with the help of hash value is called hash table.

A hash table can be implemented as an array ht[0..m-1]. The size of the hash table is limited and so it
is necessary to mapthegivendata into this fairly restricted set of integers. The hash function assigns an
integer value from 0 to m-1 to keys and these values which act as index to the hash table are
called hash addresses or hash values.

1
2 DATA STRUCTURES AND APPLICATIONS (BCS304)

What is hashing?
This process of mapping large amounts of data into a smaller table using hash function, hash
value and hash table is called hashing.

The two types of hashing techniques are:

1. Static hashing
2. Dynamic hashing

Static hashing :
What is static hashing?

Definition: This process of mapping large amounts of data into a table whose size is fixed during
compilation time is called static hashing. In static hashing, all the data items are stored in a fixed
size tablet called hash table. The hash table is implemented as an array ht[0..m-1] with 0 as the
low index and m – 1 as the high index. Each item in the table can be stored in ht[0],
ht[1],…….ht[m – 1] where m is the size of the table usually with a prime number such as 5, 7,
11 and so on. The items are inserted into the table based on the hash value obtained from the
hash function.

Hash table

Now, let us take the following example, where identifiers are inserted into the hashtable.

Example : Construct a hash table ht for storing various identifiers.

Solution: We need to store identifiers in a hash table.

Let us assume all identifiers starts with only letters from ‘A’ to ‘Z’ having the range 0 to 25.
Since, there are 26letters, let us have a hash table ht whose size is m = 26. Assume identifiers to
be inserted into hash table ht are: ant, dog, cat, bat, eagle, fish and ape. To insert an identifier
into the hash table, we require hash function.

Let us define hash function as:

h(x) = toupper(x[0]) – 65 // range is 0 to 25 for‘a’ to ‘z’

where 65 is the ASCII value of ‘A’.

Now, let us complete hash value for each of the identifier using the above hash function:
 Hash value of identifier “ant”=‘A’ – 65 = 65 – 65 = 0. So, insert “ant” into ht[0]
 Hash value of identifier “dog”= ‘D’ – 65 = 68 – 65 = 3. So, insert “dog” into ht[3]
 Hash value of identifier “cat” = ‘C’ – 65 = 67 – 65 = 2. So, insert “cat” into ht[2]
 Hash value of identifier “bat” = ‘B’ – 65 = 66 – 65 = 1. So, insert “bat” into ht[1]
 Hash value of identifier “eagle” = ‘E’ – 65 = 69 – 65 = 4. So, insert “eagle” into ht[4]
 Hash value of identifier “f ish” = ‘F’ – 65 = 70 – 65 = 5. So, insert “eagle” into ht[5]
 Hash value of identifier “a pe” = ‘A’ – 65 = 65 – 65 = 0. So, insert “a pe” into ht[0]

2
3 DATA STRUCTURES AND APPLICATIONS (BCS304)

Now, the hash table for first six identifiers is shown below:


The seventh identifier “ape” whose hash value is 0 cannot be inserted into ht[0] because,
an identifier is already placed in ht[0]. This condition is called over flow or collision.

 When there is no overflow, the time required to insert, delete or search depends only on
the time required to compute the hash function and the time to search on location in ht[i].
Hence, the insert, delete and search times are independent of n which is the number of
items.

 Most of the time collision cannot be avoided and in the worst case all keys may have the
same hash value. In such situation all the keys may be stored in only one cell in the form
of a list and so, it is required to search all n keys in the worst case.

 But, with appropriately chosen size of the hash table and using a good hash function, this
phenomenon will not occur and under reasonable assumptions, the expected time to
search for an element in a hash table will be O (1).

 So, in practical situation, hashing is extremely effective where insertion, deletion and
searching takes place frequently.

The various hashing techniques using which collision can be avoided are:
 Open addressing
 Chaining

OPEN ADDRESSING:
In open addressing hashing, the amount of space available for storing various data is
fixed at compile time by declaring a fixed array for the hash table. So, all the keys are
stored in this fixed hash table itself without the use of linked lists. In such a table,
collision can be avoided by finding another, unoccupied location in the array. The
collision can be avoided using linear probing.

Let us create a hash table. To create a hash table, we need the following:
 Initial hash table.
 Select the hashing function.
 Find the index of each location in the hash table.

3
4 DATA STRUCTURES AND APPLICATIONS (BCS304)

Create initial hash table:

Assume the size of the hash table is HASH_SIZE = 5 and the hash table can be pictorially
represented as shown below:

The empty hash table is indicated by storing 0 values in each location as shown below:

The function to create initial hash table can be written as shown below:

Create initial hash table

Identify the hash function

H(k) = k % m wherem is HASH_SIZE. The equivalent codecan be written as shown below:

Compute hash value using the function:H(k) = k % m

int H(int k)
{
return k % HASH_SIZE;
}

Find the index for hash table given hash value

This can be done using the following code:

4
5 DATA STRUCTURES AND APPLICATIONS (BCS304)

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

{
printf (“%d “, i); // 0 1 2 3 4
}

Insert an item into hash table using linear probing

This is achieved by accessing each item in the hash table. Each item in the hash table can be
accessed using the following code:

h_value = H(item);
for (i = 0; i < HASH_SIZE; i++)
{
index = (h_value + i) % HASH_SIZE;
a[index];
}

Search for an item in the hash table

5
6 DATA STRUCTURES AND APPLICATIONS (BCS304)

HASH FUNCTIONS:

overview of four different types of uniform hash functions:

Mid-square: This method involves squaring the identifier and using a portion of the resulting
square's bits to obtain the hash address. It is effective because it usually depends on all the
characters in the identifier, reducing collisions.

Division: This method utilizes the modulus operator, where the identifier is divided by a chosen
number M, and the remainder is used as the hash address. However, the choice of M is crucial,
and it's recommended to avoid biases by selecting a prime number for M.

Folding: This technique partitions the identifier into parts and combines them to obtain the hash
address. There are two methods: shift folding and folding at the boundaries, each with its own
way of combining the parts.

Digit Analysis: This approach is suitable for static files where all identifiers are known in
advance. It involves transforming identifiers into numbers, examining their digits, and deleting
digits with skewed distributions until the remaining digits provide a suitable hash address range.

Creation of a hash function

6
7 DATA STRUCTURES AND APPLICATIONS (BCS304)

Linear insert into a hash table

C program to create hash table and to search for key

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

#define HASH_SIZE 5

void main()
{
int a[10], item, key, choice, flag;

initialize_hash_table(a); // Create initial hash table

7
8 DATA STRUCTURES AND APPLICATIONS (BCS304)

DYNAMIC HASHING:

Challenges with Traditional Hashing in DBMS: Traditional hashing methods require static
allocation of memory for the hash table, which can be inefficient. Allocating too much memory
wastes space, while allocating too little requires restructuring the entire file when data exceeds
the table's capacity, leading to time-consuming operations.
Dynamic Hashing Solution: Dynamic hashing, or extendible hashing, addresses these
challenges by allowing the hash table to accommodate dynamically increasing and decreasing
file sizes without penalties. It maintains fast retrieval times while adapting to changing data
volumes.
File Structure: In dynamic hashing, a file (F) consists of records (R), each identified by a key
field (K). Records are stored in buckets or pages, with each page typically having a capacity of p.
Minimizing page accesses is crucial, as pages are often stored on disk, and retrieving them into
memory dominates any operation.

8
9 DATA STRUCTURES AND APPLICATIONS (BCS304)

Space Utilization: The efficiency of dynamic hashing is measured by the ratio of the number of
records (n) to the total space (mp), where m is the number of pages. Maximizing space utilization
is essential for optimal performance.

Dynamic hashing using directories with the provided example of identifiers and their
binary representations:

1. Page Structure: We have four pages indexed by the 2-bit sequence: 00, 01, 10, 11, each
capable of holding up to two identifiers.
2. Identifier Representation: Each identifier consists of two characters, with each character
represented by 3 bits. For example:
- Identifier "aO" is represented as 100 000
- Identifier "al" is represented as 100 001
- Identifier "bO" is represented as 101 000
- And so on.
3. Placement of Identifiers: Using the two low-order bits of each identifier, we determine the
page address for each identifier. For example:
- "aO" and "bO" have the same low-order bits (00), so they are placed on the first page (index
00).
- "c2" has the low-order bits 10, so it goes on the third page (index 10).
- "al" and "bl" have the low-order bits 01, so they go on the second page (index 01).
- "c3" has the low-order bits 11, so it goes on the fourth page (index 11).
4. Trie Structure: We construct a trie where each node represents a bit position, and branching
occurs based on the value of that bit. For example:
- At the root node, we branch based on the least significant bit.
- At the next level, we branch based on the second least significant bit, and so on.
5. Traversal: To locate an identifier, we follow its bit sequence through the trie, branching
accordingly at each node until reaching a leaf node containing a pointer to the corresponding
page.
6. Efficient Retrieval: Organizing identifiers in this manner allows for efficient retrieval, as the
trie structure enables direct traversal based on the binary representation of the identifiers.

9
10 DATA STRUCTURES AND APPLICATIONS (BCS304)

7. Leaf Nodes: Only the leaf nodes of the trie contain pointers to pages, indicating where the
identifiers are stored in the table.
C program that provides many of the details for implementing the directory version of
dynamic hashing.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_IDENTIFIERS 100

#define MAX_PAGES 4
#define MAX_IDENTIFIERS_PER_PAGE 2

// Structure to represent an identifier

typedef struct {
char name[3]; // Assuming each identifier has two characters
} Identifier;

// Structure to represent a page

typedef struct {
Identifier identifiers[MAX_IDENTIFIERS_PER_PAGE];
int num_identifiers;
} Page;

// Structure to represent a directory

typedef struct {
Page pages[MAX_PAGES];
} Directory;

// Hash function to determine the page index for an identifier

10
11 DATA STRUCTURES AND APPLICATIONS (BCS304)

int hash(char identifier[3]) {

// Use the two low-order bits of the identifier
return (identifier[0] & 0x03);
}

// Function to insert an identifier into the directory

void insert_identifier(Directory *directory, char identifier[3]) {
int index = hash(identifier);
Page *page = &directory->pages[index];

// Check if page is full

if (page->num_identifiers < MAX_IDENTIFIERS_PER_PAGE) {
strcpy(page->identifiers[page->num_identifiers].name, identifier);
page->num_identifiers++;
} else {
// Page is full, handle overflow or split
// Implementation specific, not included in this pseudo code
printf("Page is full. Overflow or split needed.\n");
}
}

// Function to search for an identifier in the directory

void search_identifier(Directory *directory, char identifier[3]) {
int index = hash(identifier);
Page *page = &directory->pages[index];

// Search for the identifier in the page

for (int i = 0; i < page->num_identifiers; i++) {

11
12 DATA STRUCTURES AND APPLICATIONS (BCS304)

if (strcmp(page->identifiers[i].name, identifier) == 0) {
printf("Identifier %s found in page %d.\n", identifier, index);
return;
}
}

printf("Identifier %s not found.\n", identifier);

}

int main() {
Directory directory;

// Initialize directory pages

for (int i = 0; i < MAX_PAGES; i++) {
directory.pages[i].num_identifiers = 0;
}

// Example of inserting identifiers

insert_identifier(&directory, "aO");
insert_identifier(&directory, "bO");
insert_identifier(&directory, "c2");
insert_identifier(&directory, "al");
insert_identifier(&directory, "bl");
insert_identifier(&directory, "c3");

// Example of searching for identifiers

search_identifier(&directory, "aO");
search_identifier(&directory, "c2");

12
13 DATA STRUCTURES AND APPLICATIONS (BCS304)

search_identifier(&directory, "d1"); // Identifier not inserted

return 0;
}

Leftist tree:
To define a leftist tree, we first introduce the concept of an extended binary tree. An extended
binary tree is a binary tree where all empty binary subtrees have been replaced by square nodes,
called external nodes. The original nodes of the binary tree are called internal nodes.

1. Extended Binary Tree:

- An extended binary tree is a binary tree where all empty subtrees are replaced by square
nodes, called external nodes.
- Internal nodes are the original nodes of the binary tree.

2. Shortest Path Length:

- For any node X in an extended binary tree, let shortest(X) denote the length of the shortest
path from X to an external node.

3. Properties of Shortest Path Length:

- The shortest path length satisfies the following recurrence:
shortest(X) =
0 if X is an external node (square node)
1 1 + min(shortest(left-child(X)), shortest(right-child(X))) otherwise

4. Leftist Tree:
- A leftist tree is a binary tree that satisfies the leftist property, which states that the shortest
path length of any node's right subtree is always greater than or equal to the shortest path length
of its left subtree.
- Formally, for any node X in a leftist tree, the leftist property is given by:
Shortest(right-child(X)) >= shortest(left-child(x))

13
14 DATA STRUCTURES AND APPLICATIONS (BCS304)

5. Combine Operation:
- The combine operation for leftist trees merges two leftist trees into a single leftist tree.
- During the combine operation, the trees are merged such that the leftist property is
maintained.
- The combine operation in a leftist tree takes logarithmic time, making it efficient for merging
priority queues.

Two binary trees

. Extended binary trees

14
15 DATA STRUCTURES AND APPLICATIONS (BCS304)

15
16 DATA STRUCTURES AND APPLICATIONS (BCS304)

Finding an optimal binary search tree

16
 Question Bank
Subject: Data Structure and Applications Class: AIDS
Subject code: BCS304 Faculty: Mrs. Jyothi R

Course Outcomes
CO 1. Explain different data structures and their applications.
CO 2. Apply Arrays, Stacks and Queue data structures to solve the given problems.
CO 3. Use the concept of linked list in problem solving.
CO 4. Develop solutions using trees and graphs to model the real-world problem.
CO 5. Explain the advanced Data Structures concepts such as Hashing Techniques and Optimal
Binary Search Trees
MODULE 5

Sl. Questions CO
No.
1. What is Hashing? Explain how Hashing table is constructed CO5
2. Explain the creation of hash function. CO5
3. Discuss Linear insert into hash table CO5
4. CO5
Write a C program to create hash table and to search for key
5. Explain DYNAMIC HASHING CO5
6. Dynamic hashing using directories with the provided example of identifiers and CO5
their binary representations
7. C program that provides many of the details for implementing the directory version CO5
of dynamic hashing
8. CO5
Explain Leftist tree.
9. Write a function to Finding an optimal binary search tree CO5