What is Data structure?

A data structure is a technique of storing and organizing the data in such a

way that the data can be utilized in an efficient manner. In computer
science, a data structure is designed in such a way that it can work with
various algorithms. A data structure is classified into two categories:
o Linear data structure
o Non-linear data structure
Now let's have a brief look at both these data structures.
What is the Linear data structure?
A linear data structure is a structure in which the elements are stored
sequentially, and the elements are connected to the previous and the next
element. As the elements are stored sequentially, so they can be traversed
or accessed in a single run. The implementation of linear data structures is
easier as the elements are sequentially organized in memory. The data
elements in an array are traversed one after another and can access only
one element at a time.
The types of linear data structures are Array, Queue, Stack, Linked List.
22.5M
429
Difference between JDK, JRE, and JVM
Let's discuss each linear data structure in detail.
o Array: An array consists of data elements of a same data type. For
example, if we want to store the roll numbers of 10 students, so
instead of creating 10 integer type variables, we will create an array
having size 10. Therefore, we can say that an array saves a lot of
memory and reduces the length of the code.
o Stack: It is linear data structure that uses the LIFO (Last In-First Out)
rule in which the data added last will be removed first. The addition of
data element in a stack is known as a push operation, and the deletion
of data element form the list is known as pop operation.
o Queue: It is a data structure that uses the FIFO rule (First In-First Out).
In this rule, the element which is added first will be removed first.
There are two terms used in the queue front end and rear The
insertion operation performed at the back end is known ad enqueue,
and the deletion operation performed at the front end is known as
dequeue.
o Linked list: It is a collection of nodes that are made up of two parts,
i.e., data element and reference to the next node in the sequence.
What is a Non-linear data structure?
A non-linear data structure is also another type of data structure in which the
data elements are not arranged in a contiguous manner. As the arrangement
is nonsequential, so the data elements cannot be traversed or accessed in a
single run. In the case of linear data structure, element is connected to two
elements (previous and the next element), whereas, in the non-linear data
structure, an element can be connected to more than two elements.
Trees and Graphs are the types of non-linear data structure.
Let's discuss both the data structures in detail.
o Tree
It is a non-linear data structure that consists of various linked nodes. It has a
hierarchical tree structure that forms a parent-child relationship. The
diagrammatic representation of a tree data structure is shown below:

For example, the posts of employees are arranged in a tree data structure
like managers, officers, clerk. In the above figure, A represents a
manager, B and C represent the officers, and other nodes represent the
clerks.
o Graph
A graph is a non-linear data structure that has a finite number of vertices
and edges, and these edges are used to connect the vertices. The vertices
are used to store the data elements, while the edges represent the
relationship between the vertices. A graph is used in various real-world
problems like telephone networks, circuit networks, social networks like
LinkedIn, Facebook. In the case of facebook, a single user can be considered
as a node, and the connection of a user with others is known as edges.

Differences between the Linear data structure and non-linear data

structure.
 Linear Data structure Non-Linear Data structure

Basic In this structure, the In this structure, the elements are

elements are arranged arranged hierarchically or non-linear
sequentially or linearly manner.
and attached to one
another.

Types Arrays, linked list, stack, Trees and graphs are the types of a
queue are the types of a non-linear data structure.
linear data structure.

implementati Due to the linear Due to the non-linear organization,

on organization, they are they are difficult to implement.
easy to implement.

Traversal As linear data structure is The data items in a non-linear data

a single level, so it structure cannot be accessed in a
requires a single run to single run. It requires multiple runs
traverse each data item. to be traversed.

Arrangement Each data item is Each item is attached to many other

attached to the previous items.
and next items.

Levels This data structure does In this, the data elements are
not contain any arranged in multiple levels.
hierarchy, and all the
data elements are
organized in a single
level.

Memory In this, the memory In this, memory is utilized in a very

utilization utilization is not efficient. efficient manner.

Time The time complexity of The time complexity of non-linear

complexity linear data structure data structure often remains same
increases with the with the increase in the input size.
increase in the input size.

Applications Linear data structures Non-linear data structures are used

are mainly used for in image processing and Artificial
developing the software. Intelligence.
 Array vs Linked List
Array and Linked list are the two ways of organizing the data in the
memory. Before understanding the differences between the Array and
the Linked List, we first look at an array and a linked list.
What is an array?
An array is a data structure that contains the elements of the same type. A
data structure is a way of organizing the data; an array is a data structure
because it sequentially organizes the data. An array is a big chunk of
memory in which memory is divided into small-small blocks, and each block
is capable of storing some value.
Suppose we have created an array that consists of 10 values, then each
block will store the value of an integer type. If we try to store the value in an
array of different types, then it is not a correct array and will throw a
compile-time error.
Declaration of array
An array can be declared as:
Hello Java Program for Beginners
1. data_type name of the array[no of elements]
To declare an array, we first need to specify the type of the array and then
the array's name. Inside the square brackets, we need to specify the number
of elements that our array should contain.
Let's understand through an example.
1. int a[5];
In the above case, we have declared an array of 5 elements with 'a' name of
an integer data type.
What is Linked list?
A linked list is the collection of nodes that are randomly stored. Each node
consists of two fields, i.e., data and link. Here, data is the value stored at
that particular node, and the link is the pointer that holds the address of the
next node.
Differences between Array and Linked list
We cannot say which data structure is better, i.e., array or linked list. There
can be a possibility that one data structure is better for one kind of
requirement, while the other data structure is better for another kind of
requirement. There are various factors like what are the frequent operations
performed on the data structure or the size of the data, and other factors
also on which basis the data structure is selected. Now we will see some
differences between the array and the linked list based on some parameters.
1. Cost of accessing an element
In case of an array, irrespective of the size of an array, an array takes a
constant time for accessing an element. In an array, the elements are stored
in a contiguous manner, so if we know the base address of the element, then
we can easily get the address of any element in an array. We need to
perform a simple calculation to obtain the address of any element in an
array. So, accessing the element in an array is O(1) in terms of time
complexity.

In the linked list, the elements are not stored in a contiguous manner. It
consists of multiple blocks, and each block is represented as a node. Each
node has two fields, i.e., one is for the data field, and another one stores the
address of the next node. To find any node in the linked list, we first need to
determine the first node known as the head node. If we have to find the
second node in the list, then we need to traverse from the first node, and in
the worst case, to find the last node, we will be traversing all the nodes. The
average case for accessing the element is O(n).
We conclude that the cost of accessing an element in array is less than the
linked list. Therefore, if we have any requirement for accessing the elements,
then array is a better choice.
2. Cost of inserting an element
There can be three scenarios in the insertion:
o Inserting the element at the beginning: To insert the new element at the
beginning, we first need to shift the element towards the right to create a
space in the first position. So, the time complexity will be proportional to the
size of the list. If n is the size of the array, the time complexity would be O(n).

In the case of a linked list, to insert an element at the starting of the linked
list, we will create a new node, and the address of the first node is added to
the new node. In this way, the new node becomes the first node. So, the time
complexity is not proportional to the size of the list. The time complexity
would be constant, i.e., O(1).

o Inserting an element at the end

If the array is not full, then we can directly add the new element through the
index. In this case, the time complexity would be constant, i.e., O(1). If the
array is full, we first need to copy the array into another array and add a new
element. In this case, the time complexity would be O(n).
To insert an element at the end of the linked list, we have to traverse the
whole list. If the linked list consists of n elements, then the time complexity
would be O(n).
o Inserting an element at the mid
Suppose we want to insert the element at the i th position of the array; we
need to shift the n/2 elements towards the right. Therefore, the time
complexity is proportional to the number of the elements. The time
complexity would be O(n) for the average case.

In the case of linked list, we have to traverse to that position where we have
to insert the new element. Even though, we do not have to perform any kind
of shifting, but we have to traverse to n/2 position. The time taken is
proportional to the n number of elements, and the time complexity for the
average case would be O(n).

The resultant linked list is:

o Ease of use
The implementation of an array is easy as compared to the linked list. While
creating a program using a linked list, the program is more prone to errors
like segmentation fault or memory leak. So, lots of care need to be taken
while creating a program in the linked list.
o Dynamic in size
The linked list is dynamic in size whereas the array is static. Here, static
doesn't mean that we cannot decide the size at the run time, but we cannot
change it once the size is decided.
3. Memory requirements
As the elements in an array store in one contiguous block of memory, so
array is of fixed size. Suppose we have an array of size 7, and the array
consists of 4 elements then the rest of the space is unused. The memory
occupied by the 7 elements:

Memory space = 7*4 = 28 bytes

Where 7 is the number of elements in an array and 4 is the number of bytes
of an integer type.
In case of linked list, there is no unused memory but the extra memory is
occupied by the pointer variables. If the data is of integer type, then total
memory occupied by one node is 8 bytes, i.e., 4 bytes for data and 4 bytes
for pointer variable. If the linked list consists of 4 elements, then the memory
space occupied by the linked list would be:
Memory space = 8*4 = 32 bytes
The linked list would be a better choice if the data part is larger in size.
Suppose the data is of 16 bytes. The memory space occupied by the array
would be 16*7=112 bytes while the linked list occupies 20*4=80, here we
have specified 20 bytes as 16 bytes for the size of the data plus 4 bytes for
the pointer variable. If we are choosing the larger size of data, then the
linked list would consume a less memory; otherwise, it depends on the
factors that we are adopting to determine the size.
Let's look at the differences between the array and linked list in a
tabular form.

Array Linked list

An array is a collection of elements of a A linked list is a collection of objects known

similar data type. as a node where node consists of two
parts, i.e., data and address.

Array elements store in a contiguous Linked list elements can be stored

memory location. anywhere in the memory or randomly
stored.

Array works with a static memory. Here The Linked list works with dynamic
static memory means that the memory memory. Here, dynamic memory means
size is fixed and cannot be changed at that the memory size can be changed at
the run time. the run time according to our
requirements.

Array elements are independent of each Linked list elements are dependent on
 other. each other. As each node contains the
address of the next node so to access the
next node, we need to access its previous
node.

Array takes more time while performing Linked list takes less time while performing
any operation like insertion, deletion, etc. any operation like insertion, deletion, etc.

Accessing any element in an array is Accessing an element in a linked list is

faster as the element in an array can be slower as it starts traversing from the first
directly accessed through the index. element of the linked list.

In the case of an array, memory is In the case of a linked list, memory is

allocated at compile-time. allocated at run time.

Memory utilization is inefficient in the Memory utilization is efficient in the case of

array. For example, if the size of the a linked list as the memory can be
array is 6, and array consists of 3 allocated or deallocated at the run time
elements only then the rest of the space according to our requirement.
will be unused.

Stack vs. Queue

First, we will look at what is stack and what is queue individually, and
then we will discuss the differences between stack and queue.
What is a Stack?
A Stack is a linear data structure. In case of an array, random access is
possible, i.e., any element of an array can be accessed at any time, whereas
in a stack, the sequential access is only possible. It is a container that follows
the insertion and deletion rule. It follows the principle LIFO (Last In First
Out) in which the insertion and deletion take place from one side known as
a top. In stack, we can insert the elements of a similar data type, i.e., the
different data type elements cannot be inserted in the same stack. The two
operations are performed in LIFO, i.e., push and pop operation.
The following are the operations that can be performed on the
stack:
o push(x): It is an operation in which the elements are inserted at the top of
the stack. In the push function, we need to pass an element which we want
to insert in a stack.
o pop(): It is an operation in which the elements are deleted from the top of
the stack. In the pop() function, we do not have to pass any argument.
o peek()/top(): This function returns the value of the topmost element
available in the stack. Like pop(), it returns the value of the topmost element
but does not remove that element from the stack.
o isEmpty(): If the stack is empty, then this function will return a true value or
else it will return a false value.
o isFull(): If the stack is full, then this function will return a true value or else it
will return a false value.
In stack, the top is a pointer which is used to keep track of the last inserted
element. To implement the stack, we should know the size of the stack. We
need to allocate the memory to get the size of the stack. There are two ways
to implement the stack:
17.2M
356
Java Try Catch
o Static: The static implementation of the stack can be done with the help of
arrays.
o Dynamic: The dynamic implementation of the stack can be done with the
help of a linked list.
What is the Queue?
A Queue is a linear data structure. It is an ordered list that follows the
principle FIFO (First In -First Out). A Queue is a structure that follows some
restrictions on insertion and deletion. In the case of Queue, insertion is
performed from one end, and that end is known as a rear end. The deletion
is performed from another end, and that end is known as a front end. In
Queue, the technical words for insertion and deletion
are enqueue() and dequeue(), respectively whereas, in the case of the
stack, the technical words for insertion and deletion are push() and pop(),
respectively. Its structure contains two pointers front pointer and rear
pointer, where the front pointer is a pointer that points to the element that
was first added in the queue and the rear pointer that points to the element
inserted last in the queue.

Similarities between stack and queue.

There are two similarities between the stack and queue:
o Linear data structure
Both the stack and queue are the linear data structure, which means that the
elements are stored sequentially and accessed in a single run.
o Flexible in size
Both the stack and queue are flexible in size, which means they can grow and
shrink according to the requirements at the run-time.
Differences between stack and queue
The following are the differences between the stack and queue:
Stack Queue
Basis for
comparison

Principle It follows the principle LIFO It follows the principle FIFO (First In -
(Last In- First Out), which First Out), which implies that the
implies that the element element which is added first would
which is inserted last would be the first element to be removed
be the first one to be from the list.
deleted.

Structure It has only one end from It has two ends, i.e., front and rear
which both the insertion and end. The front end is used for the
deletion take place, and that deletion while the rear end is used
end is known as a top. for the insertion.

Number of It contains only one pointer It contains two pointers front and
pointers used known as a top pointer. The rear pointer. The front pointer holds
top pointer holds the address the address of the first element,
of the last inserted or the whereas the rear pointer holds the
topmost element of the address of the last element in a
stack. queue.

Operations It performs two operations, It performs mainly two operations,

performed push and pop. The push enqueue and dequeue. The enqueue
operation inserts the element operation performs the insertion of
in a list while the pop the elements in a queue while the
operation removes the dequeue operation performs the
element from the list. deletion of the elements from the
 queue.

Examination of If top==-1, which means that If front== -1 or front = rear+1,

the empty the stack is empty. which means that the queue is
condition empty.

Examination of If top== max-1, this If rear==max-1, this condition

full condition condition implies that the implies that the stack is full.
stack is full.

Variants It does not have any types. It is of three types like priority
queue, circular queue and double
ended queue.

Implementatio It has a simpler It has a comparatively complex

n implementation. implementation than a stack.

Visualization A Stack is visualized as a A Queue is visualized as a horizontal

vertical collection. collection.

Linear vs Circular Queue

What is a Linear Queue?
A linear queue is a linear data structure that serves the request first, which
has been arrived first. It consists of data elements which are connected in a
linear fashion. It has two pointers, i.e., front and rear, where the insertion
takes place from the front end, and deletion occurs from the front end.

Operations on Linear Queue

There are two operations that can be performed on a linear queue:
o Enqueue: The enqueue operation inserts the new element from the rear
end.
o Dequeue: The dequeue operation is used to delete the existing element
from the front end of the queue.
What is a Circular Queue?
As we know that in a queue, the front pointer points to the first element
while the rear pointer points to the last element of the queue. The problem
that arises with the linear queue is that if some empty cells occur at the
beginning of the queue then we cannot insert new element at the empty
space as the rear cannot be further incremented.
A circular queue is also a linear data structure like a normal queue that
follows the FIFO principle but it does not end the queue; it connects the last
position of the queue to the first position of the queue. If we want to insert
new elements at the beginning of the queue, we can insert it using the
circular queue data structure.
22.5M
429
Difference between JDK, JRE, and JVM
In the circular queue, when the rear reaches the end of the queue, then rear
is reset to zero. It helps in refilling all the free spaces. The problem of
managing the circular queue is overcome if the first position of the queue
comes after the last position of the queue.

Conditions for the queue to be a circular queue

o Front ==0 and rear=n-1
o Front=rear+1
If either of the above conditions is satisfied means that the queue is a
circular queue.
Operations on Circular Queue
The following are the two operations that can be performed on a circular
queue are:
 o Enqueue: It inserts an element in a queue. The given below are the
scenarios that can be considered while inserting an element:
1. If the queue is empty, then the front and rear are set to 0 to insert a
new element.
2. If queue is not empty, then the value of the rear gets incremented.
3. If queue is not empty and rear is equal to n-1, then rear is set to 0.
o Dequeue: It performs a deletion operation in the Queue. The following are
the points or cases that can be considered while deleting an element:
1. If there is only one element in a queue, after the dequeue operation is
performed on the queue, the queue will become empty. In this case,
the front and rear values are set to -1.
2. If the value of the front is equal to n-1, after the dequeue operation is
performed, the value of the front variable is set to 0.
3. If either of the above conditions is not fulfilled, then the front value is
incremented.
Differences between linear Queue and Circular Queue

Basis of Linear Queue Circular Queue

comparison

Meaning The linear queue is a type of The circular queue is also a linear data
linear data structure that structure in which the last element of
contains the elements in a the Queue is connected to the first
sequential manner. element, thus creating a circle.

Insertion In linear queue, insertion is In circular queue, the insertion and

and Deletion done from the rear end, and deletion can take place from any end.
deletion is done from the front
end.
Memory The memory space occupied It requires less memory as compared to
space by the linear queue is more linear queue.
than the circular queue.

Memory The usage of memory is The memory can be more efficiently

utilization inefficient. utilized.

Order of It follows the FIFO principle in It has no specific order for execution.
execution order to perform the tasks.
Let's look at the differences in a tabular form.

Basis of Linear search Binary search

comparison

Definition The linear search starts It finds the position of the

searching from the first searched element by finding
element and compares each the middle element of the
element with a searched array.
element till the element is not
found.

Sorted data In a linear search, the The pre-condition for the

elements don't need to be binary search is that the
arranged in sorted order. elements must be arranged
in a sorted order.

Implementati The linear search can be The implementation of binary

on implemented on any linear search is limited as it can be
data structure such as an implemented only on those
array, linked list, etc. data structures that have
two-way traversal.

Approach It is based on the sequential It is based on the divide and

approach. conquer approach.

Size It is preferrable for the small- It is preferrable for the large-

sized data sets. size data sets.

Efficiency It is less efficient in the case of It is more efficient in the case

large-size data sets. of large-size data sets.

Worst-case In a linear search, the worst- In a binary search, the worst-

scenario case scenario for finding the case scenario for finding the
element is O(n). element is O(log2n).

Best-case In a linear search, the best- In a binary search, the best-

 scenario case scenario for finding the case scenario for finding the
first element in the list is O(1). first element in the list is
O(1).

Dimensional It can be implemented on both It can be implemented only

array a single and multidimensional on a multidimensional array.
array.

Singly Linked List vs Doubly Linked List

What is a singly linked list?
A singly linked list can be simply called a linked list. A singly linked list is a
list that consists of a collection of nodes, and each node has two parts; one
part is the data part, and another part is the address. The singly linked can
also be called a chain as each node refers to another node through its
address part. We can perform various operations on a singly linked list like
insertion, deletion, and traversing.

What is a doubly-linked list?

A doubly linked list is another type of the linked list. It is called a doubly
linked list because it contains two addresses while a singly linked list
contains a single address. It is a list that has total three parts, one is a data
part, and others two are the pointers, i.e., previous and next. The previous
pointer holds the address of the previous node, and the next pointer holds
the address of the next node. Therefore, we can say that list has two
references, i.e., forward and backward reference to traverse in either
direction.
We can also perform various operations on a doubly-linked list like insertion,
deletion, and traversing.
History of Java
Differences between the singly-linked list and doubly linked list.

The differences between the singly-linked list and doubly linked list are given
below:
o Definition
The singly-linked is a linear data structure that consists of a collection of
nodes in which one node consists of two parts, i.e., one is the data part, and
another one is the address part. In contrast, a doubly-linked list is also a
linear data structure in which the node consists of three parts, i.e., one is the
data part, and the other two are the address parts.
o Direction
As we know that in a singly linked list, a node contains the address of the
next node, so the elements can be traversed in only one direction, i.e.,
forward direction. In contrast, in a doubly-linked list, the node contains two
pointers (previous pointer and next pointer) that hold the address of the
next node and the address of the previous node, respectively so
elements can be traversed in both directions.
o Memory space
The singly linked list occupies less memory space as it contains a single
address. We know that the pointer variable stores the address, and the
pointer variable occupies 4 bytes; therefore, the memory space occupied by
the pointer variable in the singly linked list is also 4 bytes. The doubly linked
list holds two addresses in a node, one is of the next node and the other one
is of the previous node; therefore, the space occupied by the two pointer
variables is 8 bytes.
o Insertion and Deletion
The insertion and deletion in a singly-linked list are less complex than a
doubly linked list. If we insert an element in a singly linked list then we need
to update the address of only next node. On the other hand, in the doubly
linked list, we need to update the address of both the next and the previous
node.
Let's look at the differences in a tabular form.

Basis of Singly linked list Doubly linked list

comparison

Definition A single linked list is a A doubly linked list is also a collection

list of nodes in which of nodes in which node has three
node has two parts, the fields, the first field is the pointer
first part is the data part, containing the address of the previous
and the next part is the node, the second is the data field, and
pointer pointing to the the third is the pointer containing the
next node in the address of the next node.
sequence of nodes.

Access The singly linked list can The doubly linked list can be accessed
be traversed only in the in both directions.
forward direction.

List It requires only one list It requires two list pointer

pointer pointer variable, i.e., the variables, head and last. The head
head pointer pointing to pointer points to the first node, and
the first node. the last pointer points to the last node
of the list.

Memory It utilizes less memory It utilizes more memory space.

space space.

Efficiency It is less efficient as It is more efficient.

compared to a doubly-
linked list.

Implement It can be implemented It can be implemented on stack, heap

ation on the stack. and binary tree.

Complexity In a singly linked list, the In a doubly-linked list, the time

time complexity for complexity for inserting and deleting
inserting and deleting an an element is O(1).
element from the list
is O(n).

Binary tree vs Binary Search tree

What is a Binary tree?
A Binary tree is a non-linear data structure in which a node can have
either 0, 1 or maximum 2 nodes. Each node in a binary tree is represented
either as a parent node or a child node. There can be two children of the
parent node, i.e., left child and right child.
There is only one way to reach from one node to its next node in a binary
tree.
A node in a binary tree has three fields:tay
o Pointer to the left child: It stores the reference of the left-child node.
o Pointer to the right child: It stores the reference of the right-child node.
o Data element: The data element is the value of the data which is stored by
the node.
The binary tree can be represented as:

In the above figure, we can observe that each node contains utmost 2
children. If any node does not contain left or right child then the value of the
pointer with respect to that child would be NULL.
Basic terminologies used in a Binary tree are:
o Root node: The root node is the first or the topmost node in a binary tree.
o Parent node: When a node is connected to another node through edges,
then that node is known as a parent node. In a binary tree, parent node can
have a maximum of 2 children.
o Child node: If a node has its predecessor, then that node is known as
a child node.
o Leaf node: The node which does not contain any child known as a leaf
node.
o Internal node: The node that has atleast 2 children known as an internal
node.
o Depth of a node: The distance from the root node to the given node is
known as a depth of a node. We provide labels to all the nodes like root
node is labeled with 0 as it has no depth, children of the root nodes are
labeled with 1, children of the root child are labeled with 2.
o Height: The longest distance from the root node to the leaf node is
the height of the node.
In a binary tree, there is one tree known as a perfect binary tree. It is
a tree in which all the internal nodes must contain two nodes, and all the leaf
nodes must be at the same depth. In the case of a perfect binary tree, the
total number of nodes exist in a binary tree can be calculated by using the
following equation:
n = 2m+1-1
where n is the number of nodes, m is the depth of a node.
What is a Binary Search tree?
A Binary search tree is a tree that follows some order to arrange the
elements, whereas the binary tree does not follow any order. In a Binary
search tree, the value of the left node must be smaller than the parent node,
and the value of the right node must be greater than the parent node.
Let's understand the concept of a binary search tree through
examples.

In the above figure, we can observe that the value of the root node is 15,
which is greater than the value of all the nodes in the left subtree. The value
of root node is less than the values of all the nodes in a right-subtree. Now,
we move to the left-child of the root node. 10 is greater than 8 and lesser
than 12; it also satisfies the property of the Binary search tree. Now, we
move to the right-child of the root node; the value 20 is greater than 17 and
lesser than 25; it also satisfies the property of binary search tree. Therefore,
we can say that the tree shown above is the binary search tree.
Now, if we change the value of 12 to 16 in the above binary tree, we have to
find whether it is still a binary search tree or not.

The value of the root node is 15 which is greater than 10 but lesser than 16,
so it does not satisfy the property of the Binary search tree. Therefore, it is
not a binary search tree.
Operations on Binary search tree
We can perform insert, delete and search operations on the binary search
tree. Let's understand how a search is performed on a binary search. The
binary tree is shown below on which we have to perform the search
operation:

Suppose we have to search 10 in the above binary tree. To perform the

binary search, we will consider all the integers in a sorted array. First, we
create a complete list in a search space, and all the numbers will exist in the
search space. The search space is marked by two pointers, i.e., start and
end. The array of the above binary tree can be represented as

First, we will calculate the middle element and compare the middle element
with the element, which is to be searched. The middle element is calculated
by using n/2. The value of n is 7; therefore, the middle element is 15. The
middle element is not equal to the searched element, i.e., 10.
Note: If the element is being searched is lesser than the mid element, then the
searching will be performed in the left half; else, searching will be done on the right
half. In the case of equality, the element is found.
As the element to be searched is lesser than the mid element, so searching
will be performed on the left array. Now the search is reduced to half, as
shown below:

The mid element in the left array is 10, which is equal to the searched
element.
Time complexity
In a binary search, there are n elements. If the middle element is not equal
to the searched element, then the search space is reduced to n/2, and we
will keep on reducing the search space by n/2 until we found the element. In
the whole reduction, if we move from n to n/2 to n/4 and so on, then it will
take log2n steps.
Differences between Binary tree and Binary search tree

Basis for Binary tree Binary search tree

comparison

Definition A binary tree is a non-linear data

structure in which a node can have
utmost two children, i.e., a node can
have 0, 1 or maximum two children. A
binary search tree is an ordered binary
tree in which some order is followed to
organize the nodes in a tree.

Structure The structure of the binary tree is that The binary search tree is one of
the first node or the topmost node is the types of binary tree that has
known as the root node. Each node in the value of all the nodes in the
a binary tree contains the left pointer left subtree lesser or equal to
and the right pointer. The left pointer the root node, and the value of
contains the address of the left all the nodes in a right subtree
subtree, whereas right pointer are greater than or equal to the
contains the address of right subtree. value of the root node.

Operations The operations that can be Binary search trees are the
implemented on a binary tree are sorted binary trees that provide
insertion, deletion, and traversal. fast insertion, deletion and
search. Lookups mainly
implement binary search as all
the keys are arranged in sorted
order.

types Four types of binary trees are Full There are different types of
Binary Tree, Complete Binary Tree, binary search trees such as AVL
Perfect Binary Tree, and Extended trees, Splay tree, Tango trees,
Binary Tree. etc.

What is Tree?
A tree is a non-linear data structure that represents the hierarchy. A tree is a
collection of nodes that are linked together to form a hierarchy.
17.7M
367
HTML Tutorial
Let's look at some terminologies used in a tree data structure.
o Root node: The topmost node in a tree data structure is known as a root
node. A root node is a node that does not have any parent.
o Parent of a node: The immediate predecessor of a node is known as a
parent of a node. Here predecessor means the previous node of that
particular node.
 o Child of a node: The immediate successor of a node is known as a child of
a node.
o Leaf node: The leaf node is a node that does not have any child node. It is
also known as an external node.
o Non-leaf node: The non-leaf node is a node that has atleast one child node.
It is also known as an internal node.
o Path: It is a sequence of the consecutive edges from a source node to the
destination node. Here edge is a link between two nodes.
o Ancestor: The predecessor nodes that occur in the path from the root to that
node is known as an ancestor.
o Descendant: The successor nodes that exist in the path from that node to
the leaf node.
o Sibling: All the children that have the same parent node are known as
siblings.
o Degree: The number of children of a particular node is known as a degree.
o Depth of node: The length of the path from the root to that node is known
as a depth of a node.
o Height of a node: The number of edges that occur in the longest path from
that node to the leaf node is known as the height of a node.
o Level of node: The number of edges that exist from the root node to the
given node is known as a level of a node.
Note: If there are n number of nodes in the tree, then there would be (n-1) number of
edges.
How is a tree represented in the memory?
Each node will contain three parts, data part, address of the left subtree, and
address of the right subtree. If any node does not have the child, then both
link parts will have NULL values.

What is a Graph?
A graph is like a tree data structure is a collection of objects or entities
known as nodes that are connected to each other through a set of edges. A
tree follows some rule that determines the relationship between the nodes,
whereas graph does not follow any rule that defines the relationship among
the nodes. A graph contains a set of edges and nodes, and edges can
connect the nodes in any possible way.
Mathematically, it can be defined as an ordered pair of a set of vertices, and
a set of nodes where vertices are represented by 'V' and edges are
represented by 'E'.
G= (V , E)
Here we are referring to an ordered pair because the first object must be the
set of vertices, and the second object must be a set of edges.
In Graph, each node has a different name or index to uniquely identify each
node in the graph. The graph shown below has eight vertices named as v1,
v2, v3, v4, v5, v6, v7, and v8. There is no first node, a second node, a third
node and so on. There is no ordering of the nodes. Now, we will see how can
we represent the edges in a graph?. An edge can be represented by the two
endpoints in the graph. We can write the name of the two endpoints as a
pair, that represents the edge in a graph.
There are two types of edges:
o Directed edge: The directed edge represents one endpoint as an origin and
another point as a destination. The directed edge is one-way. For example,
there are two vertices U and V; then directed edge would represent the link
or path from U to V, but no path exists from V to U. If we want to create a
path from V to U, then we need to have one more directed edge from V to U.
The directed edge can be represented as an ordered pair in which the first
element is the origin, whereas the second element is the destination.
o Undirected edge: The undirected edge is two-way means that there is
no origin and destination. For example, there are two vertices U and V,
then undirected would represent two paths, i.e., from U to V as well as from V
to U. An undirected edge can be represented as an unordered pair because
the edge is bi-directional.
The tree data structure contains only directed edges, whereas the graph can
have both types of edges, i.e., directed as well as undirected. But, we
consider the graph in which all the edges are either directed edges or
undirected edges.
There are two types of graphs:
Directed graph: The graph with the directed edges known as a directed
graph.

Undirected graph: The graph with the undirected edges known as

a undirected graph. The directed graph is a graph in which all the edges
are uni-directional, whereas the undirected graph is a graph in which all the
edges are bi-directional.
Differences between tree and graph data structure.

Basis for Tree Graph

comparison

Definition Tree is a non-linear data structure in A Graph is also a non-linear data

which elements are arranged in structure.
multiple levels.

Structure It is a collection of edges and nodes. It is a collection of vertices and

For example, node is represented by edges. For example, vertices are
N and edge is represented as E, so it represented by V, and edge is
can be written as: represented as 'E', so it can be
T = {N,E} written as:
T = {V, E}

Root node In tree data structure, there is a In graph data structure, there is
unique node known as a parent node. no unique node.
It represents the topmost node in the
tree data structure.

Loop It does not create any loop or cycle. In graph, loop or cycle can be
formation formed.

Model type It is a hierarchical model because It is a network model. For

nodes are arranged in multiple level, example, facebook is a social
and that creates a hierarchy. For network that uses the graph data
example, any organization will have a structure.
hierarchical model.

Edges If there are n nodes then there would The number of edges depends
be n-1 number of edges. on the graph.

Type of Tree data structure will always have In graph data structure, all the
edge directed edges. edges can either be directed
edges, undirected edges, or
 both.

Applications It is used for inserting, deleting or It is mainly used for finding the
searching any element in tree. shortest path in the network.

What is a Binary Search Tree?

The binary search tree is a tree data structure that follows the condition of
the binary tree. As we know, that tree can have 'n' number of children,
whereas; the binary tree can contain the utmost two children. So, the
constraint of a binary tree is also followed by the binary search tree. Each
node in a binary search tree should have the utmost two children; in other
words, we can say that the binary search tree is a variant of the binary tree.
The binary search tree also follows the properties of the binary search. In
binary search, all the elements in an array must be in sorted order. We
calculate the middle element in the binary search in which the left part of the
middle element contains the value lesser than the middle value, and the
right part of the middle element contains the values greater than the middle
value.
In Binary Search Tree, the middle element becomes the root node, the right
part becomes the right subtree, and the left part becomes the left subtree.
Therefore, we can say that the binary search tree is a combination of
a binary tree and binary search.
21.3M
467
C++ vs Java
Note: Binary Search Tree can be defined as the binary tree in which all the elements
of the left subtree are less than the root node, and all the elements of the right
subtree are greater than the root node.
Time Complexity in Binary Search Tree
If the binary search tree is almost a balanced tree then all the operations will
have a time complexity of O(logn) because the search is divided either to
the left or the right subtree.
If the binary search tree is either left or right-skewed, then all the operations
will have the time complexity of O(n) because we need to traverse till the n
elements.
What is the AVL Tree?
An AVL tree is a self-balancing binary search tree where the difference
between heights of left and right subtrees cannot be more than one. This
difference is known as a balance factor. In the AVL tree, the values of
balance factor could be either -1, 0 or 1.
How does the self-balancing of the binary search tree happen?
As we know that AVL tree is a self-balancing binary search tree. If the binary
search tree is not balanced, it can be self-balanced with some re-
arrangements. These re-arrangements can be done using some rotations.
Let's understand self-balancing through an example.
Suppose we want to insert 10, 20, 30 in an AVL tree.
The following are the ways of inserting 10, 20, 30 in an AVL tree:
o If the order of insertion is 30, 20, 10.
Step 1: First, we create a Binary search tree, as shown below:

Step 2: In the above figure, we can observe that tree is unbalanced because
the balance factor of node 30 is 2. In order to make it an AVL tree, we need
to perform some rotations. If we perform the right rotation on node 20 then
the node 30 will move downwards, whereas the node 20 will move upwards,
as shown below:

As we can observe, the final tree follows the property of the Binary Search
tree and a balanced tree; therefore, it is an AVL tree.
In the case, the tree was left unbalanced tree, so we perform the right
rotation on the node.
o If the order of insertion is 10, 20, 30.
Step 1: First we create a Binary search tree as shown below:

Step 2: In the above figure, we can observe that the tree is unbalanced
because the balance factor of node 10 is -2. In order to make it an AVL tree,
we need to perform some rotations. It is a right unbalanced tree, so we will
perform left rotation. If we perform left rotation on node 20, then the node
20 will move upwards, and node 10 will move downwards, as shown below:
As we can observe, the final tree follows the property of the Binary Search
tree and a balanced tree; therefore, it is an AVL tree.
o If the order of insertion is 30, 10, 20
Step 1: First we create the Binary Search tree as shown below:

Step 2: In the above figure, we can observe that the tree is unbalanced
because the balance factor of the root node is 2. In order to make it an AVL
tree, we need to perform some rotations. The above scenario is left-right
unbalanced as one node is the left of its parent node and another is the right
of its parent node. First, we will perform the left rotation, and rotation
happens between nodes 10 and 20. After left rotation, 20 will move upwards,
and 10 will move downwards as shown below:

Still, the tree is unbalanced, so we perform the right rotation on the tree.
Once the right rotation is performed on the tree, then the tree would like, as
shown below:

As we can observe in the above tree, the tree follows the property of the
Binary Search tree and a balanced tree; therefore, it is an AVL tree.
o If the order of the insertion is 10, 30, 20
Step 1: First, we create the Binary Search tree, as shown below:

Step 2: In the above figure, we can observe that tree is unbalanced because
the balance factor of the root node is 2. In order to make it an AVL tree, we
need to perform some rotations. The above scenario is right-left unbalanced
as one node is right of its parent node, and another node is left of its parent
node. First, we will perform the right rotation that happens between nodes
30 and 20. After right rotation, 20 will move upwards, and 30 will move
downwards as shown below:

Still, the above tree is unbalanced, so we need to perform left rotation on the
node. Once the left rotation is performed, the node 20 will move upwards,
and node 10 will move downwards as shown below:

As we can observe in the above tree, the tree follows the property of the
Binary Search tree and a balanced tree; therefore, it is an AVL tree.
Differences between Binary Search tree and AVL tree

Binary Search tree AVL tree

Every binary search tree is a binary tree Every AVL tree is also a binary tree because
because both the trees contain the utmost AVL tree also has the utmost two children.
two children.

In BST, there is no term exists, such as In the AVL tree, each node contains a
balance factor. balance factor, and the value of the
 balance factor must be either -1, 0, or 1.

Every Binary Search tree is not an AVL tree Every AVL tree is a binary search tree
because BST could be either a balanced or because the AVL tree follows the property
an unbalanced tree. of the BST.

Each node in the Binary Search tree Each node in the AVL tree consists of four
consists of three fields, i.e., left subtree, fields, i.e., left subtree, node value, right
node value, and the right subtree. subtree, and the balance factor.

In the case of Binary Search tree, if we want In the case of AVL tree, first, we will find the
to insert any node in the tree then we suitable place to insert the node. Once the
compare the node value with the root value; node is inserted, we will calculate the
if the value of node is greater than the root balance factor of each node. If the balance
node value then the node is inserted to the factor of each node is satisfied, the
right subtree otherwise the node is inserted insertion is completed. If the balance factor
to the left subtree. Once the node is is greater than 1, then we need to perform
inserted, there is no need of checking the some rotations to balance the tree.
height balance factor for the insertion to be
completed.

In Binary Search tree, the height or depth of In AVL tree, the height or depth of the tree
the tree is O(n) where n is the number of is O(logn).
nodes in the Binary Search tree.

It is simple to implement as we have to It is complex to implement because in AVL

follow the Binary Search properties to insert tree, we have to first construct the AVL
the node. tree, and then we need to check height
balance. If the height is imbalance then we
need to perform some rotations to balance
the tree.

BST is not a balanced tree because it does AVL tree is a height balanced tree because
not follow the concept of the balance factor. it follows the concept of the balance factor.

Searching is inefficient in BST when there Searching is efficient in AVL tree even when
are large number of nodes available in the there are large number of nodes in the tree
tree because the height is not balanced. because the height is balanced.
The Red-Black tree is a binary search tree, and the AVL tree is also a binary
search tree.
o Rules
The following rules are applied in a Red-Black Tree:
1. The node in a Red-Black tree is either red or black in color.
2. The color of the root node should be black.
3. The adjacent nodes should not be red. In other words, we can say that
the red node cannot have red children, but the black node can have
black children.
 4. There should be the same number of black nodes in every path; then,
only a tree can be considered a Red-Black tree.
5. The external nodes are the nil nodes, which are always black in color.
Rule of the AVL tree:
Every node should have the balance factor either as -1, 0 or 1.
o Example

In the above figure, we need to check whether the tree is a Red-Black tree or
not. In order to check this, first, we need to check whether the tree is a
binary search tree or not. As we can observe in the above figure that it
satisfies all the properties of the binary search tree; therefore, it is a binary
search tree. Secondly, we have to verify whether it satisfies the above-said
rules or not. The above tree satisfies all the above five rules; therefore, it
concludes that the above tree is a Red-Black tree.

In the above figure, we need to check whether the tree is an AVL tree or not.
As each node has a value of balance factor either as -1, 0, or 1, so it is an
AVL tree.
o How can the tree be considered as a balanced tree or not?
In the case of a Red-Black tree, if all the above rules are satisfied, provided
that a tree is a binary search tree, then the tree is said to be a Red-black
tree.
In the case of the AVL tree, if the balance factor is -1, 0, or 1, then the above
tree is said to be an AVL tree.
o Tools used for balancing
If the tree is not balanced, then two tools are used for balancing the tree in a
Red-Black tree:
1. Recoloring
 2. Rotation
If the tree is not balanced, then one tool is used for balancing the tree in the
AVL tree:
1. Rotation
o Efficient for which operation
In the case of the Red-Black tree, the insertion and deletion operations are
efficient. If the tree gets balanced through the recoloring, then insertion and
deletion operations are efficient in the Red-Black tree.
In the case of the AVL tree, the searching operation is efficient as it requires
only one tool to balance the tree.
o Time complexity
In the Red-Black tree case, the time complexity for all the operations, i.e.,
insertion, deletion, and searching is O(logn).
In the case of AVL tree, the time complexity for all the operations, i.e.,
insertion, deletion, and searching is O(logn).
Let's understand the differences in the tabular form.

Parameter Red Black Tree AVL Tree

Searching Red Black tree does not AVL trees provide efficient
provide efficient searching as searching as it is strictly
Red Black Trees are roughly balanced tree.
balanced.

Insertion Insertion and Deletion are Insertion and Deletion are

and easier in Red Black tree as it complex in AVL tree as it
Deletion requires fewer rotations to requires multiple rotations to
balance the tree. balance the tree.

Color of In the Red-Black tree, the color In the case of AVL trees, there
the node of the node is either Red or is no color of the node.
Black.

Balance It does not contain any balance Each node has a balance
factor factor. It stores only one bit of factor in AVL tree whose value
information that denotes either can be 1, 0, or -1. It requires
Red or Black color of the node. extra space to store the
balance factor per node.

Strictly Red-black trees are not strictly AVL trees are strictly balanced,
balanced balanced. i.e., the left subtree's height
and the height of the right
subtree differ by at most 1.
B tree vs B+ tree
Before understanding B tree and B+ tree differences, we should know the B
tree and B+ tree separately.
What is the B tree?
B tree is a self-balancing tree, and it is a m-way tree where m defines the
order of the tree. Btree is a generalization of the Binary Search tree in which
a node can have more than one key and more than two children depending
upon the value of m. In the B tree, the data is specified in a sorted order
having lower values on the left subtree and higher values in the right
subtree.
Properties of B tree
The following are the properties of the B tree:
OPs Concepts in Java
o In the B tree, all the leaf nodes must be at the same level, whereas, in the
case of a binary tree, the leaf nodes can be at different levels.
Let's understand this property through an example.

In the above tree, all the leaf nodes are not at the same level, but they have
the utmost two children. Therefore, we can say that the above tree is
a binary tree but not a B tree.
o If the Btree has an order of m, then each node can have a maximum of m In
the case of minimum children, the leaf nodes have zero children, the root
node has two children, and the internal nodes have a ceiling of m/2.
o Each node can have maximum (m-1) keys. For example, if the value of m is 5
then the maximum value of keys is 4.
o The root node has minimum one key, whereas all the other nodes except the
root node have (ceiling of m/2 minus - 1) minimum keys.
o If we perform insertion in the B tree, then the node is always inserted in the
leaf node.
Suppose we want to create a B tree of order 3 by inserting values
from 1 to 10.
Step 1: First, we create a node with 1 value as shown below:
Step 2: The next element is 2, which comes after 1 as shown below:

Step 3: The next element is 3, and it is inserted after 2 as shown below:

As we know that each node can have 2 maximum keys, so we will split this
node through the middle element. The middle element is 2, so it moves to its
parent. The node 2 does not have any parent, so it will become the root node
as shown below:

Step 4: The next element is 4. Since 4 is greater than 2 and 3, so it will be

added after the 3 as shown below:

Step 5: The next element is 5. Since 5 is greater than 2, 3 and 4 so it will be

added after 4 as shown below:

As we know that each node can have 2 maximum keys, so we will split this
node through the middle element. The middle element is 4, so it moves to its
parent. The parent is node 2; therefore, 4 will be added after 2 as shown
below:
Step 6: The next element is 6. Since 6 is greater than 2, 4 and 5, so 6 will
come after 5 as shown below:

Step 7: The next element is 7. Since 7 is greater than 2, 4, 5 and 6, so 7 will

come after 6 as shown below:

As we know that each node can have 2 maximum keys, so we will split this
node through the middle element. The middle element is 6, so it moves to its
parent as shown below:

But, 6 cannot be added after 4 because the node can have 2 maximum keys,
so we will split this node through the middle element. The middle element is
4, so it moves to its parent. As node 4 does not have any parent, node 4 will
become a root node as shown below:
What is a B+ tree?
The B+ tree is also known as an advanced self-balanced tree because every
path from the root of the tree to the leaf of the tree has the same length.
Here, the same length means that all the leaf nodes occur at the same level.
It will not happen that some of the leaf nodes occur at the third level and
some of them at the second level.
A B+ tree index is considered a multi-level index, but the B+ tree structure is
not similar to the multi-level index sequential files.
Why is the B+ tree used?
A B+ tree is used to store the records very efficiently by storing the records
in an indexed manner using the B+ tree indexed structure. Due to the multi-
level indexing, the data accessing becomes faster and easier.
B+ tree Node Structure
The node structure of the B+ tree contains pointers and key values shown in
the below figure:

As we can observe in the above B+ tree node structure that it contains n-1
key values (k1 to kn-1) and n pointers (p1 to pn).
The search key values which are placed in the node are kept in sorted order.
Thus, if i<j then ki<kj.
Constraint on various types of nodes
Let 'b' be the order of the B+ tree.
Non-Leaf node
Let 'm' represents the number of children of a node, then the relation
between the order of the tree and the number of children can be represented
as:
Let k represents the search key values. The relation between the order of the
tree and search key can be represented as:
As we know that the number of pointers is equal to the search key values
plus 1, so mathematically, it can be written as:
Number of Pointers (or children) = Number of Search keys + 1
Therefore, the maximum number of pointers would be 'b', and the minimum
number of pointers would be the ceiling function of b/2.
Leaf Node
A leaf node is a node that occurs at the last level of the B+ tree, and each
leaf node uses only one pointer to connect with each other to provide the
sequential access at the leaf level.
In leaf node, the maximum number of children is:

The maximum number of search keys is:

Root Node
The maximum number of children in the case of the root node is: b
The minimum number of children is: 2
Special cases in B+ tree
Case 1: If the root node is the only node in the tree. In this case, the root
node becomes the leaf node.
In this case, the maximum number of children is 1, i.e., the root node itself,
whereas, the minimum number of children is b-1, which is the same as that
of a leaf node.
Representation of a leaf node in B+ tree
In the above figure, '.' represents the pointer, whereas the 10, 20 and 30 are
the key values. The pointer contains the address at which the key value is
stored, as shown in the above figure.
Example of B+ tree

In the above figure, the node contains three key values, i.e., 9, 16, and 25.
The pointer that appears before 9, contains the key values less than 9
represented by ki. The pointer that appears before 16, contains the key
values greater than or equal to 9 but less than 16 represented by kj. The
pointer that appears before 25, contains the key values greater than or equal
to 16 but less than 25 represented by kn.
The following are the differences between the B tree and B+ tree:
B tree B+ tree

In the B tree, all the keys and In the B+ tree, keys are the indexes stored in the
records are stored in both internal internal nodes and records are stored in the leaf
as well as leaf nodes. nodes.

In B tree, keys cannot be In the B+ tree, there can be redundancy in the

repeatedly stored, which means occurrence of the keys. In this case, the records
that there is no duplication of are stored in the leaf nodes, whereas the keys
keys or records. are stored in the internal nodes, so redundant
keys can be present in the internal nodes.

In the Btree, leaf nodes are not In B+ tree, the leaf nodes are linked to each
linked to each other. other to provide the sequential access.

In Btree, searching is not very In B+ tree, searching is very efficient or quicker

efficient because the records are because all the records are stored in the leaf
either stored in leaf or internal nodes.
nodes.

Deletion of internal nodes is very Deletion in B+ tree is very fast because all the
slow and a time-consuming records are stored in the leaf nodes so we do not
process as we need to consider have to consider the child of the node.
the child of the deleted key also.

In Btree, sequential access is not In the B+ tree, all the leaf nodes are connected
possible. to each other through a pointer, so sequential
access is possible.

In Btree, the more number of B+ tree has more width as compared to height.
 splitting operations are performed
due to which height increases
compared to width,

In Btree, each node has atleast In B+ tree, internal nodes contain only pointers
two branches and each node and leaf nodes contain records. All the leaf nodes
contains some records, so we do are at the same level, so we need to traverse till
not need to traverse till the leaf the leaf nodes to get the data.
nodes to get the data.

The root node contains atleast 2 The root node contains atleast 2 to m children
to m children where m is the order where m is the order of the tree.
of the tree.

Difference Between Quick Sort and Merge Sort

A sorting is the arrangement of collectively data in particular format like
ascending or descending order. Generally, it is used to arrange the
homogeneous data in sorted manner. Using the sorting algorithms, we can
arrange the data in a sequence order and search an element easily and
faster. Sorting techniques depends on two situation such as total time and
total space required to execute a program. In this section, we will
discuss quick sort and merge sort and also compare them each other.
Quick Sort
Quick sort is a comparison based sorting algorithm that follows the divide and conquer
technique to sort the arrays. In quick sort, we usually use a pivot (key) element to compare
and interchange the position of the element based on some condition. When a pivot element gets
its fixed position in the array that shows the termination of comparison & interchange procedure.
After that, the array divides into the two sub arrays. Where the first partition contains all those
elements that are less than pivot (key) element and the other parts contains all those elements that
are greater than pivot element. After that, it again selects a pivot element on each of the sub
arrays and repeats the same process until all the elements in the arrays are sorted into an array.
Algorithm of Quick Sort
Partition (A, p, r)
1.X <- A[r]
2.I <- p-1
[Link] j <- p to r -1
[Link] if A[j] <= x
[Link] I <- I + 1
[Link] A[i] <-> A[j]
[Link] A[I + 1] <--> A[r]
[Link] I + 1
Quicksort (A, p, r)9MHow to find Nth Highest Salary in SQL
1. While (p < r)
2. Do q <- Partition (A, p, r)
3. R <- q-1
4. While (p < r)
 5. Do q <- Partition (A, p, r)
6. P <- q + 1
Steps to sort an array using the quick sort algorithm
Suppose, we have an array X having the elements X[1], X[2], X[3],…., X[n]
that are to be sort. Let's follow the below steps to sort an array using the
quick sort.
Step 1: Set the first element of the array as the pivot or key element. Here,
we assume pivot as X[0], left pointer is placed at the first element and
the last index of the array element as right.
Step 2: Now we starts the scanning of the array elements from right side
index, then
If X[key] is less than X[right] or if X[key] < X[Right],
1. Continuously decreases the right end pointer variable until it becomes equal
to the key.
2. If X[key] > X[right], interchange the position of the key element to the
X[right] element.
3. Set, key = right and increment the left index by 1.
Step 3: Now we again start the scanning of the element from left side and
compare each element with the key element. X[key] > X[left] or X[key] is
greater than X[left], then it performs the following actions:
1. Continuously compare the left element with the X[key] and increment the left
index by 1 until key becomes equal to the left.
2. If X[key] < X[left], interchange the position of the X[key] with X[left] and go
to step 2.
Step 4: Repeat Step 2 and 3 until the X[left] becomes equal to X[key]. So,
we can say that if X[left] = X[key], it shows the termination of the
procedures.
Step 5: After that, all the elements at the left side will be smaller than the
key element and the rest element of the right side will be larger than the key
element. Thus indicating the array needs to partitioned into two sub arrays.
Step 6: Similarly, we need to repeatedly follow the above procedure to the
sub arrays until the entire array becomes sorted.
Example: Consider an array of 6 elements. Sort the array using the
quick sort.
arr[] = {50, 20, 60, 30, 40, 56}
In the above array, 50 is in its right place. So, we divided the elements that
are less than pivot in one sub array and the elements that are larger than
the pivot element in another sub array.

Hence, we get the sorted array.

Merge sort
Merge sort is a most important sorting techniques that work on the divide and conquer
strategies. It is the most popular sorting techniques used to sort data that is externally available in
a file. The merge sort algorithm divides the given array into two halves (N/2). And then, it
recursively divides the set of two halves array elements into the single or individual elements or
we can say that until no more division can take place. After that, it compares the corresponding
element to sort the element and finally, all sub elements are combined to form the final sorted
elements.
Steps to sort an array using the Merge sort algorithm
 1. Suppose we have a given array, then first we need to divide the array into
sub array. Each sub array can store 5 elements.
2. Here we gave the first sub array name as A1 and divide into next two
subarray as B1 and B2.
3. Similarly, the right sub array name as A2 and divide it into next two sub array
as B3 and B4.
4. This process is repeated continuously until the sub array is divided into a
single element and no more partitions may be possible.
5. After that, compare each element with the corresponding one and then start
the process of merging to arrange each element in such a way that they are
placed in ascending order.
6. The merging process continues until all the elements are merged in
ascending order.
Let's see an example of merge sort.
Example: Consider an array of 9 elements. Sort the array using the
merge sort.
arr[] = {70, 80, 40, 50, 60, 11, 35, 85, 2}
Hence, we get the sorted array using the merge sort.
Quick Sort vs. Merge Sort
S.N Parameter Quick Sort Merge Sort
.

1. Definition It is a quick sort algorithm It is a merge sort algorithm that

that arranges the given arranges the given sets of elements
elements into ascending in ascending order using the divide
order by comparing and and conquer technique, and then
interchanging the position compare with corresponding
of the elements. elements to sort the array.

2. Principle It works on divide and It works on divide and conquer

conquer techniques. techniques.

3. Partition of In quick sort, the array can Merge sort partition an array into
elements be divide into any ratio. two sub array (N/2).

4. Efficiency It is more efficient and It is more efficient and work faster in

work faster in smaller size larger data sets or array, as
array, as compared to the compare to the quick sort.
merge sort.

5 Sorting It is an internal sorting It is an external sorting method that

method method that sort the array sort the array or data sets available
or data available on main on external file.
memory.

6 Time Its worst time complexity Whereas, it's worst time complexity
complexity is O (n2). is O (n log n).

7 Preferred It is a sorting algorithm Whereas, the merge sort algorithm

that is applicable for large that is preferred to sort the linked
unsorted arrays. lists.

8 Stability Quick sort is an unstable Merge sort is a stable sort algorithm

sort algorithm. But we can that contains two equal elements
made it stable by using with same values in sorted output.
some changes in
programming code.

9 Requires It does not require any It requires the additional space as

Space additional space to temporary array to merge two sub
perform the quick sort. arrays.

10. Functionali Compare each element Whereas, the merge sort splits the
ty with the pivot until all array into two parts (N/2) and it
 elements are arranged in continuously divides the array until
ascending order. an element is left.

What is BFS?
BFS stands for Breadth First Search. It is also known as level order
traversal. The Queue data structure is used for the Breadth First Search
traversal. When we use the BFS algorithm for the traversal in a graph, we
can consider any node as a root node.
Let's consider the below graph for the breadth first search traversal.

Suppose we consider node 0 as a root node. Therefore, the traversing would

be started from node [Link] of Java -

Once node 0 is removed from the Queue, it gets printed and marked as
a visited node.
Once node 0 gets removed from the Queue, then the adjacent nodes of node
0 would be inserted in a Queue as shown below:

Now the node 1 will be removed from the Queue; it gets printed and marked
as a visited node
Once node 1 gets removed from the Queue, then all the adjacent nodes of a
node 1 will be added in a Queue. The adjacent nodes of node 1 are 0, 3, 2, 6,
and 5. But we have to insert only unvisited nodes in a Queue. Since nodes 3,
2, 6, and 5 are unvisited; therefore, these nodes will be added in a Queue as
shown below:
The next node is 3 in a Queue. So, node 3 will be removed from the Queue, it
gets printed and marked as visited as shown below:

Once node 3 gets removed from the Queue, then all the adjacent nodes of
node 3 except the visited nodes will be added in a Queue. The adjacent
nodes of node 3 are 0, 1, 2, and 4. Since nodes 0, 1 are already visited, and
node 2 is present in a Queue; therefore, we need to insert only node 4 in a
Queue.

Now, the next node in the Queue is 2. So, 2 would be deleted from the
Queue. It gets printed and marked as visited as shown below:

Once node 2 gets removed from the Queue, then all the adjacent nodes of
node 2 except the visited nodes will be added in a Queue. The adjacent
nodes of node 2 are 1, 3, 5, 6, and 4. Since the nodes 1 and 3 have already
been visited, and 4, 5, 6 are already added in the Queue; therefore, we do
not need to insert any node in the Queue.
The next element is 5. So, 5 would be deleted from the Queue. It gets printed
and marked as visited as shown below:

Once node 5 gets removed from the Queue, then all the adjacent nodes of
node 5 except the visited nodes will be added in the Queue. The adjacent
nodes of node 5 are 1 and 2. Since both the nodes have already been visited;
therefore, there is no vertex to be inserted in a Queue.
The next node is 6. So, 6 would be deleted from the Queue. It gets printed
and marked as visited as shown below:

Once the node 6 gets removed from the Queue, then all the adjacent nodes
of node 6 except the visited nodes will be added in the Queue. The adjacent
nodes of node 6 are 1 and 4. Since the node 1 has already been visited and
node 4 is already added in the Queue; therefore, there is not vertex to be
inserted in the Queue.
The next element in the Queue is 4. So, 4 would be deleted from the Queue.
It gets printed and marked as visited.
Once the node 4 gets removed from the Queue, then all the adjacent nodes
of node 4 except the visited nodes will be added in the Queue. The adjacent
nodes of node 4 are 3, 2, and 6. Since all the adjacent nodes have already
been visited; so, there is no vertex to be inserted in the Queue.
What is DFS?
DFS stands for Depth First Search. In DFS traversal, the stack data structure
is used, which works on the LIFO (Last In First Out) principle. In DFS,
traversing can be started from any node, or we can say that any node can be
considered as a root node until the root node is not mentioned in the
problem.
In the case of BFS, the element which is deleted from the Queue, the
adjacent nodes of the deleted node are added to the Queue. In contrast, in
DFS, the element which is removed from the stack, then only one adjacent
node of a deleted node is added in the stack.
Let's consider the below graph for the Depth First Search traversal.
Consider node 0 as a root node.
First, we insert the element 0 in the stack as shown below:

The node 0 has two adjacent nodes, i.e., 1 and 3. Now we can take only one
adjacent node, either 1 or 3, for traversing. Suppose we consider node 1;
therefore, 1 is inserted in a stack and gets printed as shown below:

Now we will look at the adjacent vertices of node 1. The unvisited adjacent
vertices of node 1 are 3, 2, 5 and 6. We can consider any of these four
vertices. Suppose we take node 3 and insert it in the stack as shown below:

Consider the unvisited adjacent vertices of node 3. The unvisited adjacent

vertices of node 3 are 2 and 4. We can take either of the vertices, i.e., 2 or 4.
Suppose we take vertex 2 and insert it in the stack as shown below:
The unvisited adjacent vertices of node 2 are 5 and 4. We can choose either
of the vertices, i.e., 5 or 4. Suppose we take vertex 4 and insert in the stack
as shown below:

Now we will consider the unvisited adjacent vertices of node 4. The unvisited
adjacent vertex of node 4 is node 6. Therefore, element 6 is inserted into the
stack as shown below:

After inserting element 6 in the stack, we will look at the unvisited adjacent
vertices of node 6. As there is no unvisited adjacent vertices of node 6, so we
cannot move beyond node 6. In this case, we will perform backtracking.
The topmost element, i.e., 6 would popped out from the stack as shown

below:

The topmost element in the stack is 4. Since there are no unvisited adjacent
vertices left of node 4; therefore, node 4 is popped out from the stack as
shown below:
The next topmost element in the stack is 2. Now, we will look at the unvisited
adjacent vertices of node 2. Since only one unvisited node, i.e., 5 is left, so
node 5 would be pushed into the stack above 2 and gets printed as shown
below:

Now we will check the adjacent vertices of node 5, which are still unvisited.
Since there is no vertex left to be visited, so we pop the element 5 from the
stack as shown below:

We cannot move further 5, so we need to perform backtracking. In

backtracking, the topmost element would be popped out from the stack. The
topmost element is 5 that would be popped out from the stack, and we move
back to node 2 as shown below:
Now we will check the unvisited adjacent vertices of node 2. As there is no
adjacent vertex left to be visited, so we perform backtracking. In
backtracking, the topmost element, i.e., 2 would be popped out from the
stack, and we move back to the node 3 as shown below:

Now we will check the unvisited adjacent vertices of node 3. As there is no

adjacent vertex left to be visited, so we perform backtracking. In
backtracking, the topmost element, i.e., 3 would be popped out from the
stack and we move back to node 1 as shown below:
After popping out element 3, we will check the unvisited adjacent vertices of
node 1. Since there is no vertex left to be visited; therefore, the backtracking
will be performed. In backtracking, the topmost element, i.e., 1 would be
popped out from the stack, and we move back to node 0 as shown below:

We will check the adjacent vertices of node 0, which are still unvisited. As
there is no adjacent vertex left to be visited, so we perform backtracking. In
this, only one element, i.e., 0 left in the stack, would be popped out from the
stack as shown below:
As we can observe in the above figure that the stack is empty. So, we have
to stop the DFS traversal here, and the elements which are printed is the
result of the DFS traversal.
Differences between BFS and DFS
The following are the differences between the BFS and DFS:

BFS DFS

Full form BFS stands for Breadth First DFS stands for Depth First Search.
Search.

Technique It a vertex-based technique to It is an edge-based technique because

find the shortest path in a the vertices along the edge are
graph. explored first from the starting to the
end node.

Definition BFS is a traversal technique in DFS is also a traversal technique in

which all the nodes of the which traversal is started from the
same level are explored first, root node and explore the nodes as
and then we move to the next far as possible until we reach the node
level. that has no unvisited adjacent nodes.

Data Queue data structure is used Stack data structure is used for the
Structure for the BFS traversal. BFS traversal.

Backtracking BFS does not use the DFS uses backtracking to traverse all
backtracking concept. the unvisited nodes.

Number of BFS finds the shortest path In DFS, a greater number of edges are
edges having a minimum number of required to traverse from the source
edges to traverse from the vertex to the destination vertex.
source to the destination
vertex.

Optimality BFS traversal is optimal for DFS traversal is optimal for those
those vertices which are to be graphs in which solutions are away
searched closer to the source from the source vertex.
vertex.

Speed BFS is slower than DFS. DFS is faster than BFS.

Suitability It is not suitable for the It is suitable for the decision tree.
for decision decision tree because it Based on the decision, it explores all
tree requires exploring all the the paths. When the goal is found, it
neighboring nodes first. stops its traversal.

Memory It is not memory efficient as it It is memory efficient as it requires

efficient requires more memory than less memory than BFS.
DFS.