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.
Programming Praxis 
In Python.
import StringIO DATA = """75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23""" def bottom_up(data): while len(data) > 1: bottom = data.pop() data[-1][:] = [t + max(bottom[i:i+2]) for i, t in enumerate(data[-1])] return data[0][0] def bottom_up_path(data): data[-1][:] = [(t, [t]) for t in data[-1]] while len(data) > 1: bottom = data.pop() for i, t in enumerate(data[-1]): m = max(bottom[i:i+2]) data[-1][i] = (t + m[0], [t] + m[1]) return data[0][0] data = [[int(x) for x in line.split()] for line in StringIO.StringIO(DATA)] print bottom_up_path(data) # (1074, [75, 64, 82, 87, 82, 75, 73, 28, 83, 32, 91, 78, 58, 73, 93])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):
#include <iostream> #include <vector> #include <math.h> #include <assert.h> using namespace std; // 2A = N(N+1) => N^2+N-2A = 0 // a = 1, b = 1, c = -2A // N = (sqrt(1+8A)-1)/2 int main() { vector<int> a; { int n; while(cin >> n) { a.push_back(n); } } int A = a.size();; int N = (sqrt(1+8*A)-1)/2; // IEEE754 sqrt needed! assert(A == N*(N+1)/2); // Check the input is sane { int q = A-N-1; // The table position we are filling in. for (int n = N-1; n > 0; n--) { // The row widths for (int i = n; i > 0; i--,q--) { // Go across the row a[q] += max(a[q+n],a[q+n+1]); } } } { int p = 0; // current index in path for (int n = 1; n < N; n++) { int t = a[p]; // current value p += n+(a[p+n+1] > a[p+n]); cout << t-a[p] << " "; } cout << a[p] << "\n"; } }My Scala solution can be found here.
Haskell solution: