# Solution by vinay007

• Intuition

This problem is very similar to finding maximum height of a binary tree with a small caveat.

The recursion is as follows:

When the node is leaf node i.e. if left and right children are null, then

``````minDepth(root) = 1
``````

When a node has only one child:

``````minDepth(root) = minDepth(root.left)+1 ... if left child is not null
minDepth(root) = minDepth(root.right)+1 ... if right child is not null
``````

When a node has two children:

``````minDepth(root) = min(minDepth(root.left), minDepth(root.right))+1
``````

Note that we need to find the length of smallest path to a leaf node, so if a subtree is empty we need to avoid using the height of that subtree in the recursion.

Java

Java code is as follows:

``````    public int minDepth(TreeNode root) {
if (root == null)
return 0;

if (root.left == null && root.right == null)
return 1;

return Math.min(
(root.left != null)?minDepth(root.left) : Integer.MAX_VALUE,
(root.right != null)?minDepth(root.right):Integer.MAX_VALUE)+1;
}
``````

Complexity Analysis

• Time complexity : O(n)
• Space complexity : O(1)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.