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.
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.
My answer is O(n^2), but I believe it is accurate, and takes a slightly different approach and looks easier to implement.
Assume the value stored at node i is denoted by VALUE[i]. My idea is to store at each node the sum of the values on the path from root to that node. So for each node i, SUM[i] is sum of path from root to node i.
Then for each node pair (i,j), find their common ancestor k. If SUM(i)+SUM(j)-SUM(k) = TARGET_SUM, you have found an answer.
This is O(n^2) since we are looping over all node pairs. Although, I wish I can figure out a better way than just picking all pairs.
We could optimize it a little by discarding subtrees where the value of the node rooted at the subtree is greater than TARGET_SUM. Any further optimizations are welcome :)
Psuedocode:
# Skipping code for storing sum of values from root to each node i in SUM[i] for i in nodes: for j in nodes: k = common_ancestor(i,j) if ( SUM[i] + SUM[j] - SUM[k] == TARGET_SUM ): print_path(i,k,j) Function common_ancestor is a pretty standard problem for a binary search tree. Psuedocode (from memory, hopefully there are no errors!):
sub common_ancestor (i, j): parent_i = parent(i) # Go up the parent chain until parent's value is out of the range. # That's a red flag. while( VAL[i] <= VAL[parent_i] <= VAL[j] ) : last_parent = parent_i parent_i = parent(i) if ( parent_i == NULL ): # root node break return last_parent Old question, but here's my stab at it - should be O(n) time as your visiting each node only once:
public static List<ArrayList<Integer>> pathSum(Node head, int sum) { List<Integer> currentPath = new ArrayList<Integer>(); List<ArrayList<Integer>> validPaths = new ArrayList<ArrayList<Integer>>(); dfsSum(head, sum, currentPath, validPaths); return validPaths; } public static void dfsSum(Node head, int sum, List<Integer> currentPath, List<ArrayList<Integer>> validPaths) { if (head == null) return; currentPath.add(head.val); if (head.left == null && head.right == null && sum == head.val) { validPaths.add(new ArrayList<Integer>(currentPath)); } dfsSum(head.left, sum - head.val, new ArrayList<Integer>(currentPath), validPaths); dfsSum(head.right, sum - head.val, new ArrayList<Integer>(currentPath), validPaths); } And the node class:
class Node { public int val; public Node left; public Node right; public Node(int val) { this.val = val; } } 