Find paths in a binary search tree summing to a target value

Question

Given a binary search tree and a target value, find all the paths (if there exists more than one) which sum up to the target value. It can be any path in the tree. It doesn't have to be from the root.

For example, in the following binary search tree:

  2
 / \ 
1   3 

when the sum should be 6, the path 1 -> 2 -> 3 should be printed.

Answer 1

Traverse through the tree from the root and do a post-order gathering of all path sums. Use a hashtable to store the possible paths rooted at a node and going down-only. We can construct all paths going through a node from itself and its childrens' paths.

Here is psuedo-code that implements the above, but stores only the sums and not the actual paths. For the paths themselves, you need to store the end node in the hashtable (we know where it starts, and there's only one path between two nodes in a tree).

function findsum(tree, target)
  # Traverse the children
  if tree->left
    findsum(tree.left, target)
  if tree->right
    findsum(tree.right, target)

  # Single node forms a valid path
  tree.sums = {tree.value}

  # Add this node to sums of children
  if tree.left
    for left_sum in tree.left.sums
      tree.sums.add(left_sum + tree.value)
  if tree.right
    for right_sum in tree.right.sums
      tree.sums.add(right_sum + tree.value)

  # Have we formed the sum?
  if target in tree.sums
    we have a path

  # Can we form the sum going through this node and both children?
  if tree.left and tree.right
    for left_sum in tree.left.sums
      if target - left_sum in tree.right.sums
        we have a path

  # We no longer need children sums, free their memory
  if tree.left
    delete tree.left.sums
  if tree.right
    delete tree.right.sums

This doesn't use the fact that the tree is a search tree, so it can be applied to any binary tree.

For large trees, the size of the hashtable will grow out of hand. If there are only positive values, it could be more efficient to use an array indexed by the sum.