Description:
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.
Examples:
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: 5Solution in Python:
To solve the problem of finding the minimum depth of a binary tree in Python, you can use a breadth-first search (BFS) approach. BFS is suitable for this problem because it explores nodes level by level, which means it will find the shortest path to a leaf node efficiently.
Python
from collections import deque
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
# If the root is null, the tree is empty and its minimum depth is 0
if not root:
return 0
# Initialize a queue for BFS. The queue stores tuples of (node, current_depth)
queue = deque([(root, 1)])
while queue:
# Pop the front element from the queue
node, depth = queue.popleft()
# Check if the current node is a leaf node
if not node.left and not node.right:
return depth
# If the current node has a left child, add it to the queue with depth + 1
if node.left:
queue.append((node.left, depth + 1))
# If the current node has a right child, add it to the queue with depth + 1
if node.right:
queue.append((node.right, depth + 1))Detailed Comments:
- TreeNode Class Definition:
- This class defines the structure of a node in the binary tree. Each node has a value (
val), and pointers to its left and right children.
- This class defines the structure of a node in the binary tree. Each node has a value (
- minDepth Method:
- Base Case: If the root is
None, the tree is empty, and the minimum depth is0. - BFS Initialization: A queue is initialized using
collections.deque. This queue will store tuples, where each tuple contains a node and its depth from the root. - BFS Loop:
- The while loop runs as long as there are elements in the queue.
- The front element of the queue is popped, which gives the current node and its depth.
- If the current node is a leaf node (i.e., it has no left and right children), the current depth is returned as the minimum depth.
- If the current node has a left child, this child is added to the queue with a depth incremented by 1.
- Similarly, if the current node has a right child, it is added to the queue with a depth incremented by 1.
- Base Case: If the root is
This approach ensures that the shortest path to a leaf node is found efficiently. The time complexity of this solution is O(n), where n is the number of nodes in the tree, because each node is processed at most once. The space complexity is also O(n) in the worst case, where the queue might hold all nodes at a specific level of the tree.
Solution in Javascript:
JavaScript
/**
* @param {TreeNode} root
* @return {number}
*/
var minDepth = function(root) {
// If the root is null, the tree is empty and its minimum depth is 0
if (root === null) {
return 0;
}
// Initialize a queue for BFS. The queue stores objects with node and depth properties
let queue = [];
queue.push({ node: root, depth: 1 });
while (queue.length > 0) {
// Dequeue the front element from the queue
let { node, depth } = queue.shift();
// Check if the current node is a leaf node
if (node.left === null && node.right === null) {
return depth;
}
// If the current node has a left child, enqueue it with depth + 1
if (node.left !== null) {
queue.push({ node: node.left, depth: depth + 1 });
}
// If the current node has a right child, enqueue it with depth + 1
if (node.right !== null) {
queue.push({ node: node.right, depth: depth + 1 });
}
}
};Solution in Java:
Java
class Solution {
public int minDepth(TreeNode root) {
// If the root is null, the tree is empty and its minimum depth is 0
if (root == null) {
return 0;
}
// Initialize a queue for BFS. The queue stores pairs of (TreeNode, depth)
Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
queue.offer(new Pair<>(root, 1));
while (!queue.isEmpty()) {
// Dequeue the front element from the queue
Pair<TreeNode, Integer> current = queue.poll();
TreeNode node = current.getKey();
int depth = current.getValue();
// Check if the current node is a leaf node
if (node.left == null && node.right == null) {
return depth;
}
// If the current node has a left child, enqueue it with depth + 1
if (node.left != null) {
queue.offer(new Pair<>(node.left, depth + 1));
}
// If the current node has a right child, enqueue it with depth + 1
if (node.right != null) {
queue.offer(new Pair<>(node.right, depth + 1));
}
}
// The tree is guaranteed to be non-empty at this point, so we should never reach here
return 0;
}
}
// Utility class to store pairs of (TreeNode, depth)
class Pair<K, V> {
private K key;
private V value;
public Pair(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
}Solution in C#:
C#
using System.Collections.Generic;
public class Solution {
public int MinDepth(TreeNode root) {
// If the root is null, the tree is empty, and its minimum depth is 0
if (root == null) {
return 0;
}
// Initialize a queue for BFS, which stores pairs of (TreeNode, depth)
Queue<(TreeNode node, int depth)> queue = new Queue<(TreeNode node, int depth)>();
queue.Enqueue((root, 1));
// BFS loop
while (queue.Count > 0) {
// Dequeue the front element from the queue
var (node, depth) = queue.Dequeue();
// Check if the current node is a leaf node
if (node.left == null && node.right == null) {
return depth;
}
// If the current node has a left child, enqueue it with depth + 1
if (node.left != null) {
queue.Enqueue((node.left, depth + 1));
}
// If the current node has a right child, enqueue it with depth + 1
if (node.right != null) {
queue.Enqueue((node.right, depth + 1));
}
}
// This line should never be reached since the input guarantees at least one node
return 0;
}
}