Solution by vinay007


  • 0
    V

    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)


Log in to reply
 

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