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).
1function TreeNode(val, left=null, right=null) {
2 this.val = (val===undefined ? 0 : val);
3 this.left = (left===undefined ? null : left);
4 this.right = (right===undefined ? null : right);
5}
6
7var minDepth = function(root) {
8 if (root === null) return 0;
9 const queue = [[root, 1]];
10 while (queue.length) {
11 const [node, depth] = queue.shift();
12 if (node.left === null && node.right === null) {
13 return depth;
14 }
15 if (node.left !== null) {
16 queue.push([node.left, depth + 1]);
17 }
18 if (node.right !== null) {
19 queue.push([node.right, depth + 1]);
20 }
21 }
22 return 0;
23};
24This JavaScript solution uses an array to serve the role of a queue, maintaining node-depth pairs for BFS tracking. The breadth-first search method ensures minimal depth capture by returning the depth of the first leaf encountered.
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.
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int minDepth(TreeNode* root) {
if (root == nullptr) return 0;
if (!root->left && !root->right) return 1;
int left = root->left ? minDepth(root->left) : INT_MAX;
int right = root->right ? minDepth(root->right) : INT_MAX;
return 1 + min(left, right);
}
This C++ solution recurses through each node's children until a leaf is reached, at which point it returns the path's length. The algorithm compares the depth of the left and right sub-trees at each node, selecting the lesser depth.