CODEWITHSUNDEEP
algorithmrecursiontree
rset_d
rset_d

Reputation: 119

Recursive calls explanation in Binary Tree Maximum Path Sum

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?

Upvotes: 1

Views: 550

Answers (1)

Selindek
Selindek

Reputation: 3423

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

Upvotes: 1

Related Questions