Find Minimum Depth of Binary Tree - The Coding Shala

Home >> Interview Questions >> Minimum Depth of a Binary Tree

Find 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:

Given binary tree [3,9,20,null,null,15,7],



    3

   / \

  9  20

      /  \
   15   7

return its minimum depth = 2.

Find Minimum Depth of Binary Tree Java Program

Method 1:
Using recursion.

Java Code: 
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root==null) return 0;
        if(root.left==null) return 1+minDepth(root.right);
        if(root.right==null) return 1+minDepth(root.left);
        return 1+Math.min(minDepth(root.left), minDepth(root.right));
    }
}

Method 2:
Using level order traversal.
We do level-order traversal and increase depth according to the current level when meeting a node in which both children is null then return the depth.

Java Code: 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root==null) return 0;
        int depth = 1;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode curr = queue.poll();
                if(curr.left==null && curr.right==null) return depth;
                if(curr.left!=null) queue.offer(curr.left);
                if(curr.right!=null) queue.offer(curr.right);
            }
            depth++;
        }
        return depth;
    }
}




Other Posts You May Like
Prev<< Height of a Binary Tree                                                                                      NEXT >>#
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala

New Year Chaos Solution - The Coding Shala

Add two numbers in Scala - The Coding Shala