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

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
	// Recursion : bottom-up approach!!!
    // public int minDepth(TreeNode root) {
    // 	if(root ==  null){
    // 		return 0;
    // 	}

    // 	if(root.left == null && root.right == null){
    // 		return 1;
    // 	}

    // 	if(root.left == null){
    // 		return minDepth(root.right) + 1;
    // 	}else if(root.right == null){
    // 		return minDepth(root.left) + 1;
    // 	}

    // 	int left = minDepth(root.left);
    // 	int right = minDepth(root.right);

    // 	return left > right? right + 1 : left + 1;
    // }


	// recursion : top-down approach!!
    public int minDepth(TreeNode root){
    	if(root == null) return 0;
    	
    	int[] res = {Integer.MAX_VALUE};

    	dfs(res, root, 1);

    	return res[0];
    }

    public void dfs(int[] res, TreeNode node, int depth){
    	if(node.left == null && node.right == null){
    		res[0] = Math.min(res[0], depth);
    		return;
    	}

    	depth++;
    	if(depth > res[0]){
    		// back-tracking
    		return;
    	}

    	if(node.left != null){
    		dfs(res, node.left, depth);
    	}

    	if(node.right != null){
    		dfs(res, node.right, depth);
    	}
    }
}
@@ -1489,8 +1489,979 @@
 %0A    %7D%0A%7D
+%0A%0A%0A/**%0A * Definition for binary tree%0A * public class TreeNode %7B%0A *     int val;%0A *     TreeNode left;%0A *     TreeNode right;%0A *     TreeNode(int x) %7B val = x; %7D%0A * %7D%0A */%0Apublic class Solution %7B%0A    public int minDepth(TreeNode root) %7B%0A        if (root == null) %7B%0A            return 0;%0A        %7D%0A        Queue%3CTreeNode%3E queue = new LinkedList%3CTreeNode%3E();%0A        queue.add(root);%0A        int min = 1;%0A        int size = 1;%0A%0A        while (!queue.isEmpty()) %7B%0A            for (int i = 0; i %3C size; i++)%7B%0A                TreeNode node = queue.poll();%0A                if (node.left == null && node.right == null) %7B%0A                    return min;%0A                %7D%0A%0A                if (node.left != null) %7B%0A                    queue.add(node.left);%0A                %7D%0A                if (node.right != null) %7B%0A                    queue.add(node.right);%0A                %7D%0A            %7D%0A            size = queue.size();%0A            min++;%0A        %7D%0A%0A        return min;%0A    %7D%0A%7D

update min depth of binary tree solution using iteration;