Java - The maximum sum of a path through a binary tree

Question

I'm trying to write a method for the maximum sum of a path through a binary tree:

public class ConsTree<T> extends BinaryTree<T>
{
    BinaryTree<T> left;
    BinaryTree<T> right;
    T data;

    public int maxSum() 
    {
    }
}

As is shown, each tree contains a tree to its left and to its right, as well as a data of a generic type. I am somewhat confused on how to go about starting this. If someone could provide help as to what the algorithm might look like or put me in the right direction, that would be great. Thanks.

Have you tried anything yet? If so, what did you try? If not, what's preventing you from trying? — nneonneo
– nneonneo, Commented Oct 14, 2012 at 7:25
Also keep in mind that a generic might not be comparable. You should use T extends Comparable to ensure that the type is comparable. — nneonneo
– nneonneo, Commented Oct 14, 2012 at 7:27
I've thought about going through every single path in the tree and then having it keep track of the sums of the largest one, but I'm not really sure how I would do that since the method is recursive. — user1547050
– user1547050, Commented Oct 14, 2012 at 7:28

nneonneo · Accepted Answer · 2012-10-14 07:41:58Z

2

The way to think recursively is to consider the cases. In our case, we look at a single node and can decide what paths it has:

If the node has no children, then the only path is the singleton path (consisting of that node by itself).
If the node has only one child, then all paths go through that child.
Otherwise, the node has two children. Then, all paths go through one of its two children.

In case 1, the maximum must be that node's value. In case 2, the maximum is that node's value, plus the max-path-sum of its child (since that path is extended to a path for the parent through the only child). In case 3, the maximum is the maximum max-path-sum of its two children (since the best path must go through one of the two children, and the parent can see which of the children's best paths is better).

Therefore, the code is really simple. Here, since you return an int, I'm going to assume T = int.

public int maxSum() {
    /* case 1 */
    if(left == null && right == null)
        return data;

    /* case 2 */
    if(right == null)
        return data + left.maxSum();
    else if(left == null)
        return data + right.maxSum();

    /* case 3 */
    return Math.max(data + left.maxSum(), data + right.maxSum());
}

answered Oct 14, 2012 at 7:41

nneonneo

181k37 gold badges331 silver badges412 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

dsfdf Over a year ago

You are assuming that the max sum path must go through the root, but i think it's not necessary. There might be a path that has the max sum which doesn't go through the root.

Bruce Zu · Accepted Answer · 2016-02-18 01:41:38Z

private static int max = Integer.MIN_VALUE;

public static int maxPathSum(TreeNode root) {
    int rd = dfs(root);
    return rd > max ? rd : max;
}

// close paths:
// 1 left leaf
// 2 right leaf
// 3 left + root + right
//
// open paths:
// 4 root
// 5 left + root
// 6 right + root
private static int dfs(TreeNode root) {
    if (root.left == null && root.right == null) {
        return root.val;
    }
    if (root.left == null && root.right != null) {
        int rPathMax = dfs(root.right);
        max = rPathMax > max ? rPathMax : max;
        return Math.max(root.val, rPathMax + root.val);
    }
    if (root.right == null && root.left != null) {
        int lPathMax = dfs(root.left);
        max = lPathMax > max ? lPathMax : max;
        return Math.max(root.val, lPathMax + root.val);
    }
    int lPathMax = dfs(root.left);
    int rPathMax = dfs(root.right);
    int closePathMax = lPathMax + rPathMax + root.val;

    int innerMax = Math.max(closePathMax, Math.max(lPathMax, rPathMax));
    max = innerMax > max ? innerMax : max;
    return Math.max(root.val, Math.max(lPathMax + root.val, rPathMax + root.val));
}

Collectives™ on Stack Overflow

Java - The maximum sum of a path through a binary tree

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related