Deepest Leaves Sum

by

Given a root node, return the sum of all the leaf node values. A leaf node can be defined as a node where the left and right child nodes are null. Our goal is to find the sum of all leaves.

To start, we need to define our root node. This data structure typically has three properties. A val property which represents the value, and a left and right node to represent the nodes children.

class TreeNode(var key: Int, var left: TreeNode?, var right: TreeNode?)

We can use a Depth-First Traversal to traverse the binary tree, starting with the root node. To do this, we will need to pass a level parameter to our recurssive DFS function. The level parameter is an Int that will increase every time our program traverses to a lower level of child nodes.

Let’s also create a mutable list of sums.

val sums = mutableListOf<Int>()

After our recursive DFS function has completed. We should end up with an array of sums that represent the sums at each level. Each element in the list will be the sum of all node values at each level.

  • sums[0] = 1
  • sums[1] = 5
  • sums[2] = 15
  • sums[3] = 7

I use a main method to construct a binary tree example, then call the depth-first search method. Let’s pass the root node for the tree we created and a 0 value to the DFS algorithm. We pass the 0 value because the root node will always start at level 0.

fun main(args: Array<String>) {
    //Let's construct a binary tree for demo purposes
    val root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left?.left = TreeNode(4)
    root.left?.right = TreeNode(5)
    root.right?.right = TreeNode(6)
    root.left?.left?.left = TreeNode(7)
    //Our tree will look like this
    //         1
    //       /   \
    //      2     3
    //     / \     \
    //    4   5     6
    //   /
    //  7

    //Call our DFS algorithm
    dfs(root,0)

    //The last sum in the array of sums will contain the sum of deepest leafs
    println(sums.last())
}

Next we will create our DFS method to recursively populate our sums mutable list. Each element in the sums list will be the sum of all values at the level. Given our example above, we should wind up with a list like [1,5,14,7], where 7 is the sum of the deepest level of leaves.

First check if the level value is equal to the size of sums list, as we are using the level parameter as an index. If the level is the same as the size of our sums list, then it must be a new level. So add the nodes value to the sums list. Otherwise, we should already have a value for this level in the tree, so add the nodes value to the existing value for the nodes level.

Next, the program uses recursion to do our traversal of the binary tree. Check if the node has a left child, if it does then call the dfs method. Do the same for any right children. This will cause the traversal to first go down the tree from the left most branch until there is no left node. Since we call right after left the same will happen for all right nodes. 

/**
 * Populates sum array with sum for each level
 */
fun dfs(node : TreeNode, level: Int) {
    if(level == sums.size)
        //new level
        sums.add(node.`val`)
    else
        //existing level
        sums[level] += node.`val`

    //recursively call left nodes, until there are no more left nodes
    node?.left?.let {
        dfs(it, level + 1)
    }

    //recursively call right nodes, until there are no more right nodes
    node?.right?.let {
        dfs(it, level + 1)
    }
}

Once DFS recursion completes, we are left with an array that represents the sums for each level. To get the sum of leaves at the deepest level, simply take the last element in sums list as it is the sum of leaves at that level.

This algorithm has a time complexity of O(n) because we must traverse through every element in the tree. It also has a space complexity of O(h), where h is the height of the binary tree.