You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. The path does not need to start or end at the root or a leaf?

The key idea here is to recognize that any simple path will consist of an optional "upward" portion of the path, some "highest" node, and then an optional "downward" portion of the path. Seen another way, there are 3 types of paths: Trivial paths consist of a single node. Fork-free paths consist of some highest node and only go downwards in one branch from there. Forked paths contain a highest node, and then have two branches that go down. Trivial paths are trivial to check (compare each value to the target value), and fork-free paths can be checked using an approach similar or identical to the approach shown in Cracking the Coding Interview. Only forked paths -- the most difficult case -- remain.First, we will consider the problem of simply detecting whether a forked path summing up to a target value T exists anywhere. Then, we can consider how we would print the paths if desired.Part 1: Basic idea, solving the problem for balanced trees in O(S log S) time, where S is tree size.Our plan of attack will be as follows: we will consider each node of the tree that has two children as a possible highest-node N for a forked path, and consider whether we can find a path from N.left going downwards that sums to X and a path from N.right going downwards that sums to Y, such that X + Y + N.value = T, where T is the target sum. That means we should look for X, Y where X + Y = T - N.value.Consider the subtree rooted at N.left. We can take that subtree and traverse it to generate, for each node within the subtree, the sum of the path from the subtree's root to that node. This data is returned back as a set (of sums) that we'll call the sum-set for N.left. Similarly, we generate the sum-set for N.right. The sets contain one element for each node visited, and therefore are of size O(N.left.treeSize) and O(N.right.treeSize). "treeSize" is the number of total descendants (children, grandchildren, etc.) a node has, plus 1 for itself. Now we calculate T - N.value, and then run a procedure similar to that used in the https://www.careercup.com/question?id=15206700 to determine whether there exists an X in the left set and a Y in the right set such that X + Y = T - N.value. This procedure runs in O(N.left.treeSize + N.right.treeSize) = O(N.treeSize), since N.treeSize = N.left.treeSize + N.right.treeSize + 1. So, the overall evaluation for each node N, including traversal of the subtrees, generating the sets, and intersecting the sets runs in O(N.treeSize).Note that for each distinct node height, the sum of the tree sizes of all the nodes at that height cannot exceed S, the total number of nodes in the entire tree on which we're running this algorithm (otherwise, the tree would have more than S nodes). That means the algorithm does at most O(HS) work, where H is the height of the tree.For a balanced tree, this algorithm therefore runs in O(S log S). For an unbalanced tree, the algorithm needs improvement because it may take O(S^2).Part 2: Improving the solution to run in O(S log S) even for unbalanced trees.To improve the algorithm, we can give a better sum-set generation procedure. This gets rather complicated, so I will only give a sketch. Rather than generating the sum-sets from scratch for each node, we generate the sum-set for each node by merging the sum-sets produced by the two children. We can do this merge in a clever way: always merge the smaller set into the larger set. This ensures that each element is moved between sets at most O(log S) times, since the first time an element gets merged into a new set, the new set must be of size at least 2, the second time the size must be at least 4, then at least 8 ..., size at least S after O(log S) steps. This will ensure the total work done in merging sets is O(S log S), assuming standard O(1) set operations.After each set merge, we will need to add in the contribution of N.value. This too requires a clever technique, since having to modify every element of the set to add N.value to it would break the previous analysis concerning the upper bound on the number of times a set element may be touched. We therefore must implement a technique of constant-folding: we store a set as a 2-tuple (C, S) of a constant and a set. This is interpreted as a set containing the value V+C for each value V in S. With this representation, we can easily add a constant to all the elements of the set in O(1): (C1 + S) + a constant C2 = (C1 + C2, S). We can verify that even when sets use constant folding, we can still merge a set into another set in O(1) per element in the first set.Likewise, to do the 2-sum operation, we will always look up the elements of the smaller set in the larger set, giving an O(S log S) runtime for that step by a similar argument.As a result only the set-merge and 2-sum operations take O(S log S) total time over all nodes. Everything else is O(1) per node, so O(S) over all nodes, for a total complexity of O(S log S).As you can see, this solution to achieve O(S log S) running time for all tree shapes (not necessarily balanced) is rather complex. If anyone has an O(S) algorithm or a simpler O(S log S) algorithm, I would be interested to hear it.Part 3: Enumerating paths or counting pathsWe can now come back to the question of printing the paths. We can store with each sum in the sum-sets a pointer to the bottom-most node of the path. If the tree is also augmented with parent pointers (which could have been done in linear time prior to starting the main algorithm), you can then recover the path up to the highest node of the path (where the fork is), and combine that with the matching second part of the path. In this case, the complexity will be O(S log S + sum(printed path lengths)).We can also easily modify the algorithm to count the number of paths adding up to T in O(S log S).

public class Node { public int Data { get; set; } public Node Left { get; set; } public Node Right { get; set; } } public class SumNode { public Node IndivNode { get; set; } public List<List<Node>> SumParts { get; set; } } private static List<SumNode> FindAllSumPaths(Node root) { List<SumNode> list = new List<SumNode>(); Queue<Node> q = new Queue<Node>(); q.Enqueue(root); Node current; while(q.Count > 0) { current = q.Dequeue(); List<Node> curNodes = new List<Node>(); List<List<Node>> sumPaths = new List<List<Node>>(); GetAllSumPathsThatSumUpTo(current, current.Data, curNodes, sumPaths); list.Add( new SumNode() { IndivNode = current, SumParts = sumPaths }); if(current.Left != null) q.Enqueue(current.Left); if(current.Right != null) q.Enqueue(current.Right); } return list; } private static void GetAllSumPathsThatSumUpTo(Node n, int sum, List<Node> curNodes, List<List<Node>> allNodes) { if (n == null) return; curNodes.Add(n); if (sum == 0) { /*curNodes at this point contains the collection of Nodes that sum up to their respective root's value. This step clones those records into a new List and adds them to the allNodes List.*/ allNodes.Add(new List<Node> (curNodes)); } if (n.Left != null) { GetAllSumPathsThatSumUpTo(n.Left, sum - n.Left.Data, curNodes, allNodes); } if (n.Right != null) { GetAllSumPathsThatSumUpTo(n.Right, sum - n.Right.Data, curNodes, allNodes); } /*Remove elements from the curNodes that did not sum up to the parent node on stack return. */ curNodes.Remove(new Node() { Data = n.Data }); return; }

I was also wondering the same as the book does not talk about the Forked Paths. I tried to construct one using Recursion and HashMaps. Hope it solves the purpose. package ramanCodeLibraray.datastructures; import java.util.ArrayList; import java.util.HashMap; import java.util.LinkedList; import java.util.Map; /** * @author Ramanpreet Singh Khinda * @category Program to find path (including Forked Paths) in a binary tree * which sums to a given value */ class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int data) { this.val = data; } } public class ForkedPathTree { private HashMap<Integer, ArrayList<LinkedList<Integer>>> findPathRecursively(TreeNode root, final int sum) { if (null == root) { return null; } /** * The path map is a hashmap which contains all the information for the * path from root down to its all the children nodes. Here "Key" is the * Sum of nodes in the path and "Value" is the List of all the paths * with specified sum key */ HashMap<Integer, ArrayList<LinkedList<Integer>>> leftPathMap = findPathRecursively(root.left, sum); HashMap<Integer, ArrayList<LinkedList<Integer>>> rightPathMap = findPathRecursively(root.right, sum); /** * Fork-free paths: check if the left subtree contains a path with the * required sum */ if (null != leftPathMap) { if (leftPathMap.containsKey(sum)) { ArrayList<LinkedList<Integer>> pathList = leftPathMap.get(sum); for (LinkedList<Integer> path : pathList) { System.out.println(""); for (int nodeData : path) { System.out.print(nodeData + " -> "); } } } } /** * Fork-free paths: check if the right subtree contains a path with the * required sum */ if (null != rightPathMap && rightPathMap.containsKey(sum)) { ArrayList<LinkedList<Integer>> pathList = rightPathMap.get(sum); for (LinkedList<Integer> path : pathList) { System.out.println(""); for (int nodeData : path) { System.out.print(nodeData + " -> "); } } } /** * Forked Path: check if any combination of left subtree, Root and right * subtree contains a path with the required sum */ if (null != leftPathMap) { for (Map.Entry<Integer, ArrayList<LinkedList<Integer>>> leftEntry : leftPathMap.entrySet()) { int partialSum = root.val + leftEntry.getKey(); if (null != rightPathMap && rightPathMap.containsKey((sum - partialSum))) { ArrayList<LinkedList<Integer>> leftPathList = leftEntry.getValue(); ArrayList<LinkedList<Integer>> rightPathList = rightPathMap.get((sum - partialSum)); for (LinkedList<Integer> leftPath : leftPathList) { for (LinkedList<Integer> rightPath : rightPathList) { System.out.println(""); for (int index = leftPath.size() - 1; index >= 0; index--) { System.out.print(leftPath.get(index) + " -> "); } System.out.print(root.val + " -> "); for (int rightNode : rightPath) { System.out.print(rightNode + " -> "); } } } } } } /** * Constructing combined path map from the path map of left subtree and * right subtree. This path map is returned back to the calling parent * node. */ HashMap<Integer, ArrayList<LinkedList<Integer>>> myMap = new HashMap<Integer, ArrayList<LinkedList<Integer>>>(); ArrayList<LinkedList<Integer>> myPathList = new ArrayList<LinkedList<Integer>>(); LinkedList<Integer> myPath = new LinkedList<Integer>(); myPath.addFirst(root.val); myPathList.add(myPath); myMap.put(root.val, myPathList); if (null != leftPathMap) { for (Map.Entry<Integer, ArrayList<LinkedList<Integer>>> leftEntry : leftPathMap.entrySet()) { int newSum = root.val + leftEntry.getKey(); ArrayList<LinkedList<Integer>> pathList = leftEntry.getValue(); for (LinkedList<Integer> path : pathList) { path.addFirst(root.val); } if (myMap.containsKey(newSum)) { myPathList = myMap.get(newSum); } else { myPathList = new ArrayList<LinkedList<Integer>>(); } myPathList.addAll(pathList); myMap.put(newSum, myPathList); } } if (null != rightPathMap) { for (Map.Entry<Integer, ArrayList<LinkedList<Integer>>> rightEntry : rightPathMap.entrySet()) { int newSum = root.val + rightEntry.getKey(); ArrayList<LinkedList<Integer>> pathList = rightEntry.getValue(); for (LinkedList<Integer> path : pathList) { path.addFirst(root.val); } if (myMap.containsKey(newSum)) { myPathList = myMap.get(newSum); } else { myPathList = new ArrayList<LinkedList<Integer>>(); } myPathList.addAll(pathList); myMap.put(newSum, myPathList); } } return myMap; } private void printPathToSum(TreeNode root, final int sum) { HashMap<Integer, ArrayList<LinkedList<Integer>>> map = findPathRecursively(root, sum); /** * Checking the path map returned by root node */ if (null != map && map.containsKey(sum)) { ArrayList<LinkedList<Integer>> pathList = map.get(sum); for (LinkedList<Integer> path : pathList) { System.out.println(""); for (int nodeData : path) { System.out.print(nodeData + " -> "); } } } } public static void main(String[] args) { ForkedPathTree tree = new ForkedPathTree(); /** * Lets construct a complex tree with + and - values * * 3 * / \ * -2 -3 * / / \ * 5 3 3 * / \ / \ * 3 -1 7 1 * / \ * 5 4 * / * 2 */ TreeNode root = new TreeNode(3); root.left = new TreeNode(-2); root.left.left = new TreeNode(5); root.left.left.left = new TreeNode(3); root.left.left.right = new TreeNode(-1); root.left.left.right.left = new TreeNode(5); root.left.left.right.right = new TreeNode(4); root.left.left.right.right.left = new TreeNode(2); root.right = new TreeNode(-3); root.right.left = new TreeNode(3); root.right.right = new TreeNode(3); root.right.right.left = new TreeNode(7); root.right.right.right = new TreeNode(1); tree.printPathToSum(root, 10); } }