#ctci

PrintPath.java

// we know how to do it if the path must start at the root.
// we can use this to solve this problem. At first glance,
// at each node we should look for sum path start there.
// actually, we could think about print out all the paths that
// ends there instead.
public class PrintPath{
    public void printPath(Node root, int target){
        if(root == null) return;
        int depth = getDepth(root);
        int[] path = new int[depth]; // the path is at most depth.
        printPath(root, target, path, 0);
    }
    
    private void printPath(Node root, int target, int[] path, int level){
        if(root == null) return;
        
        path[level] = root.val;
        
        // find out all the paths that sum up to target and ends at this node
        int sum = 0;
        for(int i = level; i >= 0; i--){
            sum += path[i];
            if(sum == target) print(path, i, level);
        }
        
        // once we are done, we move to its left and right child 
        // to see if there are any paths end there and satisifying the sum
        printPath(root.left, target, path, level + 1);
        printPath(root.right, target, path, level + 1);
        
        // not necessary but it's a good practice. 
        // remove it from the current level so other nodes at this level
        // can use it too.
        path[level] = Integer.MAX_VAL;
    }
    
    private void print(int[] path, int i, int level){
        StringBuilder builder = new StringBuilder();
        while(i <= level) builder.append(path[i++]);
        System.out.println(builder.toString());
    }
    
    private int getDepth(Node root){
        if(root == null) return 0;
        return 1 + Math.max(getDepth(root.left), getDepth(root.right));
    }
}

PrintSumPaths.java

import java.util.ArrayList;
import java.util.Arrays;
public PrintSumPaths{
    public void printAllPath(Node root, int target){
        if(root == null) return;
        
        ArrayList<Integer> values = new ArrayList<Integer>();
        printAllPath(root, values, 0, target);
    }
    
    private void printAllPath(Node root, ArrayList<Integer> values, int currentTotal, int target){
        if(root == null) return;
        
        ArrayList<Integer> updatedValues = new ArrayList<Integer>(values);
        updatedValues.add(root.val);
        if(currentTotal + root.val == target){
            System.out.println(Arrays.toString(updatedValues.toArray()));
        }
        
        printAllPath(root.left, updatedValues, currentTotal + root.val, target);
        printAllPath(root.right, updatedValues, currentTotal + root.val, target);
        // the above code only print out the path starting from root
        // we need to take care of paths starting from other nodes
        printAllPath(root.left, target);
        printAllPath(root.right, target);
    }
}