An algorithm to print all paths which sum to a given value in a Binary Tree.

Q. 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 value. The path does not need to start or end at the root or a leaf.

Algorithm:

1. Start at the root or any other node (if a node other than root is given).
2. Check all nodes to left and to right recursively, pass the running sum and a string representation of the path downwards.
3. If the sum equals the required value, store that path or print it.
4. Continue down until you hit a null. (We don't quit when running sum matches the required value as there may be negative value nodes down in the path and then a positive one or there maybe zero value nodes down in the tree which IS a possible path).

Source:

import java.util.ArrayList;
import java.util.List;

class Code{
    class Node{ 
        int value;
        Node left, right;
        Node(){}
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
        
        @Override
        public String toString(){
            return Integer.toString(value);
        } 
    }
    
    Node root;
    
    void helper(List<String> list, String s, Node origin, int sum, int value){
        if(origin == null)return;
        sum+=origin.value;
        if(sum==value){String add = s;add+=" "+origin.toString(); list.add(add);} 
        helper(list, s+" "+origin.toString(), origin.left, sum, value);
        helper(list, s+" "+origin.toString(), origin.right, sum ,value);   
    }
    
    void checkPaths(Node root, List<String> list, int value){ 
        if(root == null)return;  
        helper(list,"", root, 0, value);   
        checkPaths(root.left, list, value);
        checkPaths(root.right, list, value); 
    }
    
    public void printPathsForValue(int value){
        List<String> paths = new ArrayList<>();
        checkPaths(root, paths, value);
        System.out.println("Paths: \n"+paths);
    }
    
    public void buildCustomTree(){
        root = new Node(1);
        setChildren(root, 2, 3);
        setChildren(root.left, 1, 2);
        setChildren(root.left.right, null, 3);   
        setChildren(root.right, 1, 3); 
        setChildren(root.right.left, null, 4);
        setChildren(root.right.right, null, 2);
        setChildren(root.right.right.right, 1, null);
        
        root = new Node(1);
        setChildren(root, 2, 3);
        setChildren(root.left, 1, 0);
        setChildren(root.right, 1, 0);
        setChildren(root.left.right, 0, 1);
        setChildren(root.right, 1, 0);
        setChildren(root.left.right, 0, 1);
        setChildren(root.left.right.left, 1, null);
        setChildren(root.right.left, 3, 2);
        setChildren(root.right.left.right, 1, null);
        
        //with -ve values as well
        root = new Node(1);
        setChildren(root, 2, 3);
        setChildren(root.left, 1, 0);
        setChildren(root.left.left, -1, null);
        setChildren(root.left.left.left, 1, 2);
        setChildren(root.left.left.left.right, -1, null); 
        setChildren(root.left.right, 0, 1);
        setChildren(root.left.right.left, null, 1);
        setChildren(root.right, 1, 0);
        setChildren(root.right.left, 3, 2);
        setChildren(root.right.left.right, 1, null);
    }
    
    private void setChildren(Node node, Integer left, Integer right){
        if(left!=null)node.left = new Node(left);
        if(right!=null)node.right = new Node(right);
    }
    
    public static void main(String[] args){
        Code tree = new Code(); 
        tree.buildCustomTree();
        tree.printPathsForValue(4);
    }
}

Output:

Paths:
[ 1 2 1,  1 2 1 -1 1,  1 2 1 -1 2 -1,  1 2 0 0 1,  1 2 0 1,  1 3,  1 3 0,  2 1 -1 2,  3 1,  1 3,  1 2 1]