educative.io

Solution is wrong, doesn't even return the requested output type

Courses
,
#1

The question clearly asks to output the path with the highest sum, and defines the path as having at least 2 nodes.

The given solution outputs the maximum sum, not the path.

Keeping track of the max path and constructing it in the correct order is a significant part of the challenge of this question, which the solution ignores.

It also ignores negatives, which is wrong. If the whole tree is negative numbers, there’s still a valid path of at least 2 nodes that equates to the maximum sum.

The correct output should be:

Maximum Path Sum: [2,1,3]
Maximum Path Sum: [8,5,3,6,9]
Maximum Path Sum: [-3,-1]

#2

This may work:

def max_sum_recursive(self, root):
        if root is None:
            return 0
        if root.left is None and root.right is None:
            return root.val

        left_sum = 0
        right_sum = 0
        left_sum = self.max_sum_recursive(root.left)
        right_sum = self.max_sum_recursive(root.right)

        node_sum = left_sum + right_sum + root.val
        if node_sum < 0:
            if left_sum == 0:
                node_sum = right_sum + root.val
            elif right_sum == 0:
                node_sum = left_sum + root.val
            else:
                node_sum = max(left_sum, right_sum) + root.val
        self.max_subtree_sum = max(node_sum, self.max_subtree_sum)
        return max(left_sum, right_sum) + root.val

Can anyone suggest test cases where this breaks?

#3

The problem clearly asks to write a function to output the sum of the path with the maximum sum:

Find the path with the maximum sum in a given binary tree. Write a function that returns the maximum sum.

Your second point is valid; we should have clearly mentioned that a path should have at least one node. We’ve updated the problem description.

#4

This is still pretty confusingly worded. It asks for the path between two nodes (which, in the provided examples, includes both the source and destination node) and then right after says it should have at least one node.

To my understanding, a path between two nodes (where all the examples include both the start and end node) should be at least 2 nodes.

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Solution Review: Problem Challenge 2 - Grokking the Coding Interview: Patterns for Coding Questions