Sponsored
Sponsored
The BFS approach utilizes a queue to perform a level-order traversal of the tree. Each node is dequeued and checked if it is a leaf node. The level count is incremented each time a complete level is processed. The algorithm stops as soon as a leaf node is found, and the current level is returned as the minimum depth.
Time complexity is O(N), where N is the number of nodes, because each node is processed once. Space complexity is O(N) due to the storage requirements of the queue in the worst case (a complete/filled tree).
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5struct TreeNode {
6 int val;
7 struct TreeNode *left;
8 struct TreeNode *right;
9};
10
11struct QueueNode {
12 struct TreeNode *node;
13 int depth;
14 struct QueueNode *next;
15};
16
17void enqueue(struct QueueNode **head, struct TreeNode *node, int depth) {
18 struct QueueNode *newNode = (struct QueueNode *)malloc(sizeof(struct QueueNode));
19 newNode->node = node;
20 newNode->depth = depth;
21 newNode->next = NULL;
22 if (*head == NULL) {
23 *head = newNode;
24 } else {
25 struct QueueNode *temp = *head;
26 while (temp->next) {
27 temp = temp->next;
28 }
29 temp->next = newNode;
30 }
31}
32
33struct QueueNode *dequeue(struct QueueNode **head) {
34 struct QueueNode *temp = *head;
35 if (*head) {
36 *head = (*head)->next;
37 }
38 return temp;
39}
40
41int minDepth(struct TreeNode *root) {
42 if (root == NULL) return 0;
43 struct QueueNode *queue = NULL;
44 enqueue(&queue, root, 1);
45 while (queue != NULL) {
46 struct QueueNode *current = dequeue(&queue);
47 struct TreeNode *node = current->node;
48 int depth = current->depth;
49 if (!node->left && !node->right) {
50 return depth;
51 }
52 if (node->left) enqueue(&queue, node->left, depth + 1);
53 if (node->right) enqueue(&queue, node->right, depth + 1);
54 free(current);
55 }
56 return 0;
57}
58The solution uses a queue for the BFS traversal of the tree. Each node, along with its depth, is enqueued as we traverse. When the first leaf node is encountered (a node without left and right children), the current depth is returned as the minimum depth of the tree.
In the DFS approach, we perform a pre-order traversal of the tree with recursive calls. The minimum depth is calculated by determining the shortest path from the root to any leaf node, where leaf nodes are identified as those without children.
Time complexity is O(N) as each node requires inspection to determine minimum depth. Space complexity can be O(N) in the case of skewed trees due to the recursive stack's depth, but typically O(log N) for balanced trees.
1
Using a recursive DFS, this Java implementation finds the minimum depth by evaluating each subtree's depth. Base cases are used to return instantly when a null node is reached or when a single child is present.