Mukhtar Bahadory

Sum of Left Leaves - Recursion



Conceptual Overview

We simply have to add the sum of all nodes that are leaves and also left trees.

A leaf is a node without any children.

This is a really simple problem if you utilize a helper function, but the solution we're going to conceptualize captures the closures and returns a final answer.

The key to doing so lies in how you unwind the recursion on each tree. If you're a left tree and have no children, you will return your value. For the right tree, we will simply unwind when it reaches the null pointer but it's important to note we must return 0 as the right leaves should not contribute anything to the solution.

We determine if a tree is a left tree by the parent providing that context. The root node is initialized as not being a left tree, but it will notify its children if they're a left tree.

For the aforementioned techniques appplied on the left and right trees, the parent will combine the return values and return them to the grandparent. The grandparent will then combine that with the sum attained from its right child which might possibly have left leaves of its own.

This process will continue until we have our final answer.

Space and Time Complexity

Space: O(n)
It's possible that tree is a singular deep branch.

Time: O(n)
We recurse on every single node in the tree in an attempt to find the left leaves.


var sumOfLeftLeaves = function(root, left = false) {
  if (!root) return 0

  if (!root.left && !root.right && left) {
    return root.val

  return sumOfLeftLeaves(root.left, true) + sumOfLeftLeaves(root.right)