Data Structures-II Notes
Subject Overview
Data Structures-II moves from linear to non-linear and advanced structures — binary trees and binary search trees, height-balanced and multi-way trees (AVL, B-Tree, B+ Tree, Red-Black Tree, Heap), graphs and their traversal/
Subject at a glance
4
Units
26
Topics
3
Credits
4
Infographics
Unit-wise Syllabus
4 units — open any unit for detailed topic-wise notes, diagrams and important exam questions
- Definition and terminology
- binary trees
- array and linked-list memory representation
- recursive and non-recursive traversal
- threaded binary tree
- binary search tree — insertion
- deletion
- searching
- Preorder
- Root → Left → Right
- Inorder
- Left → Root → Right (sorted order in a BST)
- Postorder
- Left → Right → Root (used to delete trees)
- Level order
- Level by level using a queue
Study guide
Trees organise data hierarchically, and they are everywhere from file systems to databases. You learn tree terminology, binary trees and their array and linked representations, recursive and non-recursive traversals (preorder, inorder, postorder), threaded binary trees and the binary search tree with insertion, deletion and searching. Practise drawing a BST from a list of numbers and traversing it three ways.
- Height-balanced (AVL) trees — insertion and deletion
- M-way trees
- B-Trees
- B+ Trees
- Red-Black trees
- Heap trees
LL case
Single right rotation
RR case
Single left rotation
LR case
Left rotation on child, then right rotation
RL case
Right rotation on child, then left rotation
Study guide
Plain binary search trees can become lopsided, so this unit studies trees that stay balanced: AVL (height-balanced) trees with their rotations during insertion and deletion, M-way trees, B-trees and B+ trees (used in databases and file systems), red-black trees and heap trees. Learn the four AVL rotations by drawing each case; they are the most commonly asked part.
- Definition and terminology
- types of graphs
- memory representation
- depth-first and breadth-first traversal
- Dijkstra's shortest path algorithm
Data structure
Queue
Stack or recursion
Explores
Level by level
As deep as possible first
Finds shortest path
Yes, in unweighted graphs
Not guaranteed
Uses
Shortest path, web crawling
Cycle detection, topological sort
Study guide
Graphs model networks of relationships such as roads, friendships and web links. You learn graph terminology and types, how to store a graph in memory (adjacency matrix and list), depth-first and breadth-first traversal, and Dijkstra's shortest-path algorithm. Run both traversals by hand on a small graph using a stack and a queue respectively.
- Linear and binary search
- hashing
- hash tables
- hash function types
- collision resolution (open addressing and chaining)
- bubble/selection/insertion/quick sort
- comparative study of searching and sorting algorithms
Bubble sort
O(n²)
Simple; swaps adjacent elements
Selection sort
O(n²)
Fewest swaps
Insertion sort
O(n²)
Fast on nearly sorted data
Quick sort
O(n log n)
Worst case O(n²); very fast in practice
Study guide
Searching and sorting are the most tested topics in interviews. You study linear and binary search, hashing with hash tables and hash functions, collision resolution (open addressing and chaining), and the bubble, selection, insertion and quick sort algorithms, with a comparison of their efficiency. Know the best, average and worst-case time of each algorithm.
Why Data Structures-II Matters
Trees, graphs, hashing and sorting make up the core of coding interviews at almost every software company. They also explain how databases index data, how maps and routes are computed and how search engines work, so this paper pays back across your whole career.
How to Prepare for Data Structures-II
- Draw every tree and graph on paper; traversal answers are easiest to check visually.
- Memorise the time complexity table of the sorting and searching algorithms.
- Learn the AVL rotations (LL, RR, LR, RL) with a small example for each.
- Solve a few interview problems on trees and graphs every week.
Data Structures-II: Frequently Asked Questions
What is the difference between BFS and DFS?
Breadth-first search explores a graph level by level using a queue, while depth-first search goes as deep as possible along each branch using a stack or recursion.
Why are AVL trees used?
An AVL tree keeps itself height-balanced through rotations, which guarantees searching, insertion and deletion in logarithmic time.
Which sorting algorithm is fastest?
On average quick sort is among the fastest general-purpose comparison sorts, but the best choice depends on the data; bubble, selection and insertion sort are simpler but slower for large data.