700257. Minimum Depth of a Binary Tree
Minimum Depth of a Binary Tree
Slug: minimum-depth-of-a-binary-tree
Difficulty: Easy
Id: 700257
Topic Tags: Tree, Data Structures
Company Tags: Amazon, Microsoft, Facebook
Summary
The problem is to find the minimum depth of a given binary tree. The minimum depth is defined as the number of edges between the root node and the nearest leaf node.
Detailed Explanation
To solve this problem, we will use a recursive approach. We start by checking if the current node is a leaf node (i.e., it has no children). If it's a leaf node, we return its depth from the root. Otherwise, we recursively call the function on its left and right subtrees, keeping track of the minimum depth found.
Here's a step-by-step breakdown:
- Start with the root node.
- Check if the current node is a leaf node (i.e., it has no children).
- If it's a leaf node, return its depth from the root (which is 1 for the root node and 0 for any other leaf node).
- Otherwise, recursively call the function on its left and right subtrees.
- Compare the minimum depths found in steps 2-4.
- Return the minimum depth.
Time complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
Space complexity: O(H), where H is the height of the tree. We need to keep track of the recursive call stack, which can be as deep as the tree itself.
Here's an ASCII art diagram of a binary tree:
1
/ \
2 3
/ \ / \
4 5 6 7
Optimized Solutions
Java
public int minDepth(Node root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
int left = (root.left != null) ? minDepth(root.left) : Integer.MAX_VALUE;
int right = (root.right != null) ? minDepth(root.right) : Integer.MAX_VALUE;
return Math.min(left, right) + 1;
}