Root to Leaf Sum in a Binary tree : java Implementation

Hello friends,

Suppose we have a binary tree (not necessary a binary search tree), whose each node represent an Integer. We have a number: SUM. We need to find if there exist a path from Root to any Leaf such that sum of all the nodes equals the SUM. The path should contain full path from Root to a Leaf node.



If we have a binary tree as above and SUM as 26 then the Valid path comprises of (11,5,10) and not 10 and 16 as 10 and 16 is not a complete path from root to leaf but (11,5,10) nodes create a path from root (10) to leaf (11).


Friends, please find below the java code solving this problem. Please note that for representing the binary tree three arrays have been used. :
1. tree[] : This holds the actual values of the tree. This is 0 indexed array.
2. left[] : This  holds index of left child for the current index.
3. right[] : This holds index of right child for the current index.

public class RootToLeafSumInBinaryTree {
    
    // tree holds actual tree node values
    static Integer tree[] = { 10, 16, 5, -3, 6, 11 };
    // holds the index in tree[] corresponding to the left child of the each index
    static Integer left[] = { 1, null, 4, null, null, null };
    // holds the index in tree[] corresponding to the right child of the each index
    static Integer right[] = { 2, 3, 5, null, null, null };
    static Integer result[] = new Integer[tree.length];
    static int resultIndex = 0;

    public static void main(String[] args) {

        Integer sum = 21;
        boolean isSuccess = rootToSum(0, sum);
        for (int i = 0; isSuccess &&  i < resultIndex; i++) {
            System.out.println(result[i]);
        }
    }

    public static boolean rootToSum(int currentIndex, Integer sum) {
        if (left[currentIndex] == null && right[currentIndex] == null) {
            if (sum - tree[currentIndex] == 0) {
                result[resultIndex++] = tree[currentIndex];
                return true;
            } else {
                return false;
            }
        }
        boolean isLeftSuccess = false;
        boolean isRightSuccess = false;
        sum = sum - tree[currentIndex];
        if (left[currentIndex] != null) {
            isLeftSuccess = rootToSum(left[currentIndex], sum);
        }
        if (right[currentIndex] != null) {
            isRightSuccess = rootToSum(right[currentIndex], sum);
        }
        // be careful here we need to see if we get success from Either of Left
        // or Right branch we need to return Success as we have a path where the
        // sum is equal to the provided sum. 
        if (isLeftSuccess || isRightSuccess) {
            result[resultIndex++] = tree[currentIndex];
            return true;
        }
        return false;
    }
}