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
Solutions
🧠 Cpp
/**
* Definition for a binary tree node.
* struct TreeNode
* {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution
{
public:
//O(2^n) solution
int minDepth(TreeNode* root)
{
if(!root)
return 0;
//if both leafs are null, we have the last leaf
else if(!root->left && !root->right)
return 1;
//pre-order traversal
return 1 + std::min(minDepth(root->left), minDepth(root->right),
[](int a , int b)
{
if(!a) return false;
if(!b) return true;
return a < b;
});
}
};
Last updated
Was this helpful?