Algorithm

Problem Nmae: 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, 105]`.
• `-1000 <= Node.val <= 1000`

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

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

struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};

int minDepth(struct TreeNode *root) {
if (root == NULL)
return 0;

int l = minDepth(root->left);
int r = minDepth(root->right);

if (l == 0 && r == 0) { /* leaf */
return 1;
}
else if (l && r == 0) { /* no right child */
return l + 1;
}
else if (r && l == 0) { /* no left child */
return r + 1;
}
else {
return l  <  r ? (l + 1) : (r + 1);
}
}

void printTreePreOrder(struct TreeNode *p) {
if (p != NULL) {
printf("%d", p->val);
printTreePreOrder(p->left);
printTreePreOrder(p->right);
}
else printf("#");
}

int main() {
struct TreeNode *t = (struct TreeNode *)calloc(4, sizeof(struct TreeNode));
struct TreeNode *p = t;
p->val = 1;
p->right = ++t;
t->val = 2;
t->right = NULL;
p->right->left = ++t;
t->val = 3;
t->left = NULL;
p->right->left->right = ++t;
t->val = 4;
t->left = t->right = NULL;
printTreePreOrder(p); printf("\n");

/* should be 4 */
printf("%d\n", minDepth(p));

return 0;
}
``````
Copy The Code &

Input

cmd
root = [3,9,20,null,null,15,7]

Output

cmd
2

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int minDepth(TreeNode* root) {
if(!root) return 0;
int l = minDepth(root->left);
int r = minDepth(root->right);
return root->left && root->right ? min(l, r) + 1 : l + r + 1;
}
};
``````
Copy The Code &

Input

cmd
root = [3,9,20,null,null,15,7]

Output

cmd
2

#3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int steps = 1;
Queue < TreeNode> queue = new LinkedList<>();
while (!queue.isEmpty()) {
int size = queue.size();
// Level iteration
while (size-- > 0) {
TreeNode removed = queue.remove();
// Leaf reached
if (removed.left == null && removed.right == null) {
return steps;
}
if (removed.left != null) {
}
if (removed.right != null) {
}
}
steps++;
}
return steps;
}
}
``````
Copy The Code &

Input

cmd
root = [2,null,3,null,4,null,5,null,6]

Output

cmd
5

#4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const minDepth = function(root) {
if(root == null) return 0
if(root.left === null && root.right === null) return 1
const res = {
min:Number.MAX_VALUE
}
dfs(root, res, 1)
return res.min
};

function dfs(node, res, cur) {
if(node == null) return
if(node !== null && node.left === null && node.right === null) {
if(cur < res.min) {
res.min = cur
}
return
}
dfs(node.left, res, cur + 1)
dfs(node.right, res, cur + 1>

}
``````
Copy The Code &

Input

cmd
root = [2,null,3,null,4,null,5,null,6]

Output

cmd
5

#5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
return self.compute(root)
def compute(self, node):
if not node: return 0
left_d=self.compute(node.left)
right_d=self.compute(node.right)
if node.left and node.right: return min(left_d,right_d)+1
else: return max(left_d,right_d)+1
``````
Copy The Code &

Input

cmd
root = [3,9,20,null,null,15,7]

Output

cmd
2

#6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _111_MinimumDepthOfBinaryTree
{
public int MinDepth(TreeNode root)
{
if (root == null) return 0;
if (root.left == null) return MinDepth(root.right) + 1;
if (root.right == null) return MinDepth(root.left) + 1;
return Math.Min(MinDepth(root.left), MinDepth(root.right)) + 1;
}
}
}
``````
Copy The Code &

Input

cmd
root = [3,9,20,null,null,15,7]

Output

cmd
2