Algorithm {Binary Tree Maximum Path Sum}

I’ve just solved one more problem from leetcode and going to share that solution. So, solved problem calls Binary Tree Maximum Path Sum.

Problem description:

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

       1
      / \
     2   3
    / \  / \
  null null null

We will traverse to the left, check if node is null return 0 (the max path equals to 0 ) and go to the right node, again if node is null return 0 and go up to parent. Parent is 2. We should check what is the max path left +parent or right +parent. After that check if this max path biggest that current value (because left or right can be negative).

Good, after that we will have max current path in other words max path for current value. So, after that we should check what is the bigger max current path or full path (full path is left + current + right, because the path can start and end at any node) and if that value biggest that stored set it like a max path. That is all, so, words are good but better code, let’s go …

public int maxPathSum(TreeNode root) {
        Integer max[] = new Integer[1];
        maxPathSum(root, max);
        return max[0];
    }
 
    public int maxPathSum(TreeNode root, Integer[] max) {
        if (root == null) {
            return 0;
        }
        int left = maxPathSum(root.left, max);
        int right = maxPathSum(root.right, max);
        int current = root.val;
 
        // choose biggest path for return
        int maxCurrentPath = max(current, max(left+current, right+current));
 
        if (max[0] == null)
            max[0] = current;
        else {
            // choose max path
            int fullPath = left + current + right;
            max[0] = max(max[0], max(maxCurrentPath, fullPath));
        }
        return maxCurrentPath;
    }

So, that is all, if you have some questions don’t hesitate to ask me 🙂
Cheers !!!