Recursive calls explanation in Binary Tree Maximum Path Sum

Question

This is the problem:

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example: Given the below binary tree,
   1
  / \
 2   3
Return 6.

The recursive solution for this problem looks like this:

int max = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    helper(root);
    return max;
}

private int helper(TreeNode root) {
    if (root == null) return 0;
    int left = Math.max(helper(root.left), 0);
    int right = Math.max(helper(root.right), 0);
    max = Math.max(max, root.val + left + right);
    return root.val + Math.max(left, right);
}

We call helper for left child and check if left child is greater than zero.

Then we call helper for right child and check if right child is greater then zero.

Then we check current max value with the sum root.val + left + right - this is also clear.

But then, in return statement we just have sum of root value and one of the children. Why do we take only one child here but not two of them if they are both positive?

Selindek · Accepted Answer · 2017-08-25 08:04:46Z

1

The recursive method does NOT return the solution itself, it only returns with the max value of that part. The final solution is computed in the max variable.

If you check the maxPathSum method it returns with the max value not the value returned from the helper method.

It is because it is possible that the solution doesn't touch the root, like here:

       0
     /   \
    1     0
   / \   / \
  2   3 0   0

answered Aug 25, 2017 at 8:04

Selindek

3,4432 gold badges20 silver badges25 bronze badges

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

2 Comments

rset_d Over a year ago

In helper method there is an assignment max = Math.max(max, root.val + left + right); - this is clear. But why do we return root.val + Math.max(left, right);? What is the purpose of summing up root.val, how does this affect the value of max variable?

Selindek Over a year ago

The helper method returns the max - non-complete -path of the given sub-tree. The max variable contains the 'finished' paths - what starts and also ends in the given sub-tree. So when the helper method returns it returns a possible half-path, what can be combined with the other half starting from the other branch and if the combined value of this two half is more than the actual maximum then it will be the new maximum.

Collectives™ on Stack Overflow

Recursive calls explanation in Binary Tree Maximum Path Sum

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related