LeetCode //C - 111. Minimum Depth of Binary Tree

111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.
 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

Constraints:

• The number of nodes in the tree is in the range $[0,10^5]$.
• -1000 <= Node.val <= 1000

From: LeetCode
Link: 111. Minimum Depth of Binary Tree

Solution:

Ideas:

• TreeNode and QueueNode Structures: We define a TreeNode structure for the binary tree nodes and a QueueNode structure for the BFS queue.
• newTreeNode and newQueueNode Functions: These functions create new nodes for the tree and the queue.
• BFS Implementation in minDepth: We use a queue to perform BFS. For each node, we check if it’s a leaf. If it is, we return its depth. If not, we enqueue its children with their respective depths.
• Main Function: Demonstrates how to use the minDepth function and free the allocated memory for the binary tree.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct QueueNode {
    struct TreeNode *node;
    int depth;
    struct QueueNode *next;
};

// Function to create a new tree node
struct TreeNode* newTreeNode(int val) {
    struct TreeNode *temp = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    temp->val = val;
    temp->left = temp->right = NULL;
    return temp;
}

// Function to create a new queue node
struct QueueNode* newQueueNode(struct TreeNode *node, int depth) {
    struct QueueNode *temp = (struct QueueNode *)malloc(sizeof(struct QueueNode));
    temp->node = node;
    temp->depth = depth;
    temp->next = NULL;
    return temp;
}

// Function to perform BFS and find the minimum depth
int minDepth(struct TreeNode* root) {
    if (root == NULL) return 0;

    // Initialize the queue
    struct QueueNode *front = newQueueNode(root, 1);
    struct QueueNode *rear = front;

    // Perform BFS
    while (front != NULL) {
        struct TreeNode *currentNode = front->node;
        int currentDepth = front->depth;

        // Check if it's a leaf node
        if (currentNode->left == NULL && currentNode->right == NULL) {
            return currentDepth;
        }

        // Enqueue left child
        if (currentNode->left != NULL) {
            rear->next = newQueueNode(currentNode->left, currentDepth + 1);
            rear = rear->next;
        }

        // Enqueue right child
        if (currentNode->right != NULL) {
            rear->next = newQueueNode(currentNode->right, currentDepth + 1);
            rear = rear->next;
        }

        // Dequeue the front node
        struct QueueNode *temp = front;
        front = front->next;
        free(temp);
    }

    return 0; // This line should never be reached
}

// Function to free the binary tree
void freeTree(struct TreeNode *root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77