Sum of the Deepest Nodes
In this article I’ll be going over how to write a Java program to compute the sum of the values stored in the deepest level of a binary tree, given a binary tree that stores integers.
Quick Overview:
A binary tree stores information in nodes, and the structure of the tree is such that each node can have either 0, 1, or 2 child nodes that can be accessed from it. In Java, the Tree class can just be written like this:
Where the left and right nodes are subtrees of the main data structure.
Solution:
There are two methods by which we can search through every node in a binary tree: breadth-first and depth-first. In this solution, we’ll be using a depth-first approach, meaning we go as deep into the tree as possible along every possible path. For reference, a breadth-first search would mean that you traverse horizontally, searching each node at each level before moving on to the next.
To solve this problem, we first compute the height of the tree, or the longest possible path between the root of the tree and a leaf node (any node that has 0 children). The nodes at the deepest level in the tree will all have a depth equal to this height. Once we compute the height, we do a depth first search, checking to see if the level we are currently at is equal to this height. If it is, we know we’re at the deepest level of the tree, and we add the value of any node at this level to the sum.
One trick I’ve used here is storing the sum in an array instead of just as a primitive. The reason I do this is because we need to recursively update this sum; at some points, we may need to add values, but at other points we may not. This cannot be achieved with a regular variable because if instantiated in the recursive method it will just reset to 0 every time the dfs() method is called. So, we use an array (in this case essentially a reference to the variable that we store the sum in) to track the sum throughout the tree.
Thanks for reading!
