Binary Tree Maximum Path Sum | Dataford Interview Questions

Binary tree maximum path sum.

Asked in the round 4 stage. Implement the function below using the nested-list tree representation.

Contract

root is either null or [value, left, right], where each child has the same representation. Return the largest sum of node values along any path. A path may start and end at any nodes, must follow parent-child connections, and cannot revisit a node.

Constraints

root is non-null
The tree contains at most 10^5 nodes
Each node value is between -10^9 and 10^9
The nested representation of every node is [value, left, right]

Function Signature

def max_path_sum(root):

Your question is Binary Tree Maximum Path Sum. 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