class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        return recur(root, 1);
    }

    private int recur(TreeNode root, int depth) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) {
            return depth;
        }
        int ldepth = recur(root.left, depth + 1);
        int rdepth = recur(root.right, depth + 1);

        // either left or right subtree was not a leaf node
        // ignore non leaf node.
        if (ldepth == 0 || rdepth == 0) {
            return Math.max(ldepth, rdepth);
        }
        else {
            return Math.min(ldepth, rdepth);
        }
    }
}