Unit 4: Trees

Question 1

Binary Tree

Answer 1

Definition: A binary tree is a hierarchical structure where each node has at most two children, referred to as the left child and the right child.
Properties:

Maximum number of nodes at level l is 2^l.
Maximum number of nodes in a binary tree of height h is 2^(h+1) - 1.

Question 2

Binary Tree Traversals

Answer 2

In-order: Left, Root, Right.
Pre-order: Root, Left, Right.
Post-order: Left, Right, Root.

Question 3

Binary Tree Structure

Answer 3

typedef struct BTreeNode {
int data;
struct BTreeNode *left;
struct BTreeNode *right;
} BTreeNode;

Question 4

In-order Traversal (Recursive)

Answer 4

void inOrder(BTreeNode *root) {
if (root) {
inOrder(root->left);
printf(“%d “, root->data);
inOrder(root->right);
}
}

Question 5

Pre-order Traversal (Recursive)

Answer 5

void preOrder(BTreeNode *root) {
if (root) {
printf(“%d “, root->data);
preOrder(root->left);
preOrder(root->right);
}
}

Question 6

Post-order Traversal (Recursive)

Answer 6

void postOrder(BTreeNode *root) {
if (root) {
postOrder(root->left);
postOrder(root->right);
printf(“%d “, root->data);
}
}

Question 7

Height of a Binary Tree

Answer 7

Definition: The height of a binary tree is the length of the longest path from the root to a leaf node.
function height(node):
if node is NULL:
return -1
return 1 + max(height(node.left), height(node.right))

int height(BTreeNode *node) {
if (node == NULL) return -1;
return 1 + max(height(node->left), height(node->right));
}

Question 8

Binary Search Tree (BST)

Answer 8

Definition: A BST is a binary tree with the left subtree containing only nodes with values less than the parent node, and the right subtree containing only nodes with values greater.
Properties:

Fast search, insert, and delete operations.

Question 9

Insertion in BST

Answer 9

function insert(node, key):
if node is NULL:
return new_node(key)
if key < node.key:
node.left = insert(node.left, key)
else if key > node.key:
node.right = insert(node.right, key)
return node

Question 10

Searching in BST

Pseudocode:

Answer 10

function search(node, key):
if node is NULL or node.key == key:
return node
if key < node.key:
return search(node.left, key)
return search(node.right, key)

Question 11

Deletion in BST

Answer 11

function delete(node, key):
if node is NULL:
return node
if key < node.key:
node.left = delete(node.left, key)
else if key > node.key:
node.right = delete(node.right, key)
else:
// Node with only one child or no child
if node.left is NULL:
return node.right
else if node.right is NULL:
return node.left
// Node with two children: Get the inorder successor
temp = minValueNode(node.right)
node.key = temp.key
node.right = delete(node.right, temp.key)
return node

Question 12

AVL Tree

Answer 12

Definition: An AVL tree is a self-balancing binary search tree where the difference between the heights of left and right subtrees cannot be more than one for all nodes.
Balancing Factor: For each node, it’s the height of the left subtree minus the height of the right subtree.

Question 13

Rotations in AVL Trees

Answer 13

Types:

Right Rotation: Used when a left-heavy tree is unbalanced.
Left Rotation: Used when a right-heavy tree is unbalanced.
Left-Right Rotation: A combination used when the left subtree is right-heavy.
Right-Left Rotation: A combination used when the right subtree is left-heavy.

Question 14

Insertion in AVL Tree

Answer 14

function insert(node, key):
if node is NULL:
return new_node(key)
if key < node.key:
node.left = insert(node.left, key)
else if key > node.key:
node.right = insert(node.right, key)
node.height = 1 + max(height(node.left), height(node.right))
balance = getBalance(node)
// Perform rotations based on balance
return node

Question 15

Deletion in AVL Tree

Answer 15

function delete(node, key):
if node is NULL:
return node
if key < node.key:
node.left = delete(node.left, key)
else if key > node.key:
node.right = delete(node.right, key)
else:
// Node with one child or no child
// Perform rotations if needed
return node

Question 15

Graph Definition

Answer 15

Definition: A graph is a collection of nodes (vertices) connected by edges. It can be directed or undirected, weighted or unweighted.
Components:

Vertices (V): The individual points in the graph.
Edges (E): The connections between vertices.

Question 16

Graph Representation

Answer 16

Adjacency Matrix: A 2D array to represent graph connections.
Adjacency List: A list of lists to represent graph connections.

Question 17

Adjacency Matrix Representation

Answer 17

define MAX 100

int adjMatrix[MAX][MAX];
adjMatrix[u][v] = 1

Question 18

Adjacency List Representation

Answer 18

typedef struct Node {
int vertex;
struct Node* next;
} Node;

typedef struct Graph {
int numVertices;
Node** adjLists;
} Graph;

Question 19

Graph Traversal: BFS

Answer 19

Breadth-First Search (BFS): Explores all neighbors at the present depth prior to moving on to nodes at the next depth level.
Algorithm:

Start at the root (or any arbitrary node).
Mark it as visited and enqueue it.
While the queue is not empty, dequeue a vertex, print it, and enqueue its unvisited neighbors.

Question 20

BFS Implementation in C

Answer 20

void BFS(Graph* graph, int startVertex) {
bool visited[MAX] = {false};
Queue q;
enqueue(&q, startVertex);
visited[startVertex] = true;

while (!isEmpty(&q)) {
    int currentVertex = dequeue(&q);
    printf("%d ", currentVertex);

    Node* temp = graph->adjLists[currentVertex];
    while (temp) {
        int adjVertex = temp->vertex;
        if (!visited[adjVertex]) {
            enqueue(&q, adjVertex);
            visited[adjVertex] = true;
        }
        temp = temp->next;
    }
} }

Question 21

Graph Traversal: DFS

Answer 21

Depth-First Search (DFS): Explores as far as possible along each branch before backing up.
Algorithm:

Start at the root (or any arbitrary node).
Mark it as visited and recursively visit each unvisited neighbor.

Question 22

DFS Implementation in C

Answer 22

void DFS(Graph* graph, int vertex, bool visited[]) {
visited[vertex] = true;
printf(“%d “, vertex);

Node* temp = graph->adjLists[vertex];
while (temp) {
    int adjVertex = temp->vertex;
    if (!visited[adjVertex]) {
        DFS(graph, adjVertex, visited);
    }
    temp = temp->next;
} }

Question 23

Graph Applications

Answer 23

Applications:

Social Networks: Representing users and connections.
Routing Algorithms: Finding shortest paths.
Network Flow Problems: Optimizing the flow of resources.

Question 24

Shortest Path Algorithms

Answer 24

Dijkstra’s Algorithm: Used for finding the shortest path from a single source vertex to all other vertices in a graph with non-negative weights.
Bellman-Ford Algorithm: Computes shortest paths from a single source vertex to all other vertices, allowing for negative weights.

Question 25

Dijkstra’s Algorithm Pseudocode

Answer 25

function Dijkstra(graph, source):
create a priority queue Q
for each vertex v in graph:
dist[v] = ∞
prev[v] = NULL
dist[source] = 0
Q.add(source, dist[source])

while Q is not empty:
    u = Q.extract_min()
    for each neighbor v of u:
        alt = dist[u] + length(u, v)
        if alt < dist[v]:
            dist[v] = alt
            prev[v] = u
            Q.decrease_priority(v, alt)

Question 26

Dijkstra’s Algorithm Implementation in C

Answer 26

void Dijkstra(Graph* graph, int startVertex) {
int dist[MAX]; // Distance from startVertex to each vertex
bool visited[MAX] = {false};

for (int i = 0; i < graph->numVertices; i++) {
    dist[i] = INT_MAX;
}
dist[startVertex] = 0;

for (int i = 0; i < graph->numVertices - 1; i++) {
    int u = minDistance(dist, visited, graph->numVertices);
    visited[u] = true;

    Node* temp = graph->adjLists[u];
    while (temp) {
        int v = temp->vertex;
        if (!visited[v] && dist[u] != INT_MAX && dist[u] + getEdgeWeight(graph, u, v) < dist[v]) {
            dist[v] = dist[u] + getEdgeWeight(graph, u, v);
        }
        temp = temp->next;
    }
} }

Question 27

Bellman-Ford Algorithm Pseudocode

Answer 27

function BellmanFord(graph, source):
for each vertex v in graph:
dist[v] = ∞
dist[source] = 0

for i from 1 to |V| - 1:
    for each edge (u, v) in graph:
        if dist[u] + weight(u, v) < dist[v]:
            dist[v] = dist[u] + weight(u, v)

for each edge (u, v) in graph:
    if dist[u] + weight(u, v) < dist[v]:
        return "Negative weight cycle detected"

Question 28

Bellman-Ford Implementation in C

Answer 28

void BellmanFord(Graph* graph, int startVertex) {
int dist[MAX];
for (int i = 0; i < graph->numVertices; i++) {
dist[i] = INT_MAX;
}
dist[startVertex] = 0;

for (int i = 1; i < graph->numVertices; i++) {
    for (int u = 0; u < graph->numVertices; u++) {
        Node* temp = graph->adjLists[u];
        while (temp) {
            int v = temp->vertex;
            if (dist[u] != INT_MAX && dist[u] + getEdgeWeight(graph, u, v) < dist[v]) {
                dist[v] = dist[u] + getEdgeWeight(graph, u, v);
            }
            temp = temp->next;
        }
    }
} }

Question 29

Bubble Sort

Answer 29

Definition: A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
Complexity: O(n²) in the average and worst cases.

Question 30

Bubble Sort Implementation in C

Answer 30

void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
// swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}

Question 31

Selection Sort

Answer 31

Definition: A sorting algorithm that divides the input into two parts: a sorted and an unsorted part. It repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the sorted part.
Complexity: O(n²) in all cases.

Question 32

Selection Sort Implementation in C

Answer 32

void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int minIndex = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
// swap arr[minIndex] and arr[i]
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}

Question 33

Insertion Sort

Answer 33

Definition: A simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms.
Complexity: O(n²) in the average and worst cases.

Question 34

Insertion Sort Implementation in C

Answer 34

void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

Question 35

Merge Sort

Answer 35

Definition: A divide-and-conquer algorithm that sorts by recursively dividing the array in half, sorting each half, and then merging the sorted halves.
Complexity: O(n log n) in all cases.

Question 36

Merge Sort Implementation in C

Answer 36

void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

int L[n1], R[n2];

for (i = 0; i < n1; i++)
    L[i] = arr[l + i];
for (j = 0; j < n2; j++)
    R[j] = arr[m + 1 + j];

i = 0; j = 0; k = l;

while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
        arr[k] = L[i];
        i++;
    } else {
        arr[k] = R[j];
        j++;
    }
    k++;
}
while (i < n1) {
    arr[k] = L[i];
    i++; k++;
}
while (j < n2) {
    arr[k] = R[j];
    j++; k++;
} }

void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

Question 37

Complexity Analysis

Answer 37

Definition: The analysis of the efficiency of algorithms in terms of time and space complexity.
Big O Notation: Used to describe the upper limit of the time complexity in terms of the input size.

Question 38

Space Complexity

Answer 38

Definition: The amount of memory space required by an algorithm as a function of the size of the input to the program.
Factors:

Auxiliary Space: Extra space or temporary space used by an algorithm.

Question 39

Time Complexity Examples

Answer 39

O(1): Constant time (e.g., accessing an array element).
O(n): Linear time (e.g., linear search).
O(n log n): Log-linear time (e.g., merge sort).
O(n²): Quadratic time (e.g., bubble sort).

Question 40

Recursion

Answer 40

Definition: A method of solving problems where the solution depends on solutions to smaller instances of the same problem.
Components:

Base Case: The condition under which the recursion ends.
Recursive Case: The part of the function where the recursion occurs.

Question 41

Applications of Hashing

Answer 41

Database Indexing: Fast data retrieval.
Caching: Storing frequently accessed data.
Data Integrity Checks: Ensuring data has not been altered.

Question 42

Graphs vs Trees

Answer 42

Definition: Both are data structures used to represent hierarchical data.
Graphs:

Can have cycles.
Can be directed or undirected.

Trees:

A special case of graphs with no cycles.
Always directed.

Question 43

Tree Traversals

Answer 43

In-Order Traversal: Left, Root, Right.
Pre-Order Traversal: Root, Left, Right.
Post-Order Traversal: Left, Right, Root.

Question 44

Recursive In-Order Traversal:

Answer 44

void inOrder(BTreeNode* root) {
if (root) {
inOrder(root->left);
printf(“%d “, root->data);
inOrder(root->right);
}
}

Question 45

Iterative In-Order Traversal:

Answer 45

void inOrderIterative(BTreeNode* root) {
Stack s = createStack();
BTreeNode* current = root;

while (current || !isEmpty(s)) {
    while (current) {
        push(s, current);
        current = current->left;
    }
    current = pop(s);
    printf("%d ", current->data);
    current = current->right;
} }

Question 46

Applications of Trees

Answer 46

File Systems: Hierarchical storage systems.
Databases: For indexing and retrieval.
Decision Making: Representing decisions and outcomes.

Question 47

Sorting vs Searching Algorithms

Answer 47

Sorting Algorithms: Rearrange items in a specific order.
Searching Algorithms: Find a specific item in a collection.

Question 48

Searching Algorithms Overview

Answer 48

Linear Search: O(n)
Binary Search: O(log n) - requires a sorted array.

Question 49

Binary Search Implementation in C

Answer 49

int binarySearch(int arr[], int n, int key) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid; // Found
else if (arr[mid] < key)
left = mid + 1; // Search right
else
right = mid - 1; // Search left
}
return -1; // Not found