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, 10^5].
-1000 <= Node.val <= 1000
My Solution
In this problem the definition of the minimum depth is the number of nodes from the root to the nearest leaf. A leaf node will have a depth of 1. If the root is null, we just return 0. For all other nodes we just compute the depth of the left and right subtrees and return the minimum of the two. One detail to keep track of is if the node has one null subtree and one non-null subtree, we have to return the depth of the non-null subtree. We can deal with this by initializing our left and right depths to Integer.MAX_VALUE. In this way, we capture the depth of the non-null subtree.
Time complexity would be O(n), where n is the number of nodes in the tree because we traverse all the nodes. Space complexity would be O(1) because we use constant extra space.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int left = Integer.MAX_VALUE;
int right = Integer.MAX_VALUE;
if (root.left != null) {
left = 1 + minDepth(root.left);
}
if (root.right != null) {
right = 1 + minDepth(root.right);
}
return Math.min(left, right);
}
}