Binary Tree Max Path Sum: Faulty Logic

Question

I am trying to solve a problem of finding Binary Tree Max path sum. I will post the problem statement.

Write a function that takes in a Binary Tree and returns its max path sum. A path is a collection of connected nodes in a tree, where no node is connected to more than two other nodes; a path sum is the sum of the values of the nodes in a particular path. Each BinaryTree node has an integer value a left child node, and a right child node. Children nodes can either be BinaryTree nodes themselves or None / null.

I need help trying to solve this problem. I have few thoughts, but I am not close to drafting a solution or logic isn't translating to code directly.

Answers that can possibly be max path sum in the iteration

• root alone
• root alone with a left max path
• root alone with a right max path
• some double path/triangle in the left subtree
• some double path/triangle in the right subtree

so there are two types of situations:

• attachablePath (the type of path where i can add root node and compare if its bigger sum or not)
• unattachablePath (the type of path that is a triangular path with root as one of the children in subtree)

and i think i need to have a function that returns both so that the root node that calls them can decide which is more beneficial to them now we probably compare and figure out both options

    bestAttachable = max of leftattachablePath + root, rightAttachablePath + root
    bestUnattachable = max of leftUnattachable, rightUnattachable, root, leftattachable + root + unattachable.

does that make sense? Please help me think about this the right way. I feel like i am missing some things that could possibly go wrong. or unsure how to translate logic to code effectively.

I tried this

def maxPathSum(tree):
    # Write your code here.
    maxA, maxB = helper(tree)
 #   print(maxA, maxB)
    return max(maxA, maxB)
    pass


def helper(node):
    if node is None:
        return 0, float("-inf")
    left_attachable, left_unattachable = helper(node.left)
    right_attachable, right_unattachable = helper(node.right)

#    print('left is ', left_attachable, ' right is ', right_attachable)
    max_attachable = max( left_attachable+node.value, right_attachable+node.value, node.value)
    print(node.value, left_unattachable, right_unattachable, left_attachable, right_attachable)
    max_unattachable = max(left_unattachable, right_unattachable, left_attachable+node.value+right_attachable, node.value)

    return max_attachable, max_unattachable

but this fails during the cases where right_attachable or left_attachable are the maximum ones. Also, i have set the base case of attachable to be 0 but when tree has all negative nodes, then max is the least of all nodes but not 0 but I can't set -inf to attachable too, because when I attach nodes to it, it should be the magnitude of node values.

Answer 1

(The following is untested.) It seems to me that we need a wrapper method, as you indicated, since the main method returns only one value and we can't distinguish from that if it refers to a path segment not reachable from the current node. Something like:

f(tree):
  max_attachable, max_unattachable = g(tree)

  return max(
    max_attachable,
    max_unattachable
  )

For the helper method, if we're at any one node, couldn't the solution be

if node is null:
  return -Infinity, -Infinity

l_attachable, l_unattachable = g(node.left)
r_attachable, r_unattachable = g(node.right)

max_attachable = max(
  node.value,
  l_attachable + node.value,
  node.value + r_attachable
)

max_unattachable = max(
  l_attachable + node.value + r_attachable,
  l_attachable,
  r_attachable,
  l_unattachable,
  r_unattachable
)

return max_attachable, max_unattachable

?