Leetcode: 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.

Understand the problem:
The problem asks for finding the minimum depth of a binary tree. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. 

For example, given a binary tree:
      1
     /   \
   2    3
  /  \
4    5
The minimum depth is 2. 


Recursive Solution:
The recursive solution is similar to the path sum problem. We use preorder traversal of the binary tree. Each node accumulate the counter to present the depth of the node. If the node is a leaf, we compare it with the minimum value and update the minimum value. We recursively repeat this process until all nodes have been traversed. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int min = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        
        preOrderTraversal(root, 0);
        
        return min;
    }
    
    private void preOrderTraversal(TreeNode root, int depth) {
        if (root == null) return;
        
        depth++;
        
        // check if the node is leaf
        if (root.left == null && root.right == null && depth < min) {
            min = depth;
        }
            
        preOrderTraversal(root.left, depth);
        preOrderTraversal(root.right, depth);
    }
}

Iterative Solution:
The iterative solution is also very straightforward. The crux is to use two stacks, one stores the nodes, while the other store the depth of each node. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<Integer> depthStack = new Stack<Integer>();
        
        int min = Integer.MAX_VALUE;
        
        nodeStack.push(root);
        depthStack.push(1);
        
        while (!nodeStack.empty()) {
            TreeNode curNode = nodeStack.pop();
            int depth = depthStack.pop();
            
            // if it is a leaf node
            if (curNode.left == null && curNode.right == null && depth < min) {
                min = depth;
            }
            
            if (curNode.right != null) {
                nodeStack.push(curNode.right);
                depthStack.push(depth + 1);
            }
            
            if (curNode.left != null) {
                nodeStack.push(curNode.left);
                depthStack.push(depth + 1);
            }
        }
        
        return min;
    }
}

Summary:
The problem itself is straight-forward. The take-away message is to be careful the common ideas in tree-based problems. This question itself is very similar to the path sum problem. Be familiar with the ideas behind the solution.

Update on 12/16/14:

public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        return minDepthHelper(root);
    }
    
    private int minDepthHelper(TreeNode root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        
        if (root.left == null && root.right == null) {
            return 1;
        }
        
        return Math.min(minDepthHelper(root.left), minDepthHelper(root.right)) + 1; 
    }
}

Update on 4/7/15:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        return minDepthHelper(root);
    }
    
    private int minDepthHelper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftDepth = minDepthHelper(root.left);
        int rightDepth = minDepthHelper(root.right);
        
        if (leftDepth == 0 && rightDepth == 0) {
            return 1;
        }
        
        if (leftDepth == 0) {
            return rightDepth + 1;
        }
        
        if (rightDepth == 0) {
            return leftDepth + 1;
        }
        
        return Math.min(leftDepth, rightDepth) + 1;
    }
}

Update on 9/18/15:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        return minDepthHelper(root);
    }
    
    private int minDepthHelper(TreeNode root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        
        int minLeft = minDepthHelper(root.left);
        int minRight = minDepthHelper(root.right);
        
        if (minLeft == Integer.MAX_VALUE && minRight == Integer.MAX_VALUE) {
            return 1;
        }
        
        return Math.min(minLeft, minRight) + 1;
    }
}