## Maximum Sum Path

### July 22, 2014

Sometimes here at Programming Praxis we publish exercises taken from homework in computer science classes, sometimes we publish exercises that are based on or related to problems at Project Euler, and sometimes we publish exercises that based on common technical interview questions. Today we hit the trifecta: a common interview question that is frequently assigned as homework in computer science classes and that also appears at Project Euler (twice!):

Given a binary tree with integers stored in its nodes, find the maximum sum of any path from root to leaf.

For instance, in the binary tree represented by the triangle shown below, the maximum sum path goes from the 3 at the root, to its child 7, to its grandchild 4, to the leaf node 9, a sum of 23. Since there is no other path with a greater sum, the maximum sum is 23:

` 3`

7 4

2 4 6

8 5 9 3

Your task is to write a program to compute the maximum sum path through a binary tree; also write a variant of the program that returns the path. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

In Python.

In C++: read data from stdin to an stl::vector, check it’s triangular and compute what the row size is. Loop over vector filling in maximum subtree sizes, then we can retrieve the path fairly easily by scanning the data again from the top (no need to keep track of paths as we fill in table):

My Scala solution can be found here.

Haskell solution: