Maximum Path Sum in Binary Tree | Dataford Interview Questions

Maximum Path Sum in Binary Tree (LeetCode 1249 / LeetCode 124)

Asked in the Loop (Code 1 or Code 2) stage. Reported as one of the coding problems asked during the loop.

Implement max_path_sum(root). The input is a non-empty binary tree represented as nested arrays [value, left, right], where a missing child is null. Return the maximum sum of any non-empty path. A path follows parent-child edges, may start and end at any nodes, and cannot revisit a node.

Function signature: def max_path_sum(root):

Output

Return one integer.

Constraints

1 <= number of nodes <= 3 * 10^4
-10^4 <= node value <= 10^4
root is non-empty
Each node is represented as [value, left, right]
A path follows edges and cannot revisit a node

Function Signature

def max_path_sum(root):

Your question is Maximum Path Sum in Binary Tree. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem