You can, of course, generate all possible paths, adding up gradually when you go. The fact that the tree is a BST can save you time by limiting certain amounts, although I'm not sure if this will give an asymptotic increase in speed. The problem is that the amount formed using the left child of a given node will not necessarily be less than the amount formed using the correct child, since the path for the first sum can contain many more nodes. The following algorithm will work for all trees, not just BST.
To create all possible paths, note that the topmost point of the path is special: it is the only point on the path that is allowed (although not required) to have both children in the path. Each path contains a single highest point. Therefore, the outer recursion layer should be to visit each node tree and generate all the paths that have the node as the highest point.
// Report whether any path whose topmost node is t sums to target. // Recurses to examine every node under t. EnumerateTopmost(Tree t, int target) { // Get a list of sums for paths containing the left child. // Include a 0 at the start to account for a "zero-length path" that // does not contain any children. This will be in increasing order. a = append(0, EnumerateSums(t.left)) // Do the same for paths containing the right child. This needs to // be sorted in decreasing order. b = reverse(append(0, EnumerateSums(t.right))) // "List match" to detect any pair of sums that works. // This is a linear-time algorithm that takes two sorted lists -- // one increasing, the other decreasing -- and detects whether there is // any pair of elements (one from the first list, the other from the // second) that sum to a given value. Starting at the beginning of // each list, we compute the current sum, and proceed to strike out any // elements that we know cannot be part of a satisfying pair. // If the sum of a[i] and b[j] is too small, then we know that a[i] // cannot be part of any satisfying pair, since all remaining elements // from b that it could be added to are at least as small as b[j], so we // can strike it out (which we do by advancing i by 1). Similarly if // the sum of a[i] and b[j] is too big, then we know that b[j] cannot // be part of any satisfying pair, since all remaining elements from a // that b[j] could be added to are at least as big as a[i], so we can // strike it out (which we do by advancing j by 1). If we get to the // end of either list without finding the right sum, there can be // no satisfying pair. i = 0 j = 0 while (i < length(a) and j < length(b)) { if (a[i] + b[j] + t.value < target) { i = i + 1 } else if (a[i] + b[j] + t.value > target) { j = j + 1 } else { print "Found! Topmost node=", t return } } // Recurse to examine the rest of the tree. EnumerateTopmost(t.left) EnumerateTopmost(t.right) } // Return a list of all sums that contain t and at most one of its children, // in increasing order. EnumerateSums(Tree t) { If (t == NULL) { // We have been called with the "child" of a leaf node. return [] // Empty list } else { // Include a 0 in one of the child sum lists to stand for // "just node t" (arbitrarily picking left here). // Note that even if t is a leaf node, we still call ourselves on // its "children" here -- in C/C++, a special "NULL" value represents // these nonexistent children. a = append(0, EnumerateSums(t.left)) b = EnumerateSums(t.right) Add t.value to each element in a Add t.value to each element in b // "Ordinary" list merge that simply combines two sorted lists // to produce a new sorted list, in linear time. c = ListMerge(a, b) return c } }
The above pseudo code only reports the topmost node in the path. The entire path can be restored if EnumerateSums() returns a list of pairs (sum, goesLeft) instead of a simple list of sums, where goesLeft is a Boolean value indicating whether the path used to generate this sum will first go from the parent node.
The above pseudo-code calculates lists of sums several times for each node: EnumerateSums(t) will be called once for each node above t in the tree, in addition to calling for t itself. It would be possible to make EnumerateSums() memoise a list of sums for each node so that it would not be recounted on subsequent calls, but this does not actually improve the asymptotics: only O (n) work is required, print a list of n sums using regular recursion, and changing this to O (1) will not change the overall time complexity, because the entire list of sums caused by any call to EnumerateSums() should generally be read by the caller, and this takes O (n) time. EDIT: As Evgeni Klyuyev noted, EnumerateSums() actually behaves like a merge sort, being O (nlog n) when the tree is perfectly balanced and O (n ^ 2) when this is the only way. Thus, memoisation will actually give an asymptotic performance improvement.
You can get rid of temporary sumlists by rearranging EnumerateSums() into an iterator-like object that merges lists lazily and can be queried to get the next sum in ascending order. This would also entail the creation of EnumerateSumsDown() , which does the same, but extracts the amounts in descending order and uses this instead of reverse(append(0, EnumerateSums(t.right))) . Doing this reduces the complexity of the algorithm space to O (n), where n is the number of nodes in the tree, since each iterator object requires constant space (pointers to left and right child iterator objects, and also the place to write the last sum), and may not be more than one per tree node.