Saturday, 15 October 2016

Find the maximum sum leaf to root path in a Binary Tree


    Given a Binary Tree, find the maximum sum path from a leaf to root. For example, in the following tree, there are three leaf to root paths 8->-2->10, -4->-2->10 and 7->10. The sums of these three paths are 16, 4 and 17 respectively. The maximum of them is 17 and the path for maximum is 7->10.
                      10
                   /      \
                 -2        7
               /   \     
              8     -4    
Solution:
public class PrintMaxSumLeaftoroot {
Node root,leafNode;
public static int max;
public static void main(String[] args) {
PrintMaxSumLeaftoroot tree = new PrintMaxSumLeaftoroot();
        tree.root = new Node(10);
        tree.root.left = new Node(-2);
        tree.root.right = new Node(7);
        tree.root.left.left = new Node(8);
        tree.root.left.right = new Node(-4);
        System.out.println("Following are the nodes "+
                        "on maximum sum path");
        int sum = tree.maxSumPath();
        System.out.println("");
        System.out.println("Sum of nodes is : " + sum);

}
private int maxSumPath() {
if(root==null)
return 0;
callFinfRoot(root,0);
callprintleaf(root,leafNode);
return max;
}
private boolean callprintleaf(Node root2, Node leafNode2) {
if(root2==null)
return false;
if(leafNode2==root2||callprintleaf(root2.left, leafNode2)||callprintleaf(root2.right, leafNode2))
{
System.out.println(root2.data+" ");
return true;
}
return false;
}
private void callFinfRoot(Node root3, int curentsum) {
if(root3==null)
return ;
curentsum+=root3.data;
if(root3.left==null && root3.right==null)
{
if(curentsum>max)
max=curentsum;
leafNode=root3;
}
callFinfRoot(root3.left,curentsum);
callFinfRoot(root3.right, curentsum);
// TODO Auto-generated method stub
}

}

No comments:

Post a Comment