Given a binary tree, find the minimum depth of the tree. The minimum depth is defined as the minimum distance from the root node to the nearest leaf node. A leaf node is a node with no children.
Table of Contents
Sample Input:
Tree:
3
/ \
9 20
/ \
15 7
Expected Output:
2
In this example, the minimum depth of the binary tree is 2 because the path from the root node (3) to the nearest leaf node (9) has a length of 2.
Time and Space Complexity:
The time complexity of the algorithm is O(n), where ‘n’ is the number of nodes in the binary tree. We need to visit each node once to calculate the minimum depth. The space complexity is O(h), where ‘h’ is the height of the binary tree. In the worst case, the recursion stack can grow to the height of the tree.
C++ solution:
#include <iostream>
#include <algorithm>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int minDepth(TreeNode* root) {
// Base case: if the root is null, the minimum depth is 0
if (root == nullptr) {
return 0;
}
// Case 1: If the current node is a leaf node, return 1
if (root->left == nullptr && root->right == nullptr) {
return 1;
}
// Initialize the minimum depth to a large value
int minDepth = INT_MAX;
// Case 2: If the left subtree is not empty, find the minimum depth in the left subtree
if (root->left) {
minDepth = std::min(minDepth, minDepth(root->left));
}
// Case 3: If the right subtree is not empty, find the minimum depth in the right subtree
if (root->right) {
minDepth = std::min(minDepth, minDepth(root->right));
}
// Return the minimum depth of the current node plus 1 (to account for the current level)
return minDepth + 1;
}
int main() {
// Construct the binary tree for the sample input
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
// Find the minimum depth of the binary tree
int minimumDepth = minDepth(root);
std::cout << "The minimum depth of the binary tree is: " << minimumDepth << std::endl;
return 0;
}
The minDepth function recursively calculates the minimum depth of the binary tree. It handles three cases:
- If the current node is a leaf node (has no children), the minimum depth is 1.
- If the left subtree is not empty, it calculates the minimum depth in the left subtree.
- If the right subtree is not empty, it calculates the minimum depth in the right subtree.
The minimum depth of the current node is the minimum of the depths of its left and right subtrees, plus 1 (to account for the current level).
In the given example, the function will correctly find the minimum depth of the binary tree as 2, and the output will be 2.