CareerCup

I think it's not correct as in your case it seems like every path in the tree should start in the root of the tree. I guess print_path_with_sum is the first function to be called, and it start counting the sum from this place. But what if the sum starts later let's say having a following binary tree (you didn't mention it's binary search tree so will keep it just as binary tree) and you look for sum 5?

root:                   1
level 1:         2           8
level 2:   4         3

Obviously the sum is there but looks like 2, 3, and doesn't start from the root. The solution to this problem is described in Cracking Coding Review book AFAIR.

joe kidd, thanks for your response. Apparently you missed that fact that the main function (print_path_with_sum) calls the inner function (search_to_bottom) for EVERY node in the tree. So it will find other paths than those starting at the root.

I know the solution from the Cracking the Coding Interview book, I just wanted to present my approach and get some opinions.

Running on some sample data, it seems that my function visits fewer nodes than the book's solution. But they are probably equal in the worst case.

Store all the values from the tree in an array in an inorder traversal form. Of course it wont give us a sorted array as it is not a binary search tree but then in the array just apply the sum of subsets algorithm to generate all the possible paths in the array. Now two scenarios arise:
a. If in the path the root node of the tree is included then just subtract the root node from the sum and then check for the remaining sum subset in the array.
b. If in the path root node is not to be included then just apply the sos algorithm and you will get all the paths that lead us to a given sum

void checkPath(Node<T> cur, int actualSum, int expectedSum, Deque<T> path ){
		
		if( cur == null || actualSum > expectedSum ){
			return;
		}
		
		actualSum += (Integer)cur.value;
		path.push( cur.value );
		
		if( actualSum == expectedSum && cur.isLeaf() ){
			System.out.println( path );
			path.pop();
		}
		else {				
			checkPath(cur.left, actualSum, expectedSum, path);
			checkPath(cur.right, actualSum, expectedSum, path);
			
			path.pop();
		}
		
	}

Using depth first search on the tree, create a hashtable with all the paths and there corresponding sum, then iterate through the hashtable to get the sum. To save the iteration of hashtable, we can instantly print the result

Hashtable ht = new Hashtable();
        int MySum = 0;
        List<MyNode> MyPath = new List<MyNode>();

        private ArrayList GetAllPathWithSum(int sum)
        {
            ArrayList result = new ArrayList();
            MyNode node = tree.root;

            GetMyHash(node);

            var e = ht.GetEnumerator();

            while (e.MoveNext())
            {
                int CurrentKey = Convert.ToInt32(e.Value);
                if (CurrentKey == sum)
                    result.Add(e.Key);

            }

            return result;
        }

        private void GetMyHash(MyNode node)
        {
            if (node != null)
            {
                MySum += node.Value;
                MyPath.Add(node);

                ht.Add(MyPath.ToArray(),MySum );

                GetMyHash(node.Left);
                GetMyHash(node.Right);

                int iLastNodeIndex = MyPath.Count - 1;
                MySum -= MyPath[iLastNodeIndex].Value;
                MyPath.RemoveAt(iLastNodeIndex);
            }
            
        }