DSA

1. What is Asymptotic notation?

Ans. Asymptotic Notation is a mathematical tool
used in Data Structures and Algorithms to
describe the running time or space requirement
of an algorithm in terms of input size (n) when
the input becomes very large.
It helps in analyzing and comparing algorithms
by ignoring constant factors and focusing on the
growth rate of the algorithm's time or space
complexity.
Asymptotic Notations are mathematical tools
used to analyze the performance of
algorithms by understanding how their
efficiency changes as the input size grows.
✅ Types of Asymptotic Notation:
1. Big O Notation (O) – Worst Case
• It describes the maximum time an algorithm
can take.
• It gives an upper bound on time complexity.
2. Omega Notation (Ω) – Best Case
• It describes the minimum time an algorithm
takes.
• It gives a lower bound on time complexity.

3. Theta Notation (Θ) – Average Case

• It describes the exact or average time an
algorithm takes.
• It gives a tight bound (both upper and lower).
2. How linked list overcome the limitation of
array. Explain the types of Linked list.
Ans. Arrays have some limitations:
Limitation in Array How Linked List Solves
Linked list can
Fixed size (can’t grow
grow/shrink
or shrink)
dynamically
Inserting/deleting is Insertion/deletion is
difficult easier in linked list
Wastes memory if Linked list uses memory
extra size only when needed

✅ Example:
If you create an array of size 100, but only store
5 items, the rest is wasted.
But in a linked list, only 5 nodes will be created
— no memory is wasted.
🔗 Types of Linked List
1. Singly Linked List
• Each node stores: data + next pointer
• Goes in one direction only
Example:
[10 | next] → [20 | next] → [30 | NULL]

2. Doubly Linked List

• Each node stores: data, next pointer, previous
pointer
• Can move forward and backward
Example:
NULL ← [10 | prev | next] ↔ [20 | prev | next]
↔ [30 | prev | NULL]

3. Circular Linked List

• Last node connects to the first node
• Can be singly or doubly circular
 Example (Singly Circular):
[10 | next] → [20 | next] → [30 | next] ↺ (back
to 10)

3. What are the basic technology in data

structure?
Ans. ✅ 1. Arrays
• Store elements in fixed-size and continuous
memory
• Example:
int arr[5] = {1, 2, 3, 4, 5};

✅ 2. Linked Lists
• Elements (nodes) connected using pointers
• Can grow or shrink in size
Example:
10 → 20 → 30 → NULL
✅ 3. Stacks
• LIFO (Last In First Out)
• Use for undo, back button, etc.
Example:
Pushing values: 10, 20, 30
Popping: returns 30 first

✅ 4. Queues
• FIFO (First In First Out)
• Used in printers, task scheduling
Example:
Enqueue: A → B → C
Dequeue: returns A first

✅ 5. Trees
• Hierarchical structure (like a family tree)
• Used in searching, sorting, databases
Example:
10
/ \
5 15

✅ 6. Graphs
• Set of nodes and connections (edges)
• Used in networks, maps, social media
Example:
Cities as nodes, roads as edges

✅ 7. Hash Tables
• Store data as key-value pairs
• Fast searching
Example:
{"name": "Ishank", "age": 22}
4. Explain Space and Time complexity.
Ans.⏱️ Time Complexity – How fast an
algorithm runs
• It tells how much time an algorithm takes based
on input size (n).
• It counts the number of steps or operations.
✅ Example:
for (int i = 0; i < n; i++) {
printf("Hello");
}
This loop runs n times, so Time Complexity =
O(n)

💾 Space Complexity – How much memory an

algorithm uses
• It tells how much extra space is needed while
the algorithm runs.
• Includes memory for variables, data
structures, function calls, etc.
 ✅ Example:
int sum = 0;
for (int i = 0; i < n; i++) {
sum += i;
}
Only one variable sum is used, so Space
Complexity = O(1) (constant space)

5. Explain Linked List?

Ans. A Linked List is a linear data structure where
elements are stored in nodes, and each node is
connected to the next using pointers.
Unlike arrays, linked lists do not store elements
in contiguous memory. Instead, each node
contains:
linked lists to grow or shrink dynamically at
runtime, making them more flexible than arrays.
🔹 Types of Linked List:

1. ✅ Singly Linked List

• Each node points to the next node
• Traversal is in one direction only (forward)
• The last node points to NULL
📌 Example:
[10 | next] → [20 | next] → [30 | NULL]
• Singly Linked List: Playlist of songs (next song
only)

2. ✅ Doubly Linked List

• Each node has two pointers:
• Can be traversed in both directions
📌 Example:
NULL ← [10 | prev | next] ↔ [20 | prev | next]
• Doubly Linked List: Web browser history
(forward & backward)
3. ✅ Circular Linked List
• The last node connects back to the first node
• There is no NULL at the end
📌 Example (Singly Circular):
[10 | next] → [20 | next] → [30 | next] ┐
↑___________________________ ┘
• Circular Linked List: Multiplayer games (turn
rotation)
UNIT -2

6. Difference between Stack and Queue?

Ans.
Stack Queue
Follows LIFO (Last In First Follows FIFO (First In
Out) First Out)
The first element
The last element added is
added is removed
removed first
first
Uses two pointers
Uses one pointer (Top)
(Front and Rear)
Insertion and deletion
Insertion at Rear,
happen at the same end
Deletion at Front
(Top)
Also implemented
Easy to implement using
using array or linked
array or linked list
list
Stack Queue
Used for job
Used for function calls,
scheduling, queues in
undo, recursion
OS
Supports operations:
Supports operations:
enqueue, dequeue,
push, pop, peek
front
Less suitable for fair Maintains fair order
processing order of processing tasks
Can't be directly used for Useful in level-order
level-order traversal in traversal, BFS in
trees graphs
Works like a pile of books Works like a line at a
(last book on top is counter (first person
removed first) is served first)
✅ Example:
Stack Example:
Push: 10 → 20 → 30
Pop: returns 30 (last in, first out)
Queue Example:
Enqueue: A → B → C
Dequeue: returns A (first in, first out)

7. What is meant by uderflow and overflow in

Ans. 🔴 Underflow in Queue –
Underflow occurs when you try to delete
(dequeue) an element from a queue that is
already empty.
Since there are no elements to remove, the
operation is not possible and results in an
underflow condition.
✅ Example:
Queue: [ ] ← (Empty Queue)
Operation: Dequeue()
Result: Underflow (Cannot delete from an empty
queue)

🔴 Overflow in Queue –
Overflow occurs when you try to insert
(enqueue) an element into a queue that is
already full (in case of fixed-size queue).
Since there is no available space, the operation
fails and results in an overflow condition.
✅ Example:
Queue size = 3
Queue: [10, 20, 30] ← (Full Queue)
Operation: Enqueue(40)
Result: Overflow (Cannot insert into a full queue)
8. Explain Circular Queue ?
Ans. A Circular Queue is a special type of queue
where the last position is connected back to the
first position to make a circle.
It is used to avoid wasting space in a normal
(linear) queue when elements are removed.
UNIT – 3

9. Explain Binary Tree?

Ans. A Binary Tree Data Structure is a hierarchical
data structure in which each node has at most
two children, referred to as the left child and the
right child. It is commonly used in computer
science for efficient storage and retrieval of data,
with various operations such as insertion,
deletion, and traversal.
Diagram/ Example of Binary Tree.
# Types of Binary Tree
• Full Binary Tree –
Every node has 0 or 2 children.

• Degenerate Binary Tree –

Every internal node has one child
 • Skewed Binary Trees
Tree is either dominated by the left nodes or the
right nodes. Thus, there are two types of skewed
binary tree: left-skewed binary tree and right-
skewed binary tree.
10. Explain Array and Linked Representation of
Binary Tree?
Ans.
Array Representation of Binary Tree
In Array Representation, we store the elements
of a binary tree in a linear array based on the
level order traversal (top to bottom, left to right).
Rules (for 0-based indexing):
If a node is stored at index i:
• Left child → at index 2*i + 1
• Right child → at index 2*i + 2
• Parent → at index (i - 1)/2
(For 1-based indexing: Left = 2i, Right = 2i + 1)
Example:
Consider the binary tree:
A
/\
B C
/\ \
D E F
Level Order Traversal: A, B, C, D, E, _, F
Array Representation (0-based indexing):
Index: 0 1 2 3 4 5 6
Value: A B C D E null F

Advantages:
• Easy to implement.
• No need for pointers.
• Fast access to elements using index.
Disadvantages:
• Wastes memory for sparse or unbalanced
trees.
• Difficult to perform dynamic insertion and
deletion.

Linked Representation of Binary Tree

In this method, each node of the binary tree is
represented using a structure/class with three
fields:
• data – to store the value
• left – pointer/reference to the left child
• right – pointer/reference to the right child
Example:
Same binary tree:
A
/\
B C
/\ \
D E F

Advantages:
• Efficient use of memory for any tree
structure.
• Easy to perform insertion and deletion.
• Suitable for dynamic trees
(growing/shrinking).
Disadvantages:
• Requires more memory due to pointers.
• Slightly complex to implement compared to
arrays.
11. Find the Preorder In order and post order
traversal of binary tree (LAST)
12. Create a binary tree from preorder and
inorder. (LAST)
13. Construct binary tree from the preorder and
inorder sequence? (LAST)

14. Explain Complete Binary tree with example?

Ans. A complete binary tree is a special type of
binary tree where all the levels of the tree are
filled completely except the lowest level nodes
which are filled from as left as possible.
15. What is Binary tree? Explain the binary tree
representation of binary tree with example?
Ans. A Binary Tree is a data structure where each
node has:
• At most two children,
• Called left child and right child.

🔰 Example of Binary Tree:

A
/ \
B C
/\ \
D E F
Each node has at most 2 children → So it’s a valid
binary tree.
📘 Types of Binary Tree Representation:
There are three main ways to represent a binary
tree:

✅ 1. Linked Representation (Pointer Based)

Each node is represented using a structure/class
with:
• Data
• Pointer to left child
• Pointer to right child
Structure:
struct Node {
int data;
Node* left;
Node* right;
};
Example:
• Node A → left → B, right → C
 • Node B → left → D, right → E
✅ Used in most programming languages like C,
C++, Java, Python

✅ 2. Array Representation
Used for Complete Binary Trees or Heaps.
Rules (for 1-based index):
• For node at index i:
o Left child → index 2i
o Right child → index 2i + 1
o Parent → index i/2
Example Tree:
1
/ \
2 3
/\ /
4 56
Array (1-based):
[ , 1, 2, 3, 4, 5, 6]
• Index 1 → Root (1)
• Index 2 → Left of 1 = 2
• Index 3 → Right of 1 = 3
• Index 4 → Left of 2 = 4
• Index 5 → Right of 2 = 5
• Index 6 → Left of 3 = 6

✅ 3. Parent Array Representation

In this, we store a parent for each node in an
array.
Example Tree:
0
/\
1 2
/
3
Parent Array:
Index → Node
Value → Parent of node
• Node 0 → root → parent = -1
• Node 1 → parent = 0
• Node 2 → parent = 0
• Node 3 → parent = 1
✅ 4. Sequential Representation (for Complete
Binary Trees)
Same as array representation but used for storing
trees without pointers.
Tree:
A
/ \
B C
/\
D E
16. Explain one way and two threading in binary
tree using diagram? How can you implement
the node of a fully threaded binary tree?
Ans. A Threaded Binary Tree is a type of binary
tree where:
• If a node’s left or right child is NULL, we don’t
leave it empty.
• Instead, we use that NULL pointer to store:
o The in-order predecessor (if left is NULL)
o Or the in-order successor (if right is
📌 Important Point:
• The leftmost and rightmost nodes still have
NULL because they have no
predecessor/successor.
🌳 Types of Threaded Binary Tree
There are 2 types of threaded binary trees:

✅ 1. One-way Threaded Binary Tree (Single

Threaded)
• Only the right NULL pointer is used.
• If a node has no right child, its right pointer
stores the in-order successor.
• We use a rightThread flag to check if it’s a
thread or normal child.
Node Structure:
struct Node {
int value;
Node* left;
Node* right;
bool rightThread;
✅ 2. Two-way Threaded Binary Tree (Double
Threaded)
• Both left and right NULL pointers are used.
o Left NULL → stores in-order predecessor
o Right NULL → stores in-order successor
• We use leftThread and rightThread flags.
Node Structure:
struct Node {
int value;
Node* left;
Node* right;
};
📝 Summary:
Type Threads Used Threads Point To
One-
Only right thread In-order successor
way
Two- Both left and In-order predecessor &
way right threads successor
17. Explain the Linked representation of graph?
Ans. The linked representation of a graph is a
way to store a graph using linked lists, where
each vertex of the graph has a list of all the
vertices it is connected to.
This method is also called an Adjacency List
representation.

✅ Key Points:
• Time complexity to store: O(V + E), where V =
vertices, E = edges.
• Best suited for: Sparse graphs.
• Reduces memory usage compared to
adjacency matrix.

✅ Example:
Let’s say we have a directed graph with 4
vertices:
0, 1, 2, 3
And the edges are:
 • 0→1
• 0→2
• 1→2
• 2→0
• 2→3
• 3→3

✅ Adjacency List Representation:

0→1→2
1→2
2→0→3
3→3
✅ Explanation of Above Example:
• Vertex 0 is connected to 1 and 2
• Vertex 1 is connected to 2
• Vertex 2 is connected to 0 and 3
• Vertex 3 is connected to itself (self-loop)
✅ Advantages:
• Saves space for sparse graphs.
• Easy to add or remove edges.
• Faster traversal of neighbors of a vertex.

✅ Conclusion:
The linked representation of a graph is an
efficient way to represent graphs using adjacency
lists. It is highly space-efficient for large and
sparse graphs and is commonly used in
algorithms like BFS, DFS, Dijkstra’s, etc.
18. Find minimum spanning tree of the following
graph using Kruskal algorithm?

19. Compare BFS and DFS graph traversal

method?
Ans.
BFS (Breadth-First DFS (Depth-First
Search) Search)
Visits depth-wise (goes
Visits level by level
deep first)
Uses a stack (or
Uses a queue
recursion)
Explores as deep as
Explores all neighbors
possible before
before going deep
backtracking
Takes more memory Takes less memory
(due to queue) (stack or recursion)
Good for finding Not always finds the
shortest path shortest path
BFS (Breadth-First DFS (Depth-First
Search) Search)
Slower in deep graphs Faster in deep graphs
Used in Shortest Path, Used in Topological
Level Order Sort, Cycle Detection
Example for Graph: 0 → Example for Graph: 0
1 → 2 → 3 → visits: 0 1 2 → 1 → 2 → 3 → visits:
3 0 1 2 3 (but depth first)

20. Considered A as the source vertex, Apply

Dijkstas algorithm to find the shortest path ?
21. Define Directed Graph ?
Ans. A Directed Graph, also called a Digraph, is a
type of graph in which each edge has a direction.
In simple words, the edge goes from one vertex
to another in a specific direction.

📙 Explanation:
• A directed graph is made up of vertices
(nodes) and directed edges (arrows).
• Each edge is represented as an ordered pair
(u, v), meaning the edge goes from vertex u
to vertex v.
• The edge (u, v) is not the same as (v, u). They
are different unless both are present.
📗 Real-Life Example:
• Think of Instagram:
If person A follows person B, it does not
mean B follows A.
This "one-way following" is like a directed
edge from A to B.

📘 Graph Example:
Let’s consider a graph with 4 vertices: A, B, C, D
And the directed edges are:
• A→B
• A→C
• B→D
🔸 Diagram (Text Form):
A→B→D
↓
C
✅ Key Features of Directed Graph:
• Edges have direction (one-way).
• Represented as ordered pairs.
• Can be used in:
o Web pages (link from one to another)
o Social media (follower system)
o Road maps (one-way roads)
o Task scheduling (task A must finish
before task B)
22. Explain Depth first Search with example?
Ans. Depth First Search (DFS) is a graph traversal
algorithm that starts at a selected node (called
the source) and explores as far as possible along
each branch before backtracking.

📙 Explanation:
• DFS visits a node, then recursively visits all its
unvisited neighbors.
• It goes deep into one path until it reaches a
dead end (no more unvisited nodes), and
then goes back (backtracks) to explore other
paths.
• DFS uses a stack data structure, either
explicitly (using a stack) or implicitly (using
recursion).
✅ Steps of DFS Algorithm:
1. Start from a source node
2. Mark the node as visited
3. Visit the next unvisited neighbor
4. Repeat until no unvisited neighbors are left
5. Then backtrack and repeat for other nodes

📗 Example:
Let’s take a simple graph:
A
/\
B C
/\
D E
🔹 Edges:
• A → B, A → C
• B → D, B → E
🧠 Important Points:
• DFS is recursive or uses a stack
• Best for exploring all nodes in a path
• Useful in:
o Cycle Detection
o Topological Sorting
o Solving puzzles like mazes
o Pathfinding algorithms
23. Write a BSF graph traversal algorithm and
Explain ?
Ans. Breadth-First Search (BFS) is a graph
traversal algorithm that visits all the vertices of a
graph level by level starting from a selected
source node.
It uses a queue to keep track of the next node to
visit.

📙 Explanation (in easy words):

• BFS starts at a given node and visits all its
direct neighbors first.
• Then, it visits the neighbors of those
neighbors, and so on.
• It visits the graph in a layered (breadth-wise)
manner, not deep like DFS.
• It uses a queue data structure and marks
visited nodes to avoid repetition.
✅ BFS Algorithm (Step-by-Step):
1. Create a queue and add the starting node.
2. Mark the starting node as visited.
3. While the queue is not empty:
o Remove a node from the queue and
process it.
o Add all its unvisited neighbors to the
queue and mark them as visited.
4. Repeat until all reachable nodes are visited.

✅ Example:
Let’s take this simple undirected graph:
A
/\
B C
/\
D E
🧠 Key Points:
• BFS uses a Queue
• Visits nodes level-by-level
• Suitable for finding the shortest path in an
unweighted graph
• Useful in:
o Web Crawlers
o Social Networks
o Shortest Path Algorithms like in GPS
o AI for games and puzzles
Now for DFS –
Depth First Search (DFS) is a graph traversal
algorithm that starts from a given node and
explores as far as possible along each path,
before backtracking.
It uses a stack (or recursion) to keep track of the
nodes.

📙 Explanation (in easy words):

• DFS starts at a node and goes deep into one
path until there are no more nodes to visit.
• Then it goes back (backtracks) and checks
other unexplored paths.
• DFS is like exploring a maze by going as deep
as possible before turning back.
✅ DFS Algorithm (Step-by-Step):
1. Start from the source node.
2. Mark the node as visited.
3. Visit the next unvisited neighbor of the node.
4. Repeat step 2–3 until no unvisited neighbors
are left.
5. Then backtrack and repeat for other
unvisited neighbors.
6. Continue until all nodes are visited.
DFS is often implemented using recursion or a
stack.
✅ Example Graph:
Let’s take this simple undirected graph:
A
/\
B C
/\
D E
24. Explain Spanning Tree in Detail?
Ans. A spanning tree is a subset of Graph G, such
that all the vertices are connected using minimum
possible number of edges. Hence, a spanning tree
does not have cycles and a graph may have more
than one spanning tree.
Key Points:
1. A spanning tree must be connected.
2. It must not have any cycles (loops).
3. If a graph has V vertices, the spanning tree will
have exactly V - 1 edges.
4. A graph can have more than one spanning
tree.
5. Spanning trees are mostly used in network
design, minimum path cost, etc.
Algorithms to Find Minimum Spanning Tree of a
Graph:
1. Krushkal's MST Algorithm
2. Prim's MST Algorithm
25. Explain what is graph and how you can
represented a graph ?
Ans. Graph is a non-linear data
structure consisting of vertices and edges. The
vertices are sometimes also referred to as nodes
and the edges are lines or arcs that connect any
two nodes in the graph. More formally a Graph is
composed of a set of vertices( V ) and a set of
edges( E ). The graph is denoted by G(V, E).

Types Of Graphs in Data Structure and

Algorithms
• Undirected Graph
A graph in which edges do not have any
direction. That is the nodes are unordered pairs
in the definition of every edge.
 • Directed Graph
A graph in which edge has direction. That is the
nodes are ordered pairs in the definition of every
edge.

5. Connected Graph
The graph in which from one node we can visit
any other node in the graph is known as a
connected graph.
6. Disconnected Graph
The graph in which at least one node is not
reachable from a node is known as a
disconnected graph.
9. Cycle Graph
The graph in which the graph is a cycle in itself,
the minimum value of degree of each vertex is 2.
Representation of Graph Data Structure:
There are multiple ways to store a graph: The
following are the most common representations.
• Adjacency Matrix
In this method, the graph is stored in the form of
the 2D matrix where rows and columns denote
vertices. Each entry in the matrix represents the
weight of the edge between those vertices.
• Adjacency List

This graph is represented as a collection of

linked lists. There is an array of pointer which
points to the edges connected to that vertex.
UNIT – 5
26. Explain Binary search Algorithm with
example?
Ans. . Binary Search Algorithm is a searching
algorithm used in a sorted array by repeatedly
dividing the search interval in half. The idea of
binary search is to use the information that the
array is sorted and reduce the time complexity to
O(log N).
Conditions to apply Binary Search Algorithm in a
Data Structure
To apply Binary Search algorithm:
• The data structure must be sorted.
• Access to any element of the data structure
should take constant time.
Binary Search Algorithm
Below is the step-by-step algorithm for Binary
Search:
• Divide the search space into two halves
by finding the middle index "mid".
 • Compare the middle element of the search
space with the key.
• If the key is found at middle element, the
process is terminated.
• If the key is not found at middle element,
choose which half will be used as the next
search space.
o If the key is smaller than the middle
element, then the left side is used for next
search.
o If the key is larger than the middle
element, then the right side is used for
next search.
• This process is continued until the key is found
or the total search space is exhausted.

The Binary Search Algorithm can be implemented

in the following two ways
• Iterative Binary Search Algorithm
• Recursive Binary Search Algorithm
Iterative Binary Search Algorithm:

Here we use a while loop to continue the process of

comparing the key and splitting the search space in
two halves.

while low <= high:

mid = (low + high) // 2
# check mid value and adjust low/high

Recursive Binary Search Algorithm:

Create a recursive function and compare the mid of the
search space with the key. And based on the result either
return the index where the key is found or call the
recursive function for the next search space.

def binarySearch(arr, low, high, target):

if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binarySearch(arr, low, mid - 1, target)
else:
return binarySearch(arr, mid + 1, high, target)
27. Explain AVL tree ?

Ans. An AVL Tree (Adelson-Velsky and Landis Tree) is a self-

balancing binary search tree in which the balance factor
(difference in height of left and right subtree) of every node
is always -1, 0, or +1.
If the tree becomes unbalanced after insertion or deletion, it
is automatically re-balanced using rotations (LL, RR, LR, RL).
This ensures the height of the tree stays close to log(n), and
all operations like search, insert, and delete can be done in
O(log n) time, making it highly efficient and reliable for
sorted data handling.

Example.

30

20

10
28. What is Hashing and its techniques?
Ans. Hashing is a technique used to map large or
complex data (keys) into a small, fixed-size value
(hash code) using a hash function. This value is
used as an index to store or retrieve the data in a
hash table.
Hashing allows us to perform searching, insertion,
and deletion operations in O(1) time on average.
📘 Hashing Techniques (Collision Resolution
Methods)
✅ There are 2 Main Types of Hashing
Techniques:

1. Chaining (Separate Chaining)

• In this technique, each index in the hash table
points to a linked list (or a dynamic data
structure).
2. Open Addressing
• In this method, all data is stored inside the
hash table itself.
🔹 a. Linear Probing
🔹 b. Quadratic Probing
🔹 c. Double Hashing
Difference Between B+ Tree and B Tree

Parameters B+ Tree B Tree

Separate leaf
nodes for data Nodes store
Structure storage and both keys and
internal nodes data values
for indexing

Leaf nodes
form a linked Leaf nodes do
Leaf Nodes list for efficient not form a
range-based linked list
queries

Higher order Lower order

Order
(more keys) (fewer keys)

Typically allows Usually does

Key
key duplication not allow key
Duplication
in leaf nodes duplication
Parameters B+ Tree B Tree

Better disk
More disk I/O
access due to
due to non-
sequential
Disk Access sequential
reads in a
reads in
linked list
internal nodes
structure

Database In-memory
systems, file data structures,
Applications systems, where databases,
range queries general-
are common purpose use

Better Balanced
performance performance
for range for search,
Performance
queries and insert, and
bulk data delete
retrieval operations
Parameters B+ Tree B Tree

Requires less
Requires more memory as
Memory
memory for keys and values
Usage
internal nodes are stored in
the same node
29. What is B+ Tree ?
Ans. B+ Tree is a self-balancing multi-level search
tree used for storing large amounts of sorted
data in a structured and efficient way.
It is an extended form of B-Tree where all actual
records (data) are stored only in the leaf nodes,
and internal nodes contain only keys (index
values) used for navigation.
The main feature of a B+ Tree is that it maintains
all data at the same depth and the leaf nodes are
connected using linked pointers, making it
extremely efficient for range queries, sorted
traversal, and disk-based storage systems.
In a B+ Tree:
• Each node can have multiple children (not
limited to two like binary trees)
• It remains balanced at all times
• Searching, inserting, and deleting can be
done in O(log n) time
⚙️ Key Features / Properties of B+ Tree:
1. All actual data is stored only in leaf nodes
2. Internal (non-leaf) nodes store only keys, not
full data
3. All leaf nodes are at the same level, which
keeps the tree balanced
4. Leaf nodes are connected with each other
using pointers → supports fast sequential
access
5. Supports range queries and sorted access
efficiently
6. Can handle very large data (used in disk
storage, DBMS, file systems)
30. Explain Comparison and analysis internal
sorting?
Ans.
Internal Sorting refers to the process of sorting
data when the entire dataset can fit into the
computer’s main memory (RAM) during the
sorting operation.
It means all the elements that need to be sorted
are already in memory and can be accessed
directly by the CPU.
🧠 Purpose of Internal Sorting:
• To arrange data in a specific order
(ascending/descending)
• To improve search speed, remove duplicates,
or prepare for output
• Used in programs, memory-based apps, and
during run-time processing
🔍 Comparison of Internal Sorting Algorithms:
Time
Sorting
Complexity Space Stable Best For
Algorithm
(Avg)
Simple
Bubble ✅
O(n²) O(1) cases,
Sort Yes
learning
Small or
Insertion ✅
O(n²) O(1) nearly
Sort Yes
sorted lists
Not
Selection ❌
O(n²) O(1) commonly
Sort No
used
Large data,
Merge ✅
O(n log n) O(n) stable
Sort Yes
sorting
O(log ❌ Fastest in
Quick Sort O(n log n)
n) No most cases
 Time
Sorting
Complexity Space Stable Best For
Algorithm
(Avg)
Space-
❌
Heap Sort O(n log n) O(1) efficient
No
sorting