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).
1import java.util.LinkedList;
2import java.util.Queue;
3
4class TreeNode {
5 int val;
6 TreeNode left, right;
7 TreeNode (int x) {
8 val = x;
9 left = right = null;
10 }
11}
12
13public class Solution {
14 public int minDepth(TreeNode root) {
15 if (root == null) return 0;
16 Queue<TreeNode> queue = new LinkedList<>();
17 queue.add(root);
18 int depth = 1;
19
20 while (!queue.isEmpty()) {
21 int size = queue.size();
22 for (int i = 0; i < size; i++) {
23 TreeNode node = queue.poll();
24 if (node.left == null && node.right == null) return depth;
25 if (node.left != null) queue.add(node.left);
26 if (node.right != null) queue.add(node.right);
27 }
28 depth++;
29 }
30 return 0;
31 }
32}
33This Java solution utilizes a Queue to implement a BFS on the tree. Nodes are processed level by level, and the depth is updated for each level processed. The algorithm returns the depth when a leaf node is encountered, as this indicates 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 public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public int MinDepth(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
int left = root.left != null ? MinDepth(root.left) : int.MaxValue;
int right = root.right != null ? MinDepth(root.right) : int.MaxValue;
return 1 + Math.Min(left, right);
}
}
Implementing a purely recursive DFS, this C# solution evaluates the tree depth based on leaf node proximity, using conditional checks for leaf discovery and distressingly large base values for empty children.