Root of a tree

Go back

Given a root like structure like this:

   9
  2 3
 8 2 9
4 7 8 5

You can only go from top to bottom, and only once left or right per row. From top to bottom, find the maximum total of these numbers.

The solution for this 4 row deep tree is:

9 + 3 + 9 + 8 = 29.

You will find that by trying every possible route to solve the problem could result in 2^49 variations in a 50 row deep root. If you can check 10^5 results in one second, that would take 178 years to check them all. However, it works for the example above and a few more rows too, but that’s not the solution I’m looking for.

There is an efficient algorithm to solve this, I’m looking for a few seconds of a runtime. Let’s say everything from 2 to 15 seconds will be accepted. I can consider the brute force solution as a 50% success. Using a time machine or Google is not allowed. (although I can’t find the solution in Google)

The structure in the text file is provided without leading spaces:

 4
 4 7
 7 3 4
 9 2 0 4
 8 5 9 9 3

… and so on.

Download the text file: Tree.txt

lets create something great

Get in touch and send some basic info for a quick quote.

Start Your Project

cohesion Events

Invite only eCommerce events in in Leeds, Manchester, Liverpool London, Glasgow

Register for an invite