Trees, Heaps, Hashing & Graphs in C: BST Traversals, Heap Sort, Hash Tables & Graph Representations

1. What is a binary tree?

A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left and right child. It’s used for tasks like hierarchical data representation and searching.

2. What is a Binary Search Tree (BST)?

A BST is a binary tree where for each node, the left subtree contains values less than the node, and the right subtree contains values greater than the node, enabling efficient searching and sorting.

3. How do you define a binary tree node in C?

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};
      

4. What are the types of binary tree traversals?

Traversals visit all nodes in a specific order:

5. Can you give an example of BST operations and traversals in C?

Example: BST insertion and inorder traversal.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

struct Node* insert(struct Node* root, int data) {
    if (root == NULL) return createNode(data);
    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);
    return root;
}

void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data); // Visit root
        inorder(root->right);
    }
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    inorder(root); // Output: 20 30 40 50 70
    return 0;
}
      

6. What are the time complexities of BST operations?

Insertion/Search/Deletion:

Traversal (Inorder/Preorder/Postorder): O(n)

7. What are the advantages and disadvantages of BST?

8. What is a heap?

A heap is a complete binary tree that satisfies the heap property:

Heaps are used for priority queues and heap sort.

9. How do you implement a min heap in C?

Example: Array-based min heap with insertion.

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

struct MinHeap {
    int arr[MAX];
    int size;
};

void init(struct MinHeap* h) {
    h->size = 0;
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapifyUp(struct MinHeap* h, int index) {
    int parent = (index - 1) / 2;
    if (index > 0 && h->arr[index] < h->arr[parent]) {
        swap(&h->arr[index], &h->arr[parent]);
        heapifyUp(h, parent);
    }
}

void insert(struct MinHeap* h, int value) {
    if (h->size < MAX) {
        h->arr[h->size] = value;
        heapifyUp(h, h->size);
        h->size++;
    }
}

void printHeap(struct MinHeap* h) {
    for (int i = 0; i < h->size; i++) {
        printf("%d ", h->arr[i]);
    }
    printf("\n");
}

int main() {
    struct MinHeap h;
    init(&h);
    insert(&h, 10);
    insert(&h, 5);
    insert(&h, 15);
    insert(&h, 3);
    printHeap(&h); // Output: 3 5 15 10
    return 0;
}
      

10. What is heap sort?

Heap sort is a comparison-based sorting algorithm that uses a max heap to sort elements in ascending order by repeatedly extracting the maximum element.

11. Can you give an example of heap sort in C?

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) // Build max heap
        heapify(arr, n, i);
    for (int i = n - 1; i > 0; i--) { // Extract max
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {5, 2, 8, 1, 9};
    int n = 5;
    heapSort(arr, n);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]); // Output: 1 2 5 8 9
    return 0;
}
      

12. What are the time complexities of heap operations?

13. What are the advantages and disadvantages of heaps?

14. What is hashing?

Hashing maps data (keys) to indices in a hash table using a hash function, enabling fast retrieval (O(1) average case). Collisions occur when multiple keys map to the same index.

15. What is a hash table?

A hash table is a data structure that stores key-value pairs, using a hash function to compute an index for storage and retrieval.

16. What are common collision resolution techniques?

17. Can you give an example of a hash table with chaining in C?

#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

struct Node {
    int data;
    struct Node* next;
};

struct HashTable {
    struct Node* table[SIZE];
};

void init(struct HashTable* ht) {
    for (int i = 0; i < SIZE; i++) ht->table[i] = NULL;
}

int hashFunction(int key) {
    return key % SIZE;
}

void insert(struct HashTable* ht, int value) {
    int index = hashFunction(value);
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = ht->table[index];
    ht->table[index] = newNode;
}

void printTable(struct HashTable* ht) {
    for (int i = 0; i < SIZE; i++) {
        printf("Index %d: ", i);
        struct Node* temp = ht->table[i];
        while (temp) {
            printf("%d -> ", temp->data);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    struct HashTable ht;
    init(&ht);
    insert(&ht, 10); // Maps to index 0
    insert(&ht, 20); // Maps to index 0 (collision)
    insert(&ht, 15); // Maps to index 5
    printTable(&ht); // Output: Index 0: 20 -> 10 -> NULL, Index 5: 15 -> NULL, ...
    return 0;
}
      

18. What are the time complexities of hash table operations?

Insertion/Search/Deletion:

19. What are the advantages and disadvantages of hashing?

20. What is a graph?

A graph is a data structure with vertices (nodes) connected by edges (links), used to model relationships like networks or social connections.

21. What are key graph terminologies?

22. How do you represent a graph in C?

Two common representations:

23. Can you give an example of an adjacency list in C?

#include <stdio.h>
#include <stdlib.h>

#define V 4 // Number of vertices

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

struct Graph {
    struct Node* adjList[V];
};

void init(struct Graph* g) {
    for (int i = 0; i < V; i++) g->adjList[i] = NULL;
}

void addEdge(struct Graph* g, int src, int dest) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = dest;
    newNode->next = g->adjList[src];
    g->adjList[src] = newNode;
}

void printGraph(struct Graph* g) {
    for (int i = 0; i < V; i++) {
        printf("Vertex %d: ", i);
        struct Node* temp = g->adjList[i];
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    struct Graph g;
    init(&g);
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    printGraph(&g); // Output: Vertex 0: 2 -> 1 -> NULL, Vertex 1: 3 -> NULL, ...
    return 0;
}
      

24. What is an adjacency matrix?

Example:

#include <stdio.h>

#define V 4

void initMatrix(int matrix[V][V]) {
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            matrix[i][j] = 0;
}

void addEdge(int matrix[V][V], int src, int dest) {
    matrix[src][dest] = 1; // Directed graph
}

void printMatrix(int matrix[V][V]) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int matrix[V][V];
    initMatrix(matrix);
    addEdge(matrix, 0, 1);
    addEdge(matrix, 0, 2);
    addEdge(matrix, 1, 3);
    printMatrix(matrix); // Output: 0 1 1 0 \n 0 0 0 1 \n ...
    return 0;
}
      

25. What are the advantages and disadvantages of adjacency matrix vs. list?

Adjacency Matrix:

Adjacency List:

26. What are common graph algorithms?

Frequently asked questions

What is a Binary Search Tree (BST)?

Binary tree with left < root < right order. Average O(log n) insert/search/delete.

What are tree traversals?

Inorder (sorted for BST), pre order, post order. All O(n) time.

What is a Heap and Heap Sort?

Complete binary tree with min/max property. Heap Sort: O(n log n) using max heap.

What is a Hash Table?

Key-value storage with hash function. Average O(1) operations, collisions via chaining/open addressing.

How to represent Graphs in C?

Adjacency List (sparse, O(V+E) space) or Matrix (dense, O(V²) space).

Time complexities of these data structures?

BST: O(log n) avg. Heap: O(log n) insert/delete. Hash: O(1) avg. Graph ops: O(V+E).