SumOfRootToLeafBinaryNumbers

class SumOfRootToLeafBinaryNumbers {

    public static final int M = 1000000007;


    public static void main(String[] args) {
        SumOfRootToLeafBinaryNumbers s = new SumOfRootToLeafBinaryNumbers();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(0);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(1);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(1);
        System.out.println(s.sumRootToLeaf(root));

        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(1);
        System.out.println(s.sumRootToLeaf(root1));
    }

    public int sumRootToLeaf(TreeNode root) {
        return sumRootToLeaf(root, "");
    }

    public int sumRootToLeaf(TreeNode root, String s) {
        if (root != null) {
            if (root.left == null && root.right == null) {
                return convertToDecimal(s + root.val);
            }
            int lSum = sumRootToLeaf(root.left, s + root.val);
            int rSum = sumRootToLeaf(root.right, s + root.val);
            return (lSum + rSum) % M;
        }
        return 0;
    }

    private int convertToDecimal(String bin) {
        long sum = 0;
        for (int i = 0; i < bin.length(); i++) {
            int bit = bin.charAt(i) - 48;
            int p = bin.length() - i - 1;
            if (bit == 1) {
                sum = (sum + pow(2, p)) % M;
            }
        }
        return (int) sum;
    }

    public static long pow(int a, int n) {
        if (n > 0) {
            long temp = pow(a, n / 2);
            temp = (temp * temp) % M;
            if ((n & 1) == 1) {
                temp = (temp * a) % M;
            }
            return temp;
        }
        return 1;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}