Thursday, January 1, 2015

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]

1 comment:

  1. package Tree;
    import java.util.*;
    public class Paths {
    Node root;

    public static void Listing(List l,Node root,String S,int N,int c){


    if(root==null){System.out.print(0);}
    S=S+Integer.toString(root.getContent());
    c=c+root.getContent();
    if(root.getleft()==null && root.getRight()==null){l.add(S);if(c==N){System.out.println(S);};};
    if(root.getleft()!=null){Listing(l,root.getleft(),S,N,c);}
    if(root.getRight()!=null){Listing(l,root.getRight(),S,N,c);}

    }




    public static void main(String args[]){



    Node d=new Node();
    Node a=new Node();
    Node b=new Node();
    Node c=new Node();
    Node f=new Node();
    Node e=new Node();
    Node g=new Node();
    d.setcontent(9);
    d.setleft(b);
    d.setRight(f);

    b.setcontent(5);
    b.setleft(a);
    b.setRight(c);

    f.setcontent(12);
    f.setleft(e);
    f.setRight(g);

    a.setcontent(2);
    c.setcontent(7);
    e.setcontent(10);
    g.setcontent(15);

    LinkedList R=new LinkedList();
    String S="";
    Listing(R,d,S,31,0);



    }



    }


    ReplyDelete