Trees in Data Structures

Definition
 A Tree structure is a way of representing the hierarchical nature of a structure in a graphical form.
 A binary tree is a hierarchical data structure in which each node has at most two children: left and
right.
 Commonly used in searching, sorting, and representing hierarchical data.

Basic Structure:
 Each node is usually represented by a Node class containing:
 Data (e.g., integer key)
 Left and right child pointers

1. Terminology of Trees
 Tree: A hierarchical data struc
structure
ture consisting of nodes, with one node as the root and all other
nodes as subtrees of the root.
 Node:: A basic element in a tree data structure
structure.
 Root:: The topmost node of a tree
tree.
 Parent:: A node that has one or more child nodes
nodes.
 Child: A node that is directly connected to and descends from a parent node
node..
 Leaf Node (or Terminal Node):
Node) A node that has no children.
 Internal Node:: A node that has at least one child.
child
 Sibling:: Nodes that share the same parent
parent.
 Edge:: The connection or link between two nodes
nodes.
 Level of Node:: The distance of a node from the root, where the root is at level 0.
0
 Height of Tree:: The maximum level of any node in the tree
tree.
 Depth of Node:: The distance from the root to the node.
node
 Degree of Node:: The number of children a node has.
has
 Degree of Tree:: The maximum degree among all nodes in the tree.
tree

Faculty: B. Thilak Reddy

 Basic Operations
A Binary Tree Abstract Data Type (ADT) supports the following operations:
 CreateTree() → Ini alize a tree.
 Insert(value) → Add a node to the tree.
 Delete(value) → Remove a node.
 Traversal → Visit nodes in a specific order:
o Preorder: Root → Le → Right
o Inorder: Left → Root → Right
o Postorder: Left → Right → Root
o Level order (Breadth-First): Visit level by level
Find Tree traversals for following Tree:

Inorder Traversal
An inorder traversal of a binary tree visits the nodes in the following order:
left subtree, root, right subtree.
1. Step 1: The traversal starts at the root node, 1, and moves to its left subtree, which is rooted at 2. From 2,
it moves to its left subtree, which is the node 4. Node 4 has no left or right subtrees, so it's visited. The
traversal order so far is 4.
2. Step 2: After the left subtree of node 2 (which is just 4) is completely visited, node 2 is visited. The
traversal order is now 4 → 2.
3. Step 3: The right subtree of node 2 is traversed, moving to node 5. Node 5 has no left subtree, so it's
visited. There's no right subtree, so the traversal moves back up.
The traversal order is 4 → 2 → 5.
4. Step 4: With the left subtree of node 1 completely visited, node 1 is now visited. The traversal order is 4
→ 2 → 5 → 1.
5. Step 5: The right subtree of node 1 is traversed, moving to node 3. Node 3 has no left subtree, so it's
visited. The traversal order is 4 → 2 → 5 → 1 → 3.
6. Step 6: The right subtree of node 3 is traversed, and node 6 is visited. Since all nodes have been
traversed, the process ends. The final traversal order is 4 → 2 → 5 → 1 → 3 → 6.
Faculty: B. Thilak Reddy
 Postorder Traversal
A postorder traversal of a binary tree visits the nodes in the following order:
left subtree, right subtree, root.
1. Step 1: The traversal begins at the root, 1, and moves to its left subtree, 2, and then to the leftmost node,
4. Since node 4 has no subtrees, it's the first node visited.
The traversal order is 4.
2. Step 2: After the left subtree of node 2 (node 4) is visited, the traversal moves to the right subtree of 2,
which is node 5. Node 5 has no subtrees, so it's visited.
The traversal order is 4 → 5.
3. Step 3: Both the left and right subtrees of node 2 have been visited, so node 2 itself is now visited. The
traversal order is 4 → 5 → 2.
4. Step 4: With the left subtree of node 1 traversed, the traversal moves to the right subtree of 1, which is
rooted at 3. Since 3 has no left subtree, the traversal moves to its right subtree, node 6 17. Node 6 has no
subtrees and is visited. The traversal order is 4 → 5 → 2 → 6.
5. Step 5: The subtrees of node 3 are now fully traversed, so node 3 is visited.
The traversal order is 4 → 5 → 2 → 6 → 3.
6. Step 6: All subtrees of node 1 have been traversed, so node 1 is visited, and the traversal ends. The final
traversal order is 4 → 5 → 2 → 6 → 3 → 1.

Preorder Traversal
A preorder traversal of a binary tree visits the nodes in the following order:
root, left subtree, right subtree.
1. Step 1: The traversal begins by visiting the root node, 1. The traversal order is 1.
2. Step 2: The traversal then moves to the left subtree of node 1, and the root of that subtree, node 2, is
visited. The traversal order is 1 → 2.
3. Step 3: The traversal moves to the left subtree of node 2, and the root of that subtree, node 4, is visited.
The traversal order is 1 → 2 → 4.
4. Step 4: The left subtree of node 2 is fully visited. The traversal moves to the right subtree of
2, and node 5 is visited. The traversal order is 1 → 2 → 4 → 5.
5. Step 5: The left subtree of node 1 is now completely visited. The traversal moves to the right subtree of 1,
and the root node 3 is visited. The traversal order is 1 → 2 → 4 → 5 → 3.
6. Step 6: Node 3 has no left subtree, so the traversal moves directly to its right subtree, and node 6 is
visited. The traversal ends as all nodes have been visited.
The final traversal order is 1 → 2 → 4 → 5 → 3 → 6.

Faculty: B. Thilak Reddy

Representation of Trees using Linked Representation:
Each node contains:
data → value of the node
pointer(s) → references to children nodes
Code:
// Node class representing each node in the tree
class Node {
int data;
Node left, right;
Node(int value) {
data = value;
left = right = null;
}
}
// BinaryTree class
class BinaryTree {
Node root;
// Constructor
BinaryTree() {
root = null;
}
// Preorder Traversal (Root -> Left -> Right)
void preorder(Node node) {
if (node == null) return;
[Link]([Link] + " ");
preorder([Link]);
preorder([Link]);
}
// Inorder Traversal (Left -> Root -> Right)
void inorder(Node node) {
if (node == null) return;
inorder([Link]);
[Link]([Link] + " ");
inorder([Link]);
}

Faculty: B. Thilak Reddy

 // Postorder Traversal (Left -> Right -> Root)
void postorder(Node node) {
if (node == null) return;
postorder([Link]);
postorder([Link]);
[Link]([Link] + " ");
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
[Link] = new Node(10);
[Link] = new Node(20);
[Link] = new Node(30);
[Link] = new Node(40);
[Link] = new Node(50);
[Link] = new Node(60);
// Traversals
[Link]("Preorder Traversal: ");
[Link]([Link]);
[Link]();
[Link]("Inorder Traversal: ");
[Link]([Link]);
[Link]();
[Link]("Postorder Traversal: ");
[Link]([Link]);
[Link]();
}
}

Heap
A Heap is a complete binary tree that satisfies the heap property:
Max Heap:
A Max Heap is a complete binary tree where the value of a parent node is always greater than or equal
to the value of its children. This property ensures that the maximum element is always at the root of the
tree.
o Value of parent ≥ value of children.
o Maximum element at the root.
Faculty: B. Thilak Reddy
Min Heap:
A Min Heap is a complete binary tree where the value of a parent node is always less than or equal to the
value of its children. This property guarantees that the minimum element is always at the root of the
tree.
o Value of parent ≤ value of children.
o Minimum element at the root.
Min Heap Implementation
A min heap can be built using an ArrayList to represent the heap structure. The index of a node's children
and parent can be calculated using the following formulas:
 Parent of node at index i: (i−1)/2
 Left child of node at index i: 2i+1
 Right child of node at index i: 2i+2
Min Heap Example:
In a Min Heap, every parent node is smaller than or equal to its children.
 So, the smallest element is always at the root (index 0).
Example: Insert numbers 10, 20, 15, 30, 40
Step 1: Insert 10 → Heap = [10]
(No parent, so done)
Step 2: Insert 20 → Heap = [10, 20]
 Parent of 20 is (1−1)/2 = 0 → 10
 Since 20 > 10, order is fine.
Step 3: Insert 15 → Heap = [10, 20, 15]
 Parent of 15 is (2−1)/2 = 0 → 10
 Since 15 > 10, order is fine.
Step 4: Insert 30 → Heap = [10, 20, 15, 30]
 Parent of 30 is (3−1)/2 = 1 → 20
 Since 30 > 20, order is fine.
Step 5: Insert 40 → Heap = [10, 20, 15, 30, 40]
 Parent of 40 is (4−1)/2 = 1 → 20
 Since 40 > 20, order is fine.
Final Min Heap:
10
/ \
20 15
/ \
30 40
Faculty: B. Thilak Reddy
Max Heap Explanation
In a Max Heap, every parent node is greater than or equal to its children.
 So, the largest element is always at the root (index 0).
Example: Insert numbers 10, 20, 15, 30, 40
Step 1: Insert 10 → Heap = [10]
Step 2: Insert 20 → Heap = [10, 20]
 Parent of 20 is 10
 Since 20 > 10, swap → [20, 10].
Step 3: Insert 15 → Heap = [20, 10, 15]
 Parent of 15 is 20
 Since 15 < 20, no swap.
Step 4: Insert 30 → Heap = [20, 10, 15, 30]
 Parent of 30 is 10
 Since 30 > 10, swap → [20, 30, 15, 10].
 Now parent of 30 is 20 → 30 > 20, swap again → [30, 20, 15, 10].
Step 5: Insert 40 → Heap = [30, 20, 15, 10, 40]
 Parent of 40 is 20
 Swap → [30, 40, 15, 10, 20]
 Now parent of 40 is 30 → swap again → [40, 30, 15, 10, 20].
Final Max Heap:
40
/ \
30 15
/ \
10 20

Feature Min Heap Max Heap

Root Smallest element Largest element
Usage Priority queues (smallest job first) Heap Sort, scheduling (largest first)
Condition Parent ≤ Children Parent ≥ Children

import [Link];
public class MinHeapExample {
public static void main(String[] args) {
// Min Heap (default behavior of PriorityQueue)

Faculty: B. Thilak Reddy

 PriorityQueue<Integer> minHeap = new PriorityQueue<>();
[Link](10);
[Link](20);
[Link](15);
[Link](30);
[Link](40);
// Print heap (not sorted order, internal heap structure)
[Link]("Min Heap: " + minHeap);
}
}
Min Heap: [10, 20, 15, 30, 40]

Max Heap Implementation

A max heap is implemented similarly, but the comparison logic is reversed. The formulas for parent and
child indices are the same.
import [Link];
import [Link];
public class MaxHeapExample {
public static void main(String[] args) {
// Max Heap (reverse order comparator)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>([Link]());
// Insert elements
[Link](10);
[Link](20);
[Link](15);
[Link](30);
[Link](40);
// Print heap (not sorted order, internal heap structure)
[Link]("Max Heap: " + maxHeap);
}
}
Max Heap: [40, 30, 15, 10, 20]
Heap elements (descending): 40 30 20 15 10

Faculty: B. Thilak Reddy

Graphs - Introduction
In the real world, many problems can be modeled using objects and the connections between them.
Example: In an airline route map, cities are objects (nodes) and flights are connections (edges).
Graphs are powerful data structures that help solve such problems. They are widely used in:
 Route planning (roads, railways, airlines)
 Networking (computer, telephone, internet)
 Clustering & optimization problems
Definition: A Graph (G) is a mathematical structure used to represent pairwise relationships among a set
of objects. It consists of:
 V → a set of ver ces (nodes)
 E → a set of edges (connec ons)
Formally: G = (V,E)

An ordered pair of vertices if the graph is directed (digraph) -

Example:

Terminology
1. Vertex (Node):
o Represents an object (e.g., a city, computer, or person).
o A vertex can store data (like name, population, ID).
2. Edge:
o Represents a connection or relationship between two vertices.
o Can store weights (distance, cost, capacity).
3. Undirected Graph:
o Edge {u, v} means a two-way connection.
o Example: A bidirectional road between cities.

4. Directed Graph (Digraph):

o Edge (u, v) means a one-way connection (from u to v).
o Example: One-way streets, or “following” in social media.
o u → tail, v → head of the edge.

Faculty: B. Thilak Reddy

5. Weighted Graph:
o Each edge has a weight (e.g., distance, cost, time).

6. Unweighted Graph:
o Edges have no weights, only presence/absence of a connection matters.
7. Path:
o A sequence of vertices connected by edge
edges.
8. Shortest Path:
o Path between two vertices with minimum total weight (if weighted).
9. Minimum Spanning Tree (MST):
o A subgraph that connects all vertices with minimum possible total edge weight (no cycles).
Applications of Graphs
 Representing relationships between components in electronic circuits
 Transportation networks: Highway network, Flight network
 Computer networks: Local area network, Internet, Web
 Databases: For representing ER (Entity Relationsh
Relationship) diagrams in databases, for representing
epresenting
dependency of tables in databases.
databases
Graph Representation in DSA
When we use graphs in programs, we need a way to store them in memory.. There are mainly three ways
to represent a graph:
1. Adjacency Matrix
 A 2D array of size V×V (where VV = number of vertices).
 If there is an edge between vertex i and vertex j:
o matrix[i][j] = 1 (or weight if weighted graph).
o Otherwise matrix[i][j] = 00.

Faculty: B. Thilak Reddy

Example (Undirected Graph):

Adjacency Matrix:

2. Adjacency List
An adjacency list is a way to represent a graph using an array or list where each index corresponds to a
vertex. Each element in the array is a linked list of the vertices that are adjacent to the vertex at that
index.
 Each vertex stores a list of its neighbors.
 Implemented using Array + Linked List (or ArrayList in Java).
Example (same graph):

Here is the adjacency list for your graph:

 A is adjacent to B and D.
 B is adjacent to C.
 C is adjacent to A and D.
 D is adjacent to itself (a self-loop) and C.
3. Incidence Matrix
An incidence Matrix is a way of representing a graph in matrix form. It shows relationship (incidence)
between vertices (nodes) and edges.

 A V × E matrix (vertices × edges), Rows = vertices, Columns = edges.

 matrix[i][j] = 1 if vertex i is part of edge j, else 0.

Faculty: B. Thilak Reddy
Example:
For vertices V={0,1,2} and edges E={(0,1),(1,2)} for undirectred graph.
e1 (0-1) e2 (1-2)
0 1 0
1 1 1
2 0 1

For a directed edge e = (u->v):

 I[u][e] = -1 (Edge leaves u)
 I[v][e] = 1 (Edge enters v)
 0 otherwise
For vertices V={1,2,3} E={e1=(1->2), e2 = (2->3), e3 = (1->3)} for directed graph.
e1 (1->2) e2 (2->3) e3(1->3)
V1 -1 0 -1
V2 1 -1 0
V3 0 1 1

Graph traversals
Graph traversals are algorithms that systematically visit all the vertices (nodes) and edges of a graph. The
two primary methods are Breadth -First Search (BFS) and Depth-First Search (DFS).
Breadth-First Search (BFS)
BFS explores a graph level by level. It starts at a source node, then visits all its immediate neighbors, then
all their unvisited neighbors, and so on. It's like ripples spreading out in a pond.
BFS uses a queue (a First-In, First-Out or FIFO data structure) to keep track of the nodes to be visited.
BFS Algorithm
1. Start with a vertex (source).
2. Visit it, mark it as visited, and insert into queue.
3. While the queue is not empty:
Remove the front node from the queue.
Visit all its unvisited adjacent vertices:
o Mark them as visited.
o Insert them into the queue.
4. Repeat until the queue becomes empty.
Starts at a source node → visits all neighbors first → then moves to next level.

Faculty: B. Thilak Reddy

Example:

Steps:
Step 1: Start with A → Mark visited → Queue = [A]
Step 2: Dequeue A, visit neighbors B → Queue = [B]
Step 3: Dequeue B, visit neighbors C, H → Queue = [C, H]
Step 4: Dequeue C, visit neighbors D, E → Queue = [H, D, E]
Step 5: Dequeue H, no new neighbors → Queue = [D, E]
Step 6: Dequeue D, no new neighbors → Queue = [E]
Step 7: Dequeue E, visit neighbors F, G → Queue = [F, G]
Step 8: Dequeue F, no new neighbors → Queue = [G]
Step 9: Dequeue G, no new neighbors → Queue = [] (empty)
Final BFS Traversal Order: A → B → C → H → D → E → F → G

BFS in Java
import [Link].*;

Faculty: B. Thilak Reddy

class Graph {
private int V; // number of vertices
private LinkedList<Integer>[] adj; // adjacency list
// Constructor
Graph(int V) {
this.V = V;
adj = new LinkedList[V];
for (int i = 0; i < V; i++) {
adj[i] = new LinkedList<>();
}
}
void addEdge(int v, int w) { // Add edge to graph (undirected for simplicity)
adj[v].add(w);
adj[w].add(v); // remove this line if graph is directed
}
// BFS function
void BFS(int start) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
[Link](start);
while (![Link]()) {
int v = [Link](); // remove from queue
[Link](v + " ");
// Traverse all adjacent vertices
for (int i = 0; i < adj[v].size(); i++) {
int u = adj[v].get(i); // get the neighbor at index i
if (!visited[u]) {
visited[u] = true;
[Link](u);
}
}
}
}
public static void main(String[] args) {
Graph g = new Graph(5); // Graph with 5 vertices (0 to 4)
Faculty: B. Thilak Reddy
 // Add edges
[Link](0, 1);
[Link](0, 2);
[Link](1, 3);
[Link](1, 4);
[Link]("BFS starting from vertex 0: ");
[Link](0); // Start BFS from vertex 0
}
}
Depth First Search (DFS)
Depth First Search (DFS) is a graph traversal algorithm. In DFS, we explore as far as possible along one
branch (deep into the graph) before backtracking and exploring other branches.
 It explores as far as possible along each branch before backtracking.
 DFS uses a stack (explicit stack or system call stack via recursion).
How DFS Works
 Start from the source node (say v).
 Mark v as visited.
 Process the node (print/store it).
 Go to an adjacent unvisited node and recursively apply DFS.
 If no adjacent unvisited nodes are found, backtrack.
 Repeat until all nodes are visited.
Example:

Faculty: B. Thilak Reddy

Faculty: B. Thilak Reddy
Steps to DFS
1. Start at A, mark as visited → Stack = [A]
2. Visit neighbor B, mark as visited → Stack = [A, B]
3. From B, visit C, mark as visited → Stack = [A, B, C]
4. From C, visit D, mark as visited → Stack = [A, B, C, D]
5. No more unvisited neighbors of D, backtrack to C.
6. From C, next unvisited neighbor is E, mark as visited → Stack = [A, B, C, E]
7. From E, visit F, mark as visited → Stack = [A, B, C, E, F]
8. No more unvisited neighbors of F, backtrack to E.
9. From E, next unvisited neighbor is G, mark as visited → Stack = [A, B, C, E, G]
10. No more unvisited neighbors of G, backtrack to E.

Faculty: B. Thilak Reddy

 11. From E, next unvisited neighbor is H, but H is connected via B. Since B already visited, check if H is
unvisited → Yes, visit H → Stack = [A, B, C, E, H].
12. No more unvisited neighbors of H, backtrack.

Final DFS Traversal Order: A → B → C → D → E → F → G → H

DFS using Java

import [Link].*;
class Graph {
private int V;
private LinkedList<Integer>[] adj;
private boolean[] visited;
Graph(int v) {
V = v;
adj = new LinkedList[v];
visited = new boolean[v];
for (int i = 0; i < v; i++) {
adj[i] = new LinkedList<>();
}
}
void addEdge(int v, int w) {
adj[v].add(w); // directed edge v -> w
}
void DFS(int v) {
visited[v] = true;
[Link](v + " ");
for (int i = 0; i < adj[v].size(); i++) {
int n = adj[v].get(i);
if (!visited[n]) {
DFS(n);
}
}
}
public static void main(String[] args) {
Graph g = new Graph(7);
[Link](1, 2);
[Link](1, 3);

Faculty: B. Thilak Reddy

 [Link](2, 4);
[Link](2, 5);
[Link](3, 6);
[Link]("DFS starting from node 1:");
[Link](1);
}
} public static void main(String[] args) {
Graph g = new Graph(5); // Graph with 5 vertices (0 to 4)
// Add edges
[Link](0, 1);
[Link](0, 2);
[Link](1, 3);
[Link](1, 4);
[Link]("DFS starting from vertex 0: ");
[Link](0); // Start DFS from vertex 0
}
}

Faculty: B. Thilak Reddy