Leetcode: Minimum Depth of a Binary Tree

 

This question is asked at Amazon, Facebook, and Adobe. 

Given a binary tree, find its minimum depth, where a leaf is a node with no children. 

Example 1:

[3, 9, 20, null, null, 15, 7]. the output is 2 since 9 is the shallowest level. 

There is a Breadth-First-Search way of doing this and then there is a depth-first search way of doing this. the depth-first search would be if both = 0 we return Math.min(left, right) + 1 or left + right + 1. So we traverse through the bottom, we see if there is a minimum found if there is already we return that, else we return the minimum of the left + right + 1. If the left == null return the minDepth of the right root + 1. If root right = 1 return the minimum depth of root.left + 1. The reason being is that we need to go to a leaf node. 

public static int minDepth(TreeNode root) {

    if(root == null) return 0;

    //go to end of the tree leaf

    if(root.left == null) return minDepth(root.right) + 1;

    if(root.right == null) return minDepth(root.left) + 1;

    //return the minimum of both these depths recursively.

    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;

}

and here's the BFS solution: 

public int minDepth2(TreeNode root) {

    if(root == null) return 0; 

    Queue<TreeNode> queue = new LinkedList<>();

    queue.offer(root);

    int level = 1;

    //while the queue isn't empty  

    while(!queue.isEmpty()) {

        int size = queue.size(); 

        for(int i = 0; i < size; i++) {

            //"poll" the front of the queue. 

            TreeNode curNode = queue.poll();

            //return level if the nodes are null, earliest case

            if(curNode.left == null && curNode.right == null) {

                return level;

            }

            //if the left doesn't equal node, offer the put left node in back of queue

            if(curNode.left != null) {

                queue.offer(curNode.left);

            }

            //put right node in back of the queue

            if(curNode.right != null) {

                queue.offer(curNode.right);

            }

        }

        //increment the level variable and return the level of the nodes. 

        level++;

    }

    return level; 

}