CODEWITHSUNDEEP
javaalgorithmbinary-tree
IUnknown
IUnknown

Reputation: 9809

Issue while calculating max sum in a binary tree

I am not sure why and how is the maxsum getting reset to 0 during the iteration.
There is some step I am erring in calculating the max sum to the leaf. Help is appreciated.

The code - 

class MaxPathSumBTree{

    class Node{
        Node left=null;
        Node right=null;;
        int val;
        Node(int v){ this.val=v;}
    }

    int maxsum=0;
    int curr_sum=0;
    List<int[]> paths=new ArrayList<int[]>();
    int[] currpath=new int[20];

    public MaxPathSumBTree(){
        .....
        processMaxPath(v,0);
    }

    private void maxSum(Node n,int maxsum,int curr_sum,int rank){

            if(n==null){
                if(curr_sum>maxsum==true){
                System.out.println("current : " + curr_sum + " maxsum : " + maxsum);
                    maxsum=curr_sum;
                    paths.add(0,currpath);
                }
                return;
            }
            currpath[rank]=n.val;
            curr_sum+=n.val;
            rank++;
            maxSum(n.left,maxsum,curr_sum,rank);
            maxSum(n.right,maxsum,curr_sum,rank);
    }
.......
     public static void main(String[] args){
        MaxPathSumBTree msbt=new MaxPathSumBTree();
        System.out.println("Final sum : " + msbt.maxsum  );

    }

}

Output - 

Current node : 20 maxsum : 0
Current node : 8 maxsum : 0
Current node : 12 maxsum : 0
current : 40 maxsum : 40
current : 40 maxsum : 40
Current node : 15 maxsum : 0
current : 43 maxsum : 43
current : 43 maxsum : 43
Current node : 9 maxsum : 0
Current node : 17 maxsum : 0
current : 46 maxsum : 46
current : 46 maxsum : 46
Current node : 13 maxsum : 0
current : 42 maxsum : 42
current : 42 maxsum : 42

Final sum : 0

Upvotes: 0

Views: 71

Answers (1)

mats.nowak
mats.nowak

Reputation: 329

You are modifying local variable (maxsum), not class field (this.maxsum) Use "this.maxsum" instaead of "maxsum"

private void maxSum(Node n,int maxsum,int curr_sum,int rank){

        if(n==null){
          ...
            this.maxsum=curr_sum;
          ...
           }
        }

Upvotes: 2

Related Questions