Thursday, December 11, 2014

Binary Tree Maximum Path Sum

Typical divide and conquer problem.
It is possible that a single path of left subtree or right subtree has a larger sum, or it is possible that a path from left subtree -> root -> right subtree has a larger sum. The problem doesn't specify the value of the nodes, so it's possible that some nodes contain negative values. Thus, we need to track the both the maximum path and single path for each subtree.

SinglePath tracks the maximum sum that can be passed to the parent node for another path that leads to a larger sum. If the singlePath results in negative number, we assume there is no path from this node that can lead to a larger sum (reset to zero).
MaximumPath tracks the maximum sum of current tree / subtree. It is the larger value between left subtree and right subtree, if the root is negative, or the sum of a single path from left to right plus root.

Update:2016-09-27

Maximum length is left max + root value + right max.
Return value is the maximum path from leaf to current path.
If left/right path value is less than 0, reset the path to 0 because adding the path will reduce the value.

    public int maxPathSum(TreeNode root) {
        Queue rst = new LinkedList<>();
        rst.add(Integer.MIN_VALUE);
        getPathSum(root, rst);
        return rst.poll();
    }
    
    private int getPathSum(TreeNode root, Queue rst) {
        if (root == null) {
            return 0;
        }
        int left = getPathSum(root.left, rst);
        int right = getPathSum(root.right, rst);
        int curr = root.val + (left > 0 ? left : 0) + (right > 0 ? right : 0);
        if (curr > rst.peek()){
            rst.poll();
            rst.add(curr);
        }
        return root.val + Math.max(left, Math.max(right, 0));
    }




Update: 2015 - 02 - 27

singlePath = max(singlePath, 0). This operation already eliminates the negative possibility of a path.
     3
  /     \
7      -1
singlePath = max(-1, 0) = 0
maxPath = max(7, 7 + 3 + 0) = 10

Update: 2015 - 01 - 25
The maximum path sum is always the sum from left to right if all elements are positive and one of the branches if the other is negative. 

// Comment
public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
public class MaxPath 
{
 public int maxPathSum(TreeNode root) {
        ResultType rst = Helper(root);
        return rst.maxPath;
    }
    
        private class ResultType
        {
            int singlePath;
            int maxPath;
            public ResultType(int singlePath, int maxPath)
            {
                this.singlePath = singlePath;
                this.maxPath = maxPath;
            }
        }
   
        private ResultType Helper(TreeNode root)
        {
            if (root == null)
                return new ResultType (0, Integer.MIN_VALUE);
            
            //divide
            //traverse the left tree
            ResultType left = Helper(root.left);
            //traverse the right tree
            ResultType right = Helper(root.right);
            
            //Conquer
            //Choose the maximum single path between left subtree and right subtree 
            int singlepath = Math.max(left.singlePath, right.singlePath) + root.val;
            //in case node values are negative, keep the minimum number of nodes as possible 
            singlepath = Math.max(0, singlepath);
            //choose the larger between left and right
            int maxpath = Math.max(left.maxPath, right.maxPath);
            //if a path from left to right in the subtree has larger sum than a single subtree path
            maxpath = Math.max(maxpath, left.singlePath + root.val + right.singlePath);
            
            return new ResultType(singlepath, maxpath);
        }   
} 

1 comment:

  1. The development of artificial intelligence (AI) has propelled more programming architects, information scientists, and different experts to investigate the plausibility of a vocation in machine learning. Notwithstanding, a few newcomers will in general spotlight a lot on hypothesis and insufficient on commonsense application. IEEE final year projects on machine learning In case you will succeed, you have to begin building machine learning projects in the near future.

    Projects assist you with improving your applied ML skills rapidly while allowing you to investigate an intriguing point. Furthermore, you can include projects into your portfolio, making it simpler to get a vocation, discover cool profession openings, and Final Year Project Centers in Chennai even arrange a more significant compensation.


    Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account.

    ReplyDelete