UNIT 1: INTRODUCTION & ARRAYS

Introduction to Data Structures

A Data Structure is a way of organizing and storing data in a computer so that it can be
accessed and modified efficiently.

In real life, we organize books in a library, files in a cabinet, and clothes in a wardrobe.
Similarly, computers need organized ways to store data. This organization is called a Data
Structure.

Data structures help in:

• Efficient storage of data

• Fast access to data

• Easy modification of data

• Better memory utilization

Examples of data structures:

• Array

• Linked List

• Stack

• Queue

• Tree

• Graph

Why Data Structures are Important

As the amount of data increases, managing data becomes difficult.

A good data structure helps:

• Reduce execution time

• Reduce memory usage

• Improve program efficiency

• Solve complex problems easily

Without proper data structures, programs become slow and inefficient.

Data structures are mainly classified into two categories.

Primitive Data Structures

These are basic data types provided by programming languages.

Examples:

• Integer

• Float

• Character

• Double

• Boolean

Non-Primitive Data Structures

These are derived from primitive data types.

Examples:

• Array

• Linked List

• Stack

• Queue

• Tree

• Graph

Further Classification

Linear Data Structures

Elements are arranged sequentially.

Examples:

• Array

• Linked List
 • Stack

• Queue

Non-Linear Data Structures

Elements are not arranged sequentially.

Examples:

• Tree

• Graph

Operations on Data Structures

Several operations can be performed on data structures.

Traversal

Visiting each element exactly once.

Example:

10 20 30 40 50

Reading all elements one by one is called traversal.

Insertion

Adding a new element into a data structure.

Example:

10 20 40

Insert 30

10 20 30 40

Deletion

Removing an existing element.

Example:
10 20 30 40

Delete 20

10 30 40

Searching

Finding the location of an element.

Example:

Search 30 from:

10 20 30 40

Result:

Position = 3

Sorting

Arranging elements in a specific order.

Ascending Order

10 20 30 40

Descending Order

40 30 20 10

Merging

Combining two data structures into one.

Example:

Array 1: 10 20

Array 2: 30 40

Merged:
10 20 30 40
Algorithm

An algorithm is a finite sequence of steps used to solve a problem.

It provides a systematic method for obtaining the desired output.

Example:

Algorithm to add two numbers:

Step 1: Start

Step 2: Read A and B

Step 3: Calculate Sum = A + B

Step 4: Display Sum

Step 5: Stop

Characteristics of a Good Algorithm

A good algorithm should have:

Finiteness

Must terminate after a finite number of steps.

Definiteness

Each step should be clear and unambiguous.

Input

Should accept input data.

Output

Should produce at least one output.

Effectiveness

Steps should be simple and executable.

Complexity of Algorithms

Algorithm complexity measures the resources required by an algorithm.

Mainly two types:

• Time Complexity
 • Space Complexity

Time Complexity

Time complexity measures how much execution time an algorithm requires.

It is usually expressed using Big-O notation.

Examples:

• O(1)

• O(log n)

• O(n)

• O(n²)

Space Complexity

Space complexity measures the amount of memory required by an algorithm.

It includes:

• Variables

• Arrays

• Temporary storage

Lower space complexity is generally preferred.

Time-Space Tradeoff

In many situations, increasing memory usage can reduce execution time, and reducing
memory usage may increase execution time.

This relationship is called Time-Space Tradeoff.

Example

If we store precomputed results in memory:

• Memory usage increases

• Execution becomes faster

Therefore:
More Memory → Less Time

Less Memory → More Time

Arrays

An array is a collection of elements of the same data type stored in contiguous memory
locations.

Each element is identified by an index.

Example:

A = [10, 20, 30, 40, 50]

Characteristics of Arrays

• Same data type elements

• Contiguous memory allocation

• Fixed size

• Fast access using index

Classification of Arrays

Arrays can be classified based on dimensions.

One-Dimensional Array

Contains a single row of elements.

Example:

10 20 30 40 50

Two-Dimensional Array

Contains rows and columns.

Example:
123
456
789

Multi-Dimensional Array

Contains more than two dimensions.

Example:

A[2][3][4]

Used in scientific and mathematical computations.

Representation of Linear Arrays in Memory

Array elements are stored in contiguous memory locations.

Example:

A[0] = 10
A[1] = 20
A[2] = 30
A[3] = 40

Memory Layout:

1000 → 10
1004 → 20
1008 → 30
1012 → 40

Each element occupies a fixed amount of memory.

Address Calculation Formula

For a one-dimensional array:

LOC(A[i]) = Base + (i × Size)

Where:

• Base = Starting address

• i = Index
 • Size = Size of each element

This formula helps locate any element directly.

Operations on Linear Arrays

Traversing an Array

Accessing each element one by one.

Example:

10 20 30 40 50

Visit:

10 → 20 → 30 → 40 → 50

Insertion in Array

Adding a new element at a specific position.

Example:

Before:

10 20 40 50

Insert 30:

After:

10 20 30 40 50

Elements may need shifting.

Deletion in Array

Removing an element from a specific position.

Example:

Before:

10 20 30 40

Delete 20:
After:

10 30 40

Remaining elements shift left.

Sorting

Sorting arranges elements in a desired order.

Bubble Sort

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the
wrong order.

Example:

40 20 30 10

After sorting:

10 20 30 40

Characteristics:

• Easy to understand

• Slow for large datasets

Time Complexity:

O(n²)

Selection Sort

Selection Sort repeatedly selects the smallest element and places it in the correct position.

Example:

40 20 30 10

After sorting:

10 20 30 40

Characteristics:

• Fewer swaps
 • Simple implementation

Time Complexity:

O(n²)

Insertion Sort

Insertion Sort inserts each element into its proper position in an already sorted portion.

Example:

40 20 30 10

After sorting:

10 20 30 40

Characteristics:

• Efficient for small datasets

• Easy implementation

Time Complexity:

O(n²)

Searching

Searching means finding the location of an element in a collection.

Linear Search

Linear Search checks elements one by one until the required element is found.

Example:

10 20 30 40 50

Search = 40

Check:

10 → 20 → 30 → 40

Element found.

Time Complexity:
O(n)

Binary Search

Binary Search works only on sorted arrays.

The search space is divided into two halves repeatedly.

Example:

10 20 30 40 50 60 70

Search = 50

Steps:

• Check middle element.

• If smaller, search left half.

• If larger, search right half.

Time Complexity:

O(log n)

Binary Search is much faster than Linear Search.

Two-Dimensional Arrays

A two-dimensional array is an array of rows and columns.

Example:

123
456
789

Representation:

A[3][3]

Applications:

• Matrix operations

• Scientific calculations

• Image processing
Matrices

A matrix is a rectangular arrangement of elements in rows and columns.

Example:

12
34

Types:

• Row Matrix

• Column Matrix

• Square Matrix

• Diagonal Matrix

• Identity Matrix

Matrices are widely used in mathematics and computer graphics.

Sparse Matrix

A sparse matrix contains mostly zero elements.

Example:

000
500
002

Advantages:

• Saves memory

• Efficient storage

Used in:

• Scientific computing

• Graph algorithms

• Machine learning

Multi-Dimensional Arrays

Arrays having more than two dimensions are called multi-dimensional arrays.
Example:

A[2][3][4]

Applications:

• 3D graphics

• Simulations

• Scientific calculations

Quick Revision Summary

Data Structure

• Organized way of storing data.

Types

• Primitive

• Non-Primitive

Operations

• Traversal

• Insertion

• Deletion

• Searching

• Sorting

• Merging

Complexity

• Time Complexity

• Space Complexity

Array

• Same type data

• Contiguous memory

• Fixed size

Searching
 • Linear Search → O(n)

• Binary Search → O(log n)

Sorting

• Bubble Sort

• Selection Sort

• Insertion Sort

Arrays

• One-Dimensional

• Two-Dimensional

• Multi-Dimensional

Matrix

• Row and column arrangement.

Sparse Matrix

• Mostly zero elements.

• Saves memory.

UNIT 2: LINKED LISTS & HASHING

Introduction to Linked List

A Linked List is a linear data structure in which elements are stored in separate memory
locations and connected using links (pointers).

Unlike arrays, linked list elements are not stored in contiguous memory locations.

Each element of a linked list is called a Node.

A node consists of:

• Data Part

• Link (Pointer) Part

Example:

[10|•] → [20|•] → [30|•] → NULL

• 10, 20, 30 are data values.

• Links connect one node to another.

• NULL indicates the end of the list.

Why Linked List is Needed?

Arrays have some limitations:

• Fixed size

• Memory wastage

• Difficult insertion and deletion

Linked lists overcome these problems because:

• Size can grow dynamically.

• Easy insertion and deletion.

• Better memory utilization.

Comparison Between Array and Linked List

Array

• Fixed size

• Contiguous memory

• Fast random access

• Insertion/deletion costly

Linked List

• Dynamic size

• Non-contiguous memory

• Sequential access

• Easy insertion/deletion

Representation of Linked List

Data + Address of Next Node

Example:

[5|100] → [10|200] → [15|300] → NULL

Where:

• Data = Actual value

• Address = Location of next node

The first node is called the Head Node.

Traversing a Linked List

Traversal means visiting each node one by one.

Example:

[10] → [20] → [30] → [40]

Traversal sequence:

10 → 20 → 30 → 40

The traversal starts from the head node and continues until NULL is reached.

Insertion in Linked List

Insertion means adding a new node.

Insertion can occur:

• At the beginning

• At the end

• At a specific position

Insertion at Beginning

Before:

20 → 30 → 40

Insert 10:
10 → 20 → 30 → 40

Advantages:

• Fast operation

• No shifting required

Insertion at End

Before:

10 → 20 → 30

Insert 40:

10 → 20 → 30 → 40

The new node becomes the last node.

Insertion at Middle

Before:

10 → 20 → 40

Insert 30:

10 → 20 → 30 → 40

The links are adjusted accordingly.

Deletion in Linked List

Deletion means removing a node.

Deletion can occur:

• From beginning

• From end

• From a specific position

Deletion from Beginning

Before:
10 → 20 → 30 → 40

Delete 10:

20 → 30 → 40

The head moves to the next node.

Deletion from End

Before:

10 → 20 → 30 → 40

Delete 40:

10 → 20 → 30

The second last node becomes the last node.

Deletion from Middle

Before:

10 → 20 → 30 → 40

Delete 30:

10 → 20 → 40

The links are updated.

Searching in Linked List

Searching means finding a particular element.

Example:

10 → 20 → 30 → 40

Search = 30

Check nodes one by one:

10 → 20 → 30

Element found.

Time Complexity:
O(n)

Types of Linked Lists

There are several types of linked lists.

Singly Linked List

Each node contains:

• Data

• One Link

Structure:

[Data|Next]

Example:

10 → 20 → 30 → NULL

Features:

• Simple implementation

• One-way traversal

Doubly Linked List

Each node contains:

• Previous Link

• Data

• Next Link

Structure:

[Prev|Data|Next]

Example:

NULL ← 10 ⇄ 20 ⇄ 30 → NULL

Features:

• Two-way traversal
 • Easy deletion

Disadvantage:

• More memory required

Circular Linked List

The last node points back to the first node.

Example:

10 → 20 → 30
↑ ↓
←←←←←

There is no NULL node.

Features:

• Circular traversal

• Efficient for round-robin scheduling

Applications of Linked List

Linked lists are widely used in:

• Dynamic memory allocation

• Stacks

• Queues

• Graph representation

• Polynomial manipulation

• Operating systems

Addition of Polynomials Using Linked List

Polynomials can be represented using linked lists.

Example:

5x² + 3x + 2

Each node stores:

• Exponent

Representation:

[5,2] → [3,1] → [2,0]

Advantages:

• Efficient storage

• Easy polynomial operations

Introduction to Hashing

Hashing is a technique used to store and retrieve data quickly.

The main idea is to map a key to a memory location using a mathematical function called a
Hash Function.

Hashing provides very fast searching.

Hash Table

A Hash Table is a data structure used to store data using hash functions.

Example:

Index : Value

0
1
2 → 25
3
4 → 14
5
6 → 31

The position is determined using a hash function.

Hash Function

A hash function converts a key into an index.

General form:
Hash Address = h(Key)

Example:

h(k) = k mod 10

If:

k = 25

Then:

25 mod 10 = 5

Data is stored at index 5.

Characteristics of Good Hash Function

A good hash function should:

• Be simple

• Be fast

• Distribute keys uniformly

• Minimize collisions

Collision

A collision occurs when two different keys produce the same hash value.

Example:

h(k) = k mod 10

15 mod 10 = 5
25 mod 10 = 5

Both keys generate the same location.

This situation is called a collision.

Collision Resolution Techniques

To handle collisions, special methods are used.

Main techniques:
 • Open Addressing

• Chaining

Open Addressing

In open addressing, if a location is occupied, another empty location is searched.

Data is stored inside the same hash table.

Methods include:

• Linear Probing

• Quadratic Probing

• Double Hashing

Linear Probing

If a position is occupied, check the next position.

Example:

5 occupied

Check:

6
7
8
...

Advantages:

• Simple implementation

Disadvantages:

• Clustering problem

Chaining

In chaining, each table location contains a linked list.

If multiple keys hash to the same index, they are stored in the linked list.
Example:

Index 5

15 → 25 → 35

Advantages:

• Easy collision handling

• Less clustering

Disadvantages:

• Extra memory required

Difference Between Open Addressing and Chaining

Open Addressing

• Stores data in the table itself.

• No extra memory needed.

• Clustering may occur.

Chaining

• Uses linked lists.

• Requires extra memory.

• Better collision handling.

Applications of Hashing

Hashing is used in:

• Databases

• Password storage

• Symbol tables

• Dictionaries

• Search engines

• Caching systems
Quick Revision Summary

Linked List

• Dynamic linear data structure.

• Nodes connected using links.

Types of Linked List

• Singly Linked List

• Doubly Linked List

• Circular Linked List

Operations

• Traversal

• Insertion

• Deletion

• Searching

Advantages

• Dynamic size

• Easy insertion and deletion

Hashing

• Fast data retrieval technique.

Hash Table

• Stores data using hash functions.

Collision

• Two keys produce same index.

Collision Resolution

• Open Addressing

• Chaining

Applications

• Databases

• Password systems
 • Search engines

• Caching

UNIT 3: STACKS, RECURSION & QUEUES

Introduction to Stack

A Stack is a linear data structure in which insertion and deletion are performed from only
one end called the TOP.

A stack follows the LIFO (Last In First Out) principle.

This means the element inserted last is removed first.

Example

Think of a stack of books.

If you place books one above another, the last book placed on the top is the first one to be
removed.

TOP
↓
40
30
20
10

If we remove an element, 40 will be removed first.

Characteristics of Stack

• Linear data structure

• Follows LIFO principle

• Insertion operation is called Push

• Deletion operation is called Pop

• Operations occur only at TOP

Representation of Stack Using Array

Example:

Index Element

0 10
1 20
2 30
3 40

TOP points to the last inserted element.

Stack Operations

The basic operations of stack are:

• Push

• Pop

• Peek (Top)

• IsEmpty

• IsFull

Push Operation

Push means inserting a new element into the stack.

Example:

Before:

30
20
10

Push 40

After:

40
30
20
10
The TOP moves upward.

Pop Operation

Pop means removing the topmost element.

Example:

Before:

40
30
20
10

Pop

After:

30
20
10

40 is removed.

Peek (Top) Operation

Peek returns the topmost element without removing it.

Example:

40
30
20
10

Peek = 40

Stack Overflow

Stack Overflow occurs when we try to insert an element into a full stack.

Example:

Stack Size = 5
Already Contains 5 Elements

Push Another Element

Result:

Stack Overflow

Stack Underflow

Stack Underflow occurs when we try to remove an element from an empty stack.

Example:

Stack Empty

Pop Operation

Result:

Stack Underflow

Representation of Stack Using Linked List

A stack can also be implemented using a linked list.

Each node contains:

• Data

• Next Pointer

Example:

TOP
↓
40 → 30 → 20 → 10

Advantages:

• Dynamic size

• No memory wastage

• Easy insertion and deletion

Applications of Stack
Stacks are widely used in computer science.

Function Calls

Stores function execution information.

Expression Evaluation

Used in arithmetic calculations.

Parenthesis Matching

Checks balanced brackets.

Undo Operations

Used in text editors.

Backtracking

Used in maze solving and recursion.

Arithmetic Expressions

Computers evaluate arithmetic expressions using stacks.

Three common forms are:

Infix Expression

Operator appears between operands.

Example:

A+B

Prefix Expression

Operator appears before operands.

Example:

+AB

Postfix Expression

Operator appears after operands.

Example:
AB+

Comparison of Expressions

Type Example

Infix A+B

Prefix +AB

Postfix AB+

Conversion of Infix to Postfix

Example:

A+B

Postfix:

AB+

Example:

(A+B)*C

Postfix:

AB+C*

Stacks help manage operators during conversion.

Evaluation of Postfix Expression

Example:

23+

Meaning:

2+3=5

Steps:

1. Push operands.

2. Encounter operator.
 3. Pop required operands.

4. Perform operation.

5. Push result back.

Stacks make postfix evaluation very efficient.

Recursion

Recursion is a technique in which a function calls itself.

A recursive function repeatedly executes until a stopping condition is reached.

Example of Recursion

Factorial of 5:

5! = 5 × 4 × 3 × 2 × 1

Recursive Definition:

fact(n) = n × fact(n−1)

Base Condition:

fact(1) = 1

Components of Recursion

Every recursive function has:

Recursive Call

Function calls itself.

Base Condition

Stops infinite execution.

Without a base condition, recursion never ends.

Runtime Stack

Whenever a function is called, information about that function is stored in memory.

This memory area is called the Runtime Stack.

• Function parameters

• Return address

• Local variables

Each recursive call creates a new stack frame.

Example of Runtime Stack

For:

fact(3)

Stack Growth:

fact(3)
fact(2)
fact(1)

Stack Shrinks:

fact(1)
fact(2)
fact(3)

Advantages of Recursion

• Simple coding

• Easy problem solving

• Useful for trees and graphs

• Elegant program design

Disadvantages of Recursion

• More memory usage

• Slower execution

• Risk of stack overflow

Recursion is used in:

Factorial Calculation

n!

Fibonacci Series

0 1 1 2 3 5 8 ...

Binary Search

Efficient searching technique.

Tree Traversal

Preorder, Inorder, Postorder.

Tower of Hanoi

Classic recursive problem.

Introduction to Queue

A Queue is a linear data structure that follows the FIFO (First In First Out) principle.

The first inserted element is removed first.

Example:

Think of people standing in a ticket counter line.

The first person entering the queue gets service first.

Queue Structure

Insertion occurs at:

REAR

Deletion occurs at:

FRONT

Example:

FRONT
↓
10 20 30 40
 ↑
REAR

Queue Operations

Main operations are:

• Enqueue

• Dequeue

• Peek

• IsEmpty

• IsFull

Enqueue Operation

Adds an element at the rear.

Example:

Before:

10 20 30

Enqueue 40

After:

10 20 30 40

Dequeue Operation

Removes an element from the front.

Example:

Before:

10 20 30 40

Dequeue

After:

20 30 40
10 is removed first.

Queue Overflow

Occurs when insertion is attempted into a full queue.

Queue Underflow

Occurs when deletion is attempted from an empty queue.

Circular Queue

A circular queue connects the last position back to the first position.

The queue forms a circle.

Example:

1→2→3→4
↑ ↓
←←←←←←

Advantages:

• Better memory utilization

• Avoids wastage of space

Double Ended Queue (Deque)

A deque allows insertion and deletion from both ends.

Operations can occur at:

• Front

• Rear

Types:

Input Restricted Deque

Insertion allowed at one end.

Output Restricted Deque

Deletion allowed at one end.

In a priority queue, elements are processed according to priority rather than arrival order.

Example:

Priority 1 → Highest
Priority 5 → Lowest

A higher-priority element is served first.

Applications:

• CPU Scheduling

• Operating Systems

• Network Routing

Queue Using Array

Queue elements are stored in an array.

Example:

Index Element

0 10
1 20
2 30
3 40

FRONT and REAR pointers manage operations.

Queue Using Linked List

Each node contains:

• Data

• Next Pointer

Example:

FRONT
↓
10 → 20 → 30 → 40
↑
REAR

Advantages:

• Dynamic size

• No overflow unless memory is exhausted

Applications of Queue

Queues are widely used in:

CPU Scheduling

Processes wait in ready queues.

Printer Spooling

Print jobs are processed in order.

Network Communication

Packet management.

Customer Service Systems

Ticket counters and call centers.

Breadth First Search (BFS)

Graph traversal algorithm.

Quick Revision Summary

Stack

• Linear Data Structure

• LIFO Principle

• Operations: Push, Pop, Peek

Stack Problems

• Overflow

• Underflow

Expression Types
 • Infix

• Prefix

• Postfix

Recursion

• Function calls itself

• Requires Base Condition

Runtime Stack

• Stores function calls

Queue

• FIFO Principle

• Operations: Enqueue, Dequeue

Types of Queue

• Simple Queue

• Circular Queue

• Deque

• Priority Queue

Applications

• CPU Scheduling

• Printer Queue

• Network Systems

• BFS Traversal

UNIT 4: GRAPHS & TREES

Introduction to Graph

A Graph is a non-linear data structure used to represent relationships between different

• Vertices (Nodes)

• Edges (Connections)

Mathematically,

G = (V, E)

Where:

• V = Set of Vertices

• E = Set of Edges

Example of Graph

Consider four cities connected by roads.

A
/\
B---C
\
D

Here:

• A, B, C, D are vertices.

• Lines connecting them are edges.

Applications of Graph

Graphs are used in:

• Social Networks

• Google Maps

• Computer Networks

• Airline Routes

• Facebook Friend Suggestions

• Network Routing
Basic Terminology of Graph

Understanding graph terminology is very important.

Vertex (Node)

A point in a graph.

Example:

A, B, C, D

Edge

A connection between two vertices.

Example:

A ---- B

Adjacent Vertices

Two vertices connected by an edge.

Example:

A ---- B

A and B are adjacent vertices.

Degree of a Vertex

The number of edges connected to a vertex.

Example:

B
|
A---C---D

Degree of C = 3

Path

A sequence of connected vertices.

A→B→C→D

Cycle

A path that starts and ends at the same vertex.

Example:

A→B→C→A

Types of Graph

Undirected Graph

Edges have no direction.

Example:

A ----- B

Both vertices can communicate with each other.

Directed Graph (Digraph)

Edges have direction.

Example:

A→B

Communication is only from A to B.

Weighted Graph

Edges contain weights or costs.

Example:

A --5-- B

Weight = 5

Used in shortest path problems.

Graphs are represented mainly in two ways.

Adjacency Matrix

A graph is represented using a matrix.

Example:

ABC

A 011
B 101
C 110

Where:

• 1 = Edge exists

• 0 = No edge

Advantages

• Easy implementation

• Fast edge lookup

Disadvantages

• Wastes memory for sparse graphs

Adjacency List

Each vertex stores a list of connected vertices.

Example:

A→B→C

B→A→C
C→A→B

Advantages

• Saves memory

• Efficient for sparse graphs

Disadvantages

• Edge searching is slower

Graph Traversal

Traversal means visiting all vertices of a graph.

Two important traversal techniques are:

• Breadth First Search (BFS)

• Depth First Search (DFS)

Breadth First Search (BFS)

BFS visits vertices level by level.

It uses a Queue data structure.

Example:

A
/\
B C
/
D

Traversal:

A→B→C→D

Steps of BFS
 1. Start from source vertex.

2. Visit vertex.

3. Insert adjacent vertices into queue.

4. Repeat until queue becomes empty.

Applications of BFS

• Shortest Path

• Network Broadcasting

• Social Networks

• Web Crawling

Depth First Search (DFS)

DFS visits vertices as deep as possible before backtracking.

It uses:

• Stack

• Recursion

Example:

A
/\
B C
/
D

Traversal:

A→B→D→C

Steps of DFS

1. Visit starting vertex.

2. Move to an unvisited adjacent vertex.

3. Continue until no vertex remains.

Applications of DFS

• Path Finding

• Cycle Detection

• Topological Sorting

• Maze Solving

Introduction to Tree

A Tree is a special type of non-linear data structure.

It consists of nodes connected by edges.

Unlike graphs, a tree has:

• No cycles

• One root node

• Hierarchical structure

Example of Tree

A
/ \
B C
/\
D E

A is the root node.

Why Trees are Used?

Trees are used to represent hierarchical relationships.

Examples:

• File Systems

• Organization Charts
 • Family Trees

• Databases

Terminology of Tree

Root Node

The topmost node of a tree.

Example:

is the root.

Parent Node

A node having child nodes.

Example:

A
|
B

A is the parent of B.

Child Node

A node connected below a parent.

Example:

A
|
B

B is the child of A.

Leaf Node

A node with no children.

D, E, C

Sibling Nodes

Nodes having the same parent.

Example:

B and C

are siblings.

Level

Distance from root node.

Example:

Level 0 → A

Level 1 → B, C

Level 2 → D, E

Height of Tree

The maximum level in the tree.

Example:

Height = 2

Binary Tree

A binary tree is a tree in which each node can have at most two children.

These are:

• Left Child

• Right Child

Example:
 A
/\
B C

Types of Binary Trees

Full Binary Tree

Every node has either:

• 0 children

• 2 children

Example:

A
/\
B C

Complete Binary Tree

All levels are completely filled except possibly the last level.

Nodes are filled from left to right.

Perfect Binary Tree

Every internal node has two children and all leaf nodes are at the same level.

Binary Tree Traversal

Traversal means visiting every node exactly once.

Three important traversals are:

• Preorder

• Inorder

• Postorder
Preorder Traversal

Sequence:

Root → Left → Right

Example:

A
/\
B C

Traversal:

ABC

Inorder Traversal

Sequence:

Left → Root → Right

Traversal:

BAC

Postorder Traversal

Sequence:

Left → Right → Root

Traversal:

BCA

Binary Search Tree (BST)

A Binary Search Tree is a special binary tree that follows the rule:

BST Property

Left Subtree < Root < Right Subtree

Example:

50
/ \
 30 70
/\ /\
20 40 60 80

Advantages of BST

• Fast searching

• Fast insertion

• Fast deletion

Average Time Complexity:

O(log n)

Searching in BST

To search an element:

1. Compare with root.

2. If smaller, move left.

3. If larger, move right.

4. Repeat until found.

Insertion in BST

New elements are inserted according to BST property.

Example:

Insert 65

50
/ \
30 70
/
60
\
65
Deletion in BST

Deletion has three cases:

Case 1

Node has no child.

Simply delete.

Case 2

Node has one child.

Replace node with child.

Case 3

Node has two children.

Replace node with:

• Inorder Successor
or

• Inorder Predecessor

Height Balanced Tree

A height-balanced tree is a tree in which the height difference between left and right
subtrees is small.

Balanced trees improve searching efficiency.

AVL Tree

AVL Tree is a self-balancing Binary Search Tree.

Developed by:

• Adelson-Velsky

• Landis

Hence the name AVL.

For every node:

𝐵𝑎𝑙𝑎𝑛𝑐𝑒 𝐹𝑎𝑐𝑡𝑜𝑟 = 𝐻𝑒𝑖𝑔ℎ𝑡(𝐿𝑒𝑓𝑡 𝑆𝑢𝑏𝑡𝑟𝑒𝑒) − 𝐻𝑒𝑖𝑔ℎ𝑡(𝑅𝑖𝑔ℎ𝑡 𝑆𝑢𝑏𝑡𝑟𝑒𝑒)

Allowed values:

-1, 0, +1

If balance factor exceeds this range, rotations are performed.

AVL Rotations

AVL trees maintain balance using rotations.

Types:

LL Rotation

Left-Left imbalance.

RR Rotation

Right-Right imbalance.

LR Rotation

Left-Right imbalance.

RL Rotation

Right-Left imbalance.

Advantages of AVL Tree

• Always balanced

• Faster searching

• Faster insertion

• Faster deletion

Time Complexity:
O(log n)

Quick Revision Summary

Graph

• Non-linear data structure.

• Consists of vertices and edges.

Graph Representation

• Adjacency Matrix

• Adjacency List

Graph Traversal

• BFS (Queue)

• DFS (Stack/Recursion)

Tree

• Hierarchical structure.

• No cycles.

Binary Tree

• Maximum two children.

Traversals

• Preorder → Root Left Right

• Inorder → Left Root Right

• Postorder → Left Right Root

Binary Search Tree

• Left < Root < Right

AVL Tree

• Self-balancing BST

• Balance Factor = -1, 0, +1

Applications

• Databases
• File Systems

• Search Engines

• Network Routing

• Artificial Intelligence