Maximum Path Sum

#180 · Trees · Expert · 215 XP · about 35 min

A path in a binary tree is a chain of nodes where each node is joined to the next by a parent-child link and no node appears twice. A path can start and end at any node, does not have to pass through the root, and can be a single node. Write max_path_sum(root) that returns the largest possible sum of the values along a path. Values can be negative, so leaving a branch out is sometimes better than including it. The tree has at least one node.

Each node is a Node with a value val and two children, left and right, which are None when missing. The provided build makes a tree from a list of values in level order, where None marks a missing child.

Examples

max_path_sum(build([-5, 4, 12, None, None, 8, 3]))  # returns 23
max_path_sum(build([2, 4, 3]))  # returns 9
max_path_sum(build([-3, -1, -2]))  # returns -1

The drawing shows the first tree, where the best path is 8, 12, 3: it avoids the negative root. In the last tree every value is negative, so the best path is the single node -1.

Constraints

1 to 3,000 nodes; values are integers from -1,000 to 1,000.

# Provided: do not change

from collections import deque

class Node:

def __init__(self, val, left=None, right=None):

self.val = val

self.left = left

self.right = right

def build(values):

"""Build a tree from a level-order list; None marks a missing child."""

if not values or values[0] is None:

return None

root = Node(values[0])

queue = deque([root])

i = 1

while queue and i < len(values):

node = queue.popleft()

if values[i] is not None:

node.left = Node(values[i])

queue.append(node.left)

i += 1

if i < len(values) and values[i] is not None:

node.right = Node(values[i])

queue.append(node.right)

i += 1

return root

def max_path_sum(root):

# Your code here

pass

print(max_path_sum(build([-5, 4, 12, None, None, 8, 3])))

Ready?

Accept the challenge to start writing. A small timer counts the time this page is in view.

Output appears here.