How do I get the correct path that maximize the path sum for a given binary tree?

Question

I'm trying to write some kind of a variant of the solution to Leetcode 124 Binary Tree Maximum Path Sum:

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

By variant, I mean that in addition to giving the maximum path sum, the method also produces the full path.

The definition for a binary tree node is as on Leetcode, with an extra method:

class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

  def to_binary_tree(items):
    """Generate a BT from a given list"""
    n = len(items)
    if n == 0:
      return None

    def inner(index: int = 0):
      """Closure function using recursion bo build tree"""
      if n <= index or items[index] is None:
        return None

      node = TreeNode(items[index])
      node.left = inner(2 * index + 1)
      node.right = inner(2 * index + 2)
      return node

    return inner()

In addition to the constructor, I added the to_binary_tree method which generates a BT from a given list.

Here is the solution part.

class Solution:
  def maxPathSum(self, root: TreeNode) -> int:
    def traversal(root):
      if root is None:
        return 0
      left = max(0, traversal(root.left))
      right = max(0, traversal(root.right))
      layerSum = left + right + root.val
      if(layerSum>self.res):
        self.res = layerSum
        self.path = [left, root.val, right]
      return max(left, right, 0) + root.val

    self.res = float("-inf")
    self.path = []
    traversal(root)
    return self.res, self.path

In addition to giving the maximum path sum, it also returns the corresponding path.

case_1

For example, given list [-10, 9, 20, None, None, 15, 7]

root = TreeNode.to_binary_tree([-10, 9, 20, None, None, 15, 7])
testSolution = Solution()
print(testSolution.maxPathSum(root))

the above code produces

(42, [15, 20, 7])

which is as expected.

case_2

However, given another list [10, -2, 7, 8, -4, None, None],

              10
           /      \
         -2        7
       /   \     
      8     -4

the method maxPathSum returns

(23, [6, 10, 7])

which is close to but not exactly as expected. The expectation is

(23, [8, -2, 10, 7])

How do I get that?

case_3

For list [-15, 5, 6, -8, 1, 3, 9, 2, 6, None, None, None, None, None, 0, None, None, None, None, 4, -1, None, None, 10, None]

corresponding to the follow BT

       -15
       / \
      /   \
     /     \
    5       6
   / \     / \
  -8  1   3   9
 / \           \
2   6           0
               / \
              4  -1
                 /
                10

the method maxPathSum returns

(18, [3, 6, 9])

where neither the sum nor the path is as expected. The expectation is

(27, [3, 6, 9, 0 – 1, 10])

What am I missing?

Answer 1

With this assignment:

self.path = [left, root.val, right]

it is evident that the length of the path is always 3. left and right are sums, so only when those sums happen to come from a single node, will this represent the path you want to get. But if the sum is derived from multiple nodes, you need to know which nodes they were.

To achieve that, you should let traverse also return the path together with the found sum.

Here is the adapted code for traverse:

        def traversal(root):
            if root is None:
                return 0, []
            
            left, left_path = max((0, []), traversal(root.left))
            right, right_path = max((0, []), traversal(root.right))
            layer_sum = left + right + root.val
            if layer_sum > self.res:
                self.res = layer_sum
                self.path = left_path + [root.val] + right_path[::-1]
            if left > right:
                return left + root.val, left_path + [root.val]
            else:
                return right + root.val, right_path + [root.val]

The list format

Your code to build a tree from a list will only produce the same tree as LeetCode would, when it has all its leaves in the bottom two levels of the tree. In other cases, the LeetCode encoding into a list will not include some of the None values your code expects to be there. Take for example this tree:

         1 
          \  
           3
          / \
         2   4

LeetCode would represent that tree as [1, None, 3, 2, 4], not as [1, None, 3, None, None, 2, 4]. In other words, if a node has no child, its None grandchildren -- that would have been children of that None child -- are not taking slots in the list representation.

If you want to support the list input as LeetCode would give it, then use the following method:

def to_binary_tree(items):
    if not items:
        return None

    it = iter(items)
    root = TreeNode(next(it))
    q = [root]
    for node in q:
        val = next(it, None)
        if val is not None:
            node.left = TreeNode(val)
            q.append(node.left)
        val = next(it, None)
        if val is not None:
            node.right = TreeNode(val)
            q.append(node.right)
    return root