The Avalanche Algorithm — How To Calculate the Maximum Possible Path in a Binary Tree

Daily Coding Problem

Hello everyone and welcome back with another problem to solve! Today we’ll be dealing with paths, calculating the greatest path in a triangle of numbers starting from the top to the bottom!

Today’s problem comes from the archives of ProjectEuler.net : a super cool website to look at if you are in the mood for some head scratching! There are more than 800 math and coding problems to solve and a vast archive of discussions about them. It is the perfect tool to train your math skills and learn something new. Go check it out and try to solve your challenges too!

Let’s jump to the action!

The problem

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

That is,3+7+4+9=23.

Find the maximum total from top to bottom of the triangle below:

So, to recap a bit: we are given a triangle with numbers. Each number is connected to the two directly below it, forming a path. What we need to do is go from top to bottom and find the maximum possible path value. The sum of its values will be our answer. Also, as the problem states, since the routes are limited, we could try directly to solve it by brute-forcing the solution out from calculating every possible route. As we’ll see just in a moment, that would not be an efficient solution, so we should scrap our heads a bit and find a better solution.

Ready then? Let’s solve it!

Brute forcing the solution

Since the problem advises that the brute force solution is not an efficient one, let’s take a moment to understand why is by looking at some smaller triangles.

To know which path is the most valuable one, we first need to walk over all the possible paths. It would be nice to know how many of them there are in the first place.

So, let’s try to count them:

When there is one row (just one element) we have only one possible path. With two rows there are two possible paths we can take, with three rows there are 4 paths, and so on. Hopefully, you can see what’s happening here: the number of paths grows like 2ⁿ⁻¹: so for instance, with 4 rows we have 2³ = 8. In the problem’s example, the triangles have 15 rows so we count 2¹⁴ possible paths, which are 16384 possible routes, just as the problem states. Given this, to calculate the maximum path by brute force, we would need to calculate the value of all the 16384 routes and then compare them.

Besides the hassle of calculating all those possible paths, for the next similar problem mentioned by the text, which has 100 lines, we are going to have 2⁹⁹ possible paths, meaning roughly a total of 63.382.530.010.000.000.000.000.000.000 possible routes: inconvenient to say the least.

Finally, brute forcing the solution would force us with an algorithm with a time complexity of O(2ⁿ), which is one of the worst results we could hope for.

We need a better method.

The better method

As we saw, the main problem in brute-forcing the solution is that there are way too many possible routes, so too many steps that our algorithm should do to calculate them all. A better solution should involve either fewer routes or fewer steps to calculate them. Since the number of routes depends on the number of elements in the triangle, we have no control over that variable.

So, our only chance is to reduce the number of steps needed for the algorithm to complete. What if we could calculate the maximum path possible of every given triangle … with just one step?

Let’s take a triangle and reason about it.

This is the triangle from the sample given by the problem, for which we already know that the maximum path is 23 (the one in red), or 3 + 7 +4 + 9. This is our first hint: we don’t need intermediate values, we just want the sum of them. This means that we could track the growing value of each path while we go down the triangle and choose the maximum at the end. We can do this by updating intermediate numbers with their actual path value.

As you can see we can apply this process row by row, updating all the values until, in the last row, we obtain the exact solution: 23. This is why I called it the avalanche algorithm: it’s like a snowball rolling down the mountain, which takes the route with the most snow on it and collects it to grow and grow again!

We have a problem though: for certain values inside the triangle we obtain multiple values. Take the middle 4, for example, the one in the third line of the first graph. If we come to the 4 from the 10 we are going to get 14 as a result, but if we come from the 7 we are going to obtain 11.

If we think about it though, 10 and 7 in the second row are already “path values” updated from the previous row, since we’ve done 3+7=10 and 3+4=7 to get them. This means that the path coming from the 10 has already a higher value than the one coming from the 7 and, since we jump on the 4 only from those two values and from 4 we can only go to 5 and 9, we can conclude that the 10 path has an higher value than the 7 one, at least up to that point, and then we will always choose the route coming from the 10. It’s much clearer if you look it like this:

Since we are coming only from 10 and 5, no matter if we are going to 5 or 9, we will always choose the path that already has a value of 10 because it’s higher than the one with a value of 7.

This is our second hint: besides adding the “path value” row by row and number by number, for each number we can choose the highest previous path value and move on. We could also store it, as we’ll do if we want to take the inverse road and print out the final path.

Each element in the triangle will have two values then: its real value and an “updated value” to keep track of the path value up to that point.

OK: we have everything we need to start coding then. Let’s jump to the code!

The code

As with every good coder out there, I learned during the years to innately hate Java. Given this though, I feel like that for this project a solid OOP language was needed, to wrap everything up in a clear form. Go, even if is by far my first choice on almost every project, was not that suitable for this kind of task: its lack of a proper class object would have been a pain to deal with. Python is similar, since it has classes but it becomes messy to work with them after a while, in my opinion at least. So for this problem, we are going for Kotlin, which is sold as Java 2.0: much less boilerplate but the same code potential for its interoperability with Java code. If you never used it, you’ll love it in a moment.

Also, this solution requires building a tree: if you are not familiar with that kind of data structure go check some resources online if you feel this solution is not clear!

Let’s write the code then.

We’ll start writing a Node class, which will be the blueprint for each number inside the triangle. This class must be built with two parameters, value , the actual value of the number, and parents , the list of previous Nodes from which you can jump to this value (always at most 2). Then, inside the class we are going to build two other attributes: updatedValue , which will hold the updated value of the path up to that point, and chosenParent , which will hold the biggest parent of that node. We initially set updatedValue to be equal to value .

After that, we call the init block, which will be the first block executed when the class gets created. In that block, we loop over the two parents (the loop there it’s a bit useless since there always are two parents, but it’s useful to show the idea behind it) and we update the chosenParent with the biggestParent found. Finally, we update updatedValue to be equal to the value of this node plus the updated value of its bigger parent.

We can also write a simple function PrintChain which recursively print out the chain of values that brought us here.

That’s it, really: you have everything you need to solve the problem! Of course, you need a wrapper to collect all the numbers and instantiate all of them as nodes. Here’s the one I wrote, but of course you should build one yourself for your implementation.

Lastly, in the main function, we can wrap everything up and loop over the last line to get our solution.

As always, for the problems given by ProjectEuler.net, I won’t give out the solution: you need to build this by yourself, if you want to know it! ProjectEuler.net is a lovely project: besides presenting math riddles and problems, their main focus is to provide a tool to start learning, thinking, and reasoning about math and algorithms. And I love that: they are so committed that publishing results and guides for their problems is forbidden (this is one of the first 100 problems, so I understand it is permitted). Given this, I don’t feel it would be fair to just give out the solution to copy-paste and get the achievement. You have everything you need to start working on it!

Have a nice coding guys! 😎

Time complexity

It’s not that easy to model the time complexity for an algorithm like this one, but we can try to reason a bit more generally by comparing it with the brute-force solution.

First off, in both cases, we need to parse the numbers in the triangle somehow, either to collect them as nodes or to store them in lists, arrays, or any other method you can think of. Let’s suppose we use the same parsing algorithm for both solutions, the brute force one and the smart one, and let’s suppose this parsing algorithm takes O(n) time, where n is the number of rows in the triangle.

After parsing the elements, in the brute force solution, we must calculate the value of each one of the 2ⁿ⁻¹ possible routes. This, again, leaves us with a time complexity of O(2ⁿ⁻¹).

With the smart solution though we don’t need to do anything else besides parsing the elements correctly. Given that we must pass on each element to parse it as a Node, we’ll do exactly n(n+1)/2 operations. After this we only need to loop over the last row to find the maximum path, requiring O(n) time. Since we are using the same parsing algorithm for both solutions, we can discard the time used for parsing while comparing. Thus, the smarter solution requires only O(n) time while the brute force requires O(2ⁿ⁻¹) time!

Conclusion

That’s it! As always, I hope you liked the article and found it somehow useful. If so, consider leaving a clap or two or sharing it: it would make my day! I also have a Ko-Fi page, if you want to contribute to the redaction of these articles by sharing a coffee with me!

Also, feel free to share your thoughts or questions about this in the comment section: we’re all here to learn!

As always, thanks for reading.

Nicola