Data Structures and Algorithms-II - Questions & Answers
Chapter 1: Tree
Q: What is a binary tree and what are its types?
A: A binary tree is a hierarchical data structure in which each node has at most two children referred to as the
left child and the right child. Types include: Skewed tree (left/right), Strictly binary tree, Full binary tree,
Complete binary tree, Expression tree, Binary search tree, Heap.
Q: Define and differentiate between static and dynamic representation of trees.
A: Static representation uses arrays and is fixed in size. Dynamic representation uses linked nodes, allowing
flexible memory usage.
Q: What is in-order traversal in a binary tree?
A: In in-order traversal, the nodes are recursively visited in this order: left child, root, right child.
Q: What is a binary search tree (BST)?
A: A BST is a binary tree where each node follows the property: left child < parent < right child. It allows fast
search, insertion, and deletion.
Q: What is a complete binary tree?
A: A binary tree where all levels are completely filled except possibly the last, which is filled from left to right.
Q: What is a heap?
A: A heap is a complete binary tree where the value of each node is greater than or equal to (max-heap) or
less than or equal to (min-heap) the value of its children.
Q: What is the difference between preorder and postorder traversal?
Data Structures and Algorithms-II - Questions & Answers
A: Preorder: Root -> Left -> Right; Postorder: Left -> Right -> Root.
Chapter 2: Efficient Search Trees
Q: What are AVL trees and how are they balanced?
A: AVL trees are self-balancing binary search trees where the height difference between left and right
subtrees (balance factor) is at most one. Rotations (LL, RR, LR, RL) are used to maintain balance.
Q: List differences between AVL and Red-Black Trees.
A: AVL trees are more rigidly balanced, while Red-Black trees are more relaxed. AVL trees provide faster
lookups, Red-Black trees offer better insert/delete performance.
Q: What is a Red-Black tree?
A: A Red-Black tree is a balanced binary search tree where each node has a color (red or black), and the tree
maintains certain balancing rules to ensure O(log n) operations.
Q: What are B-trees used for?
A: B-trees are self-balancing search trees commonly used in databases and file systems to allow efficient
insertion, deletion, and search in logarithmic time.
Q: What is a B+ Tree?
A: A B+ tree is an extension of B-tree where all data is stored in leaf nodes, and internal nodes only store
keys. It supports efficient range queries.
Q: What is the difference between B-Tree and B+ Tree?
A: B-Tree: Keys and data can be stored in both internal and leaf nodes. B+ Tree: All data stored in leaves;
Data Structures and Algorithms-II - Questions & Answers
internal nodes only hold keys.
Chapter 3: Graph
Q: Define adjacency matrix and adjacency list.
A: Adjacency Matrix: A 2D array where A[i][j] = 1 if there's an edge between vertex i and j. Adjacency List:
Each vertex stores a list of adjacent vertices.
Q: Explain BFS and DFS.
A: BFS (Breadth-First Search): Uses a queue; explores neighbors level by level. DFS (Depth-First Search):
Uses a stack (or recursion); explores as far as possible along each branch.
Q: What is Dijkstra's Algorithm?
A: It is a greedy algorithm used to find the shortest path from a source node to all other nodes in a weighted
graph with non-negative edges.
Q: What is topological sorting?
A: A linear ordering of vertices such that for every directed edge u -> v, vertex u comes before v. Only valid
for Directed Acyclic Graphs (DAGs).
Q: What is a spanning tree?
A: A subgraph of a connected undirected graph that includes all the vertices with the minimum possible
number of edges and no cycles.
Q: Compare Prim's and Kruskal's algorithms.
A: Prim's: Grows MST from a single vertex using the minimum edge. Kruskal's: Sorts all edges and adds
Data Structures and Algorithms-II - Questions & Answers
them one by one avoiding cycles.
Q: What is Floyd-Warshall algorithm used for?
A: It computes the shortest paths between all pairs of vertices in a weighted graph using dynamic
programming.
Q: Where are graphs used in real life?
A: Social networks, Web page linking, Routing algorithms, Scheduling problems.
Chapter 4: Hash Table
Q: What is hashing?
A: Hashing is the process of converting data (key) into a fixed-size value (hash code), used for fast data
access.
Q: What is collision in hashing and how is it resolved?
A: A collision occurs when two keys produce the same hash value. Resolution techniques: Open addressing:
Linear probing, quadratic probing, rehashing; Chaining: Coalesced or separate chaining.
Q: Explain division and folding method in hash functions.
A: Division: h(k) = k mod m; Folding: Splits key into parts and combines them, often using addition or XOR.
Q: What is linear probing?
A: A collision resolution strategy where the next slot is checked linearly (i.e., index + 1, index + 2...) until an
empty slot is found.
Data Structures and Algorithms-II - Questions & Answers
Q: What is quadratic probing?
A: It checks next slots in a quadratic pattern: index + 1², index + 2², and so on, to resolve collisions.
Q: What is rehashing?
A: Rehashing is the process of creating a new, larger hash table when the original becomes too full, and
re-inserting all keys using a new hash function.
