Code Destine

Problem Statement

You have given a binary tree, write a program to find out its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node of the binary tree to its nearest leaf node.

Example 

In above binary tree, the shortest path from root node to its nearest leaf node is 2.

Breadth First Search

Using the Breadth First Traversal algorithm, we will find out the nearest leaf node from the root node and return its path as a result.

import java.util.LinkedList;
import java.util.Queue;

public class Main {

	public static void main(String[] args) {
		Main main = new Main();

		TreeNode node = new TreeNode(5);
		node.left = new TreeNode(3);
		node.right = new TreeNode(8);		
		node.left.left = new TreeNode(2);
		node.left.right = new TreeNode(4);
		
		int result = main.minDepth(node);
		System.out.println(result);
	}
	
	public int minDepth(TreeNode root) {
        if(root == null) return 0;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        int i = 0, size = 0, count = 0, min = 0;
        while(queue.size() > 0){        
            count++;
            size = queue.size();            
            for(i=0; i<size; i++){                
                root = queue.poll();                
                if(root.left == null && root.right == null){
                    min = count;
                    return min;
                }else {
                    if(root.left != null) queue.add(root.left);
                    if(root.right != null) queue.add(root.right);
                }
            }
        }
        return min;
    }
	
	public static class TreeNode {		
		int val;
		TreeNode left;
		TreeNode right;
		
		TreeNode(int x) {
			val = x;
		}
	}
}

Depth First Search

Using the Depth First Traversal algorithm, we will find out the path of all leaf nodes from the root node and store the minimum path in min variable and return it as a result.

public class Main {

	public static void main(String[] args) {
		Main main = new Main();

		TreeNode node = new TreeNode(5);
		node.left = new TreeNode(3);
		node.right = new TreeNode(8);		
		node.left.left = new TreeNode(2);
		node.left.right = new TreeNode(4);
		
		int result = main.minDepth(node);
		System.out.println(result);
	}
	
	public int minDepth(TreeNode root) {
        if(root == null) return 0;
        return dfs(root, 1, Integer.MAX_VALUE);
    }
    
    public int dfs(TreeNode node, int level, int min){        
        if(node == null){
            return min;            
        }else if(node.left == null && node.right == null){
            if(min > level){
                min = level;
            }
            return min;
        }        
        min = dfs(node.left, level+1, min);
        min = dfs(node.right, level+1, min);
        return min;        
    }
	
	public static class TreeNode {		
		int val;
		TreeNode left;
		TreeNode right;
		
		TreeNode(int x) {
			val = x;
		}
	}
}

Result

2

Similar Post

1. Sum of all Left Leaves
2. Level Order Traversal of Binary Tree
3. Minimum Distance Between BST Nodes

If you liked it, please share your thoughts in a comments section and share it with others too.