Recursion & Backtracking in C: Tree Traversals, N-Queens, Sudoku, Subsets & Permutations with Code Examples

1. What is recursion in programming?

Recursion is a process where a function calls itself to solve smaller instances of the same problem until a base case is reached. It's widely used in problems with a recursive structure, like tree traversals.

2. How does recursion relate to trees?

Trees are inherently recursive: each node has subtrees (left and right children). Recursive algorithms naturally fit tree operations like traversals, searching, or height calculation, as each subtree is a smaller problem instance.

3. What are the components of a recursive function?

• Base Case: Condition to stop recursion.
• Recursive Case: Calls the function with a smaller input.
• Progress: Ensures the input moves toward the base case.

4. Can you give an example of recursion with a binary tree in C?

Example: Inorder traversal of a binary tree.

#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;
}

void inorder(struct Node* root) {
    if (root == NULL) return; // Base case
    inorder(root->left); // Recursive case: left subtree
    printf("%d ", root->data); // Process root
    inorder(root->right); // Recursive case: right subtree
}

int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    inorder(root); // Output: 4 2 5 1 3
    return 0;
}
      

5. What are the advantages and disadvantages of recursion?

• Advantages: Simplifies code for problems with recursive structure (e.g., trees, graphs), natural for divide-and-conquer.
• Disadvantages: Stack overflow for deep recursion, higher memory usage (O(n) stack space), slower than iterative solutions in some cases.

6. What is the time and space complexity of recursion in trees?

For tree traversals (e.g., inorder):

• Time Complexity: O(n) (visit each node once).
• Space Complexity: O(h) (recursion stack, h = tree height; O(log n) for balanced trees, O(n) for skewed trees).

7. What is backtracking?

Backtracking is an algorithmic technique that incrementally builds solutions and abandons partial solutions (backtracks) when they cannot lead to a valid solution. It's like exploring a decision tree and pruning invalid paths.

8. How does backtracking work?

• Make a choice (e.g., place a queen in N-Queens).
• Recursively explore the next choices.
• If the choice leads to an invalid state, undo it (backtrack) and try another.
• Stop when a solution is found or all options are exhausted.

9. What are key features of backtracking?

• Recursive: Uses recursion to explore choices.
• State Management: Tracks and reverts state changes (e.g., board modifications).
• Pruning: Avoids exploring invalid paths early.
• Exhaustive Search: Tries all valid combinations systematically.

10. What are common backtracking problems?

N-Queens, Sudoku, Subsets, Permutations, Graph Coloring, Knapsack.

11. What is the time complexity of backtracking?

Typically exponential (e.g., O(n!) for permutations), but pruning reduces practical runtime. Specific problems vary (e.g., O(n!) for N-Queens).

12. What is the N-Queens problem?

The N-Queens problem involves placing N queens on an N×N chessboard such that no two queens threaten each other (no shared row, column, or diagonal).

13. How is backtracking used in N-Queens?

Place queens row by row, checking if each placement is safe. If a placement leads to a conflict, backtrack and try a different column.

14. Can you give an example of N-Queens in C?

#include <stdio.h>
#include <stdbool.h>

#define N 4

bool isSafe(int board[N][N], int row, int col) {
    for (int i = 0; i < col; i++) // Check row
        if (board[row][i]) return false;
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) // Upper diagonal
        if (board[i][j]) return false;
    for (int i = row, j = col; i < N && j >= 0; i++, j--) // Lower diagonal
        if (board[i][j]) return false;
    return true;
}

bool solveNQueensUtil(int board[N][N], int col) {
    if (col >= N) return true; // All queens placed
    for (int i = 0; i < N; i++) {
        if (isSafe(board, i, col)) {
            board[i][col] = 1; // Place queen
            if (solveNQueensUtil(board, col + 1)) return true;
            board[i][col] = 0; // Backtrack
        }
    }
    return false;
}

void printBoard(int board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) printf("%d ", board[i][j]);
        printf("\n");
    }
}

void solveNQueens() {
    int board[N][N] = {0};
    if (solveNQueensUtil(board, 0)) printBoard(board);
    else printf("No solution exists\n");
}

int main() {
    solveNQueens(); // Output: One valid placement (e.g., 0 1 0 0 \n 0 0 0 1 \n 1 0 0 0 \n 0 0 1 0)
    return 0;
}
      

15. What is the time complexity of N-Queens?

Time Complexity: O(n!) (trying all possible placements with pruning).

Space Complexity: O(n²) for the board and O(n) for recursion stack.

16. What is the Sudoku problem?

The Sudoku problem involves filling a 9×9 grid with digits 1–9 such that each row, column, and 3×3 subgrid contains unique digits, starting from a partially filled grid.

17. How is backtracking used in Sudoku?

Try placing digits 1–9 in empty cells, checking validity. If a digit leads to an invalid state, backtrack and try another digit.

18. Can you give an example of a Sudoku solver in C?

#include <stdio.h>
#include <stdbool.h>

#define N 9

bool isSafe(int grid[N][N], int row, int col, int num) {
    for (int x = 0; x < N; x++) // Check row and column
        if (grid[row][x] == num || grid[x][col] == num) return false;
    int startRow = row - row % 3, startCol = col - col % 3;
    for (int i = 0; i < 3; i++) // Check 3x3 subgrid
        for (int j = 0; j < 3; j++)
            if (grid[i + startRow][j + startCol] == num) return false;
    return true;
}

bool findEmpty(int grid[N][N], int* row, int* col) {
    for (*row = 0; *row < N; (*row)++)
        for (*col = 0; *col < N; (*col)++)
            if (grid[*row][*col] == 0) return true;
    return false;
}

bool solveSudoku(int grid[N][N]) {
    int row, col;
    if (!findEmpty(grid, &row, &col)) return true; // No empty cell
    for (int num = 1; num <= 9; num++) {
        if (isSafe(grid, row, col, num)) {
            grid[row][col] = num; // Place number
            if (solveSudoku(grid)) return true;
            grid[row][col] = 0; // Backtrack
        }
    }
    return false;
}

void printGrid(int grid[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) printf("%d ", grid[i][j]);
        printf("\n");
    }
}

int main() {
    int grid[N][N] = {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };
    if (solveSudoku(grid)) printGrid(grid);
    else printf("No solution exists\n");
    return 0;
}
      

19. What is the time complexity of Sudoku solver?

Time Complexity: O(9^(m)) (m = number of empty cells), but pruning reduces practical runtime.

Space Complexity: O(n²) for the grid and O(n²) for recursion stack.

20. What is the Subsets problem?

The Subsets problem involves generating all possible subsets of a given set of elements (e.g., for {1, 2}, subsets are {}, {1}, {2}, {1, 2}).

21. How is backtracking used in Subsets?

For each element, choose to include or exclude it, recursively generating all combinations and backtracking to try the other option.

22. Can you give an example of Subsets in C?

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

void printSubset(int subset[], int size) {
    printf("{ ");
    for (int i = 0; i < size; i++) printf("%d ", subset[i]);
    printf("}\n");
}

void subsetsUtil(int arr[], int n, int subset[], int index, int subsetSize) {
    printSubset(subset, subsetSize); // Print current subset
    for (int i = index; i < n; i++) {
        subset[subsetSize] = arr[i]; // Include element
        subsetsUtil(arr, n, subset, i + 1, subsetSize + 1);
        // Exclude element by not adding it (backtrack implicitly)
    }
}

void subsets(int arr[], int n) {
    int* subset = (int*)malloc(n * sizeof(int));
    subsetsUtil(arr, n, subset, 0, 0);
    free(subset);
}

int main() {
    int arr[] = {1, 2};
    int n = 2;
    subsets(arr, n); // Output: { }, { 1 }, { 2 }, { 1 2 }
    return 0;
}
      

23. What is the time complexity of Subsets?

Time Complexity: O(2^n) (generates all 2^n subsets).

Space Complexity: O(n) for recursion stack and subset array.

24. What is the Permutations problem?

The Permutations problem involves generating all possible orderings of a given set of elements (e.g., for {1, 2}, permutations are {1, 2}, {2, 1}).

25. How is backtracking used in Permutations?

Choose each element for the current position, swap it, recursively generate permutations for the remaining elements, and backtrack by undoing the swap.

26. Can you give an example of Permutations in C?

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

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

void printPermutation(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

void permute(int arr[], int start, int n) {
    if (start == n) {
        printPermutation(arr, n);
        return;
    }
    for (int i = start; i < n; i++) {
        swap(&arr[start], &arr[i]); // Choose element
        permute(arr, start + 1, n); // Recurse
        swap(&arr[start], &arr[i]); // Backtrack
    }
}

int main() {
    int arr[] = {1, 2, 3};
    int n = 3;
    permute(arr, 0, n); // Output: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 2 1, 3 1 2
    return 0;
}
      

27. What is the time complexity of Permutations?

Time Complexity: O(n!) (generates all n! permutations).

Space Complexity: O(n) for recursion stack.