How to Find Minimum Depth of Binary Tree in Java

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

Logic to solve the minimum depth of the binary tree

  • First, check whether the root node is null, if null then return 0
  • Use Recursion to calculate the minimum depth of the left subtree and right subtree and store it in left and right respectively.
  • If in case both left subtrees and right subtrees exist, select the minimum among left and right plus 1.
  • Otherwise, return the maximum among left and right plus 1.

Example

Input: root = [3,9,20,null,null,15,7]
Output: 2

Leetcode Method

/**
 * 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;
        int left=minDepth(root.left);
        int right=minDepth(root.right);
        if(root.left!=null && root.right!=null)
            return Math.min(left,right)+1;
        return Math.max(left,right)+1;   
    }
}

Solution With Main Method

Created one separate class called TreeNode.

package LeetCodeDebug;

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;
    }
}

Calling this class in another class

package LeetCodeDebug;

import java.util.*;

public class LeetCodeDebug {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(minDepth(root));
    }
    public static int minDepth(TreeNode root) {
        if(root==null)
            return 0;
        int left=minDepth(root.left);
        int right=minDepth(root.right);
        if(root.left!=null && root.right!=null)
            return Math.min(left,right)+1;
        return Math.max(left,right)+1;
    }

}

Leave a Reply

Your email address will not be published. Required fields are marked *

WhatsApp Icon Join For Job Alerts