# 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:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its minimum depth = 2.
# Solution
Approach 1: BFS iteration.
Approach 2: recursive -- but be careful when a node has only 1 child.
# Code (Python)
Approach 1:
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# BFS
if not root:
return 0
level = [root]
depth = 1
while level:
new_level = []
for node in level:
if node.left:
new_level.append(node.left)
if node.right:
new_level.append(node.right)
if not node.left and not node.right:
return depth
if new_level:
level = new_level
depth += 1
return depth
Approach 2:
def minDepth(self, root):
# recursive
# this is bad, because it won't count to the very bottom for nodes that has only 1 child
#if not root:
# return 0
#return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
if not root:
return 0
if not root.left and not root.right:
return 1
if not root.left or not root.right:
return self.minDepth(root.left) + 1 if root.left else self.minDepth(root.right) + 1
return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
# Code (C++)
Approach 1:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == NULL) return 0;
queue<TreeNode*> nodeQueue;
nodeQueue.push(root);
int level = 0;
while (!nodeQueue.empty())
{
level++;
int nodeQueueSize = nodeQueue.size();
for (int i = 0; i < nodeQueueSize; ++i) // BFS with each level separated.
{
TreeNode *node = nodeQueue.front();
nodeQueue.pop();
if (node->left == NULL && node->right == NULL)
return level;
if (node->left) nodeQueue.push(node->left);
if (node->right) nodeQueue.push(node->right);
}
}
return level;
}
};