Solution by vinay007

  • 0


    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 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.