Hi, here’s your problem today. This problem was recently asked by Facebook:

You are given the root of a binary tree. Find the path between 2 nodes that maximizes the sum of all the nodes in the path, and return the sum. The path does not necessarily need to go through the root.

class Node: def init(self, val): self.val = val self.left = None self.right = None

def maxPathSum(root):

Fill this in.

(* denotes the max path)

*10

/ \

*2 *10

/ \ \

*20 1 -25

/ \

3 4

root = Node(10) root.left = Node(2) root.right = Node(10) root.left.left = Node(20) root.left.right = Node(1) root.right.right = Node(-25) root.right.right.left = Node(3) root.right.right.right = Node(4) print maxPathSum(root)

42