111. Minimum Depth of Binary Tree (BFS + DFS) 20.3.16 Easy

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.

            
Solution no.1: ------------------------------------------------------------------ BFS
------------------------- Time complexity : O(n). Because we traverse the entire input tree once, the total run time is O(n), 
------------------------- where n is the total number of nodes in the tree.
------------------------- Space complexity : O(n)
------------------------- BFS will have to store at least an entire level of the tree in the queue (sample queue implementation). 
------------------------- With a perfect fully balanced binary tree, this would be (n/2 + 1) nodes (the very last level)
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        queue = []
        queue = [(root,  1)]
        while queue:
            currnode, currlevel = queue.pop(0)
            if not currnode.left and not currnode.right:
                return currlevel
            if currnode.left:
                queue.append((currnode.left, currlevel + 1))
            if currnode.right:
                queue.append((currnode.right, currlevel + 1))
                
Solution no.2: -------------------------------------------- DFS
--------------------------------------- O(n) T, O(n) S (maximun depth of the recursion is n if the binary tree is linear)
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
class Solution(object):
    def bfs(self, root):
        if not root:
            return 0
        if None in [root.left, root.right]:
            return max(self.bfs(root.left), self.bfs(root.right)) + 1
            '''
            why max() here?
            because the question requires that it must be counted from the leaf
            for example, 
                  1
                 /
                2
            if we do not add this max(), it will return 1 which counted from 1 but 1 is not a leaf
            so, we need to add this max() for the situations where one of children of this node is None,
            we need to calculate the part which follows the tree to the leaf, so, we use max() to take this part out,
            max(what we want, 0) = what we want
            '''
        else:
            return min(self.bfs(root.left), self.bfs(root.right)) + 1
            '''
            as for both the childrens are not None,
            we keep the principle to find the "minimum" depth
            '''

Java Version for DFS:
/**
 * 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 && root.right == null) {
            return 1;
        }
        if (root.left == null || root.right == null) {
            return Math.max(minDepth(root.left), minDepth(root.right)) + 1;
        }
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}


Java Version for BFS:
/**
 * 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;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int level = 0;
        boolean findNearestLeaf = false;
        while (q.size() != 0 && !findNearestLeaf) {
            int currSize = q.size();
            for (int i = 0; i < currSize; i ++) {
                TreeNode popNode = q.poll();
                if (popNode.left == null && popNode.right == null) {
                    findNearestLeaf = true;
                    break;
                }
                if (popNode.left != null) {
                    q.offer(popNode.left);
                }
                if (popNode.right != null) {
                    q.offer(popNode.right);
                }
            }
            level ++;
        }
        return level;
    }
}