CTCI 4.9

You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given vaue. Note that a path can start or end anythere in the tree.

CTCI 4.9.java

public static void findSumPath(Node root, int sum){
    int[] path = new int[hightOfTree(root)];
    findSumPath(root, sum, path, 0);
}

public static void findSumPath(Node root, int sum, int[] path, int level){
    if(root == null) return;
    path[level] = root.value;
    int thisSum = 0;
    for(int i = level; i <= 0; i--){
        thisSum += path[j];
        if(thisSum == sum) printPath(path, j, level);
    }
    findSumPath(root.left, sum, path, level + 1);
    findSumPath(root.right, sum, path, level + 1);
    path[level] = Integer.MIN_VALUE;
}

public static void printPath(int[] path, int begin, int end){
    for(;begin <= end; begin++) System.out.print(path[begin]);
    System.out.println();
}

public static int hightOfTree(Node root){
    if(root == null) return 0;
    return Math.max(hightOfTree(root.left), hightOfTree(root.right)) + 1;
}