LeetCode - Path Sum III - TypeScript/JavaScript Solutions

Problem Description

Link To Problem on LeetCode

I was inspired to write up a solution to this problem, because the ones I found either really could have benefited from illustrations, or the included code could have been clearer.

The problem is as follows: you are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes). The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
4  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Solution 1 - Recursive Search

If you haven't already, I recommend solving Path Sum first.

Lets take the example provided above to illustrate a brute force search. Our search should generate all possible paths/subpaths down the tree. We start at the root, 10. We have four routes to explore:

1. Make 10 the beginning of our candidate solution path. Then continue our search down the left subtree.
2. Make 10 the beginning of our candidate solution path. Continue down right.
3. Skip 10. We will use some descendent node in the left subtree as the beginning of our path (e.g. 5).
4. Skip 10. We will use some descendent node in the right subtree as the beginning of our path (e.g. -3).

Exploring these four options at every node will generate every possible subpath. At each point we just need to check if we've reached the target and add a tally to the result we will return.

function pathSum(root: TreeNode | null, sum: number): number {
  if (root == null) return 0

  // The solution is the sum of three choices we can make at each node that result
  // in a path with the target sum.
  return (
    continueSearch(root, 0, sum) + // 1. Include root in our sum and continue searching.
    pathSum(root.left, sum) + // 2. Ignore root and explore left subtree.
    pathSum(root.right, sum) // 3. Ignore root and explore right subtree.
  )
}

function continueSearch(node: TreeNode | null, currentSum: number, targetSum: number): number {
  if (node == null) return 0

  const newSum = currentSum + node.val

  return (
    (newSum === targetSum ? 1 : 0) + // Check if we reached the target, if so, add one to result.
    continueSearch(node.left, newSum, targetSum) + // Continue down left subtree with our updated sum.
    continueSearch(node.right, newSum, targetSum) // Continue down right subtree with our updated sum.
  )
}

Time and Space Complexities

The problem does not state that the binary tree given to us is balanced. In the worst case, a tree can degenerate into a linked list. Think of a tree where nodes can only have left children.

To help us arrive at a time complexity for this problem, we can reduce it to another problem. The problem can be restated as follows: Given a linked list of numbers, find a continuous sub list that has a sum of k. To solve this problem we need to consider all index pairs (i, j), 0<=i<=j<n and the sum of all the nodes starting from index i going to index j, inclusive. This has a well-known time complexity of n + n - 1 + n-2 + ... + 3 + 2 + 1 = O(n^2).

Moving on, the space complexity is O(h), where h is the height of the tree, since we will have up to h-1 calls in the runtime stack when we are visiting a leaf node. Keeping in mind the linked list case, we can also express this as O(n).

Solution 2 - Prefix Sum

We notice that we explore each node multiple times. This is indicative of unnecessary/repeated work, however, what we are repeating isn't obvious (or at least how we can avoid it).

Let's say we are at the node with value 5 (root.left). We will recurse down it's left subtree twice:

1. Restart the search down 5's left subtree (i.e. currentSum = 0).
2. Continue the search down 5's left subtree (i.e. currentSum = 10 + 5 = 15).

Both 1 and 2 will perform the same traversals on 5's left subtree. The only difference is the value of the currentSum parameter passed into continueSeach.

Ontop of this, we will arrive at 5 twice (10 -> 5 and starting a new search from 5), so we will have 2*2=4 traversals of 5's left subtree. This gets worse the further we go down the tree. This is where the O(n^2) runtime comes from.

To speed up our search to O(n), we need to search each subtree only once.

Let's say we are exploring the 1 node and our current running sum is 10 + 5 + 2 + 1 = 18. This image illustrates were we currently are in our search:

When considering all these nodes, we want our algorithm to find the path 5 -> 2 -> 1 (sum 8). One way to make this path is to "subtract" the subpath 10 from our current path of 10 -> 5 -> 2 -> 1.

How can we know that there exists a subpath that has a sum of 10 when we arrive at 1 in our search? Everytime we explore a node, we can save our current running sum into a set that can be examined when we arrive at a node. When we arrive at 1, this set will be {10, 15, 18} and the sum we've accumlated from our path from the root to here will be 10 + 5 + 2 + 1 = 18. We notice that we are 10 over our goal of 8. However, our set tells us that a subpath starting from the root has a sum of 10 (in this case, just the node 10 itself). This tells us that if we remove that part from our path, we will have a path that has a sum of 18 - 10 = 8. We have a solution.

We call this earlier portion of our running sum a prefix sum. It is a subpath that is a prefix (node 10) of our current path (10 -> 5 -> 2 -> 1). If we remove or "subtract" this prefix, we have a solution (5 -> 2 -> 1).

This is how we solve the problem with only one traversal. One thing to note is that we need to backtrack our prefix sum set as the callstack unwinds by removing the current sum at this node from it. Also, instead of a set storing our prefix sums, we map the value of the prefix sum to how many times it has occurred. We need this in case multiple prefixes can make the same sum.

let pathSumCount = 0

function pathSum(root: TreeNode | null, sum: number): number {
  pathSumCount = 0 // Reset tally for this call.
  getSums(root, 0, sum, new Map())
  return pathSumCount
}

function getSums(root: TreeNode | null, currSum: number, sum: number, frequencyBySum: Map<number, number>) {
  if (root == null) return

  currSum += root.val
  // If target is reached, add tally to result.
  pathSumCount = currSum === sum ? pathSumCount + 1 : pathSumCount
  // If a prefix(es) of the current path can produce currSum - sum, we can
  // "subtract" that prefix(es) from the current one to get the target sum.
  pathSumCount += getOrDefault(frequencyBySum, currSum - sum, 0)

  // Add this path we have as we go down.
  frequencyBySum.set(currSum, getOrDefault(frequencyBySum, currSum, 0) + 1)

  getSums(root.left, currSum, sum, frequencyBySum)
  getSums(root.right, currSum, sum, frequencyBySum)

  // Once we go back up, need to remove the frequency we added.
  frequencyBySum.set(currSum, frequencyBySum.get(currSum) - 1)
}

// Convenience function that accesses a key in a map, returning a provided
// default if the key is not found in the map.
function getOrDefault<K, V>(map: Map<K, V>, key: K, def: V) {
  if (map.has(key)) return map.get(key)
  return def
}

Runtime and Space Complexities

This brings our runtime complexity down to O(n), where n is the number of elements in the tree. This approach does require more memory, but the complexity is still O(n). We have up O(n) calls on the runtime stack (from recursive calls) and O(n) sums stored in our frequencyBySum map.