Problem

Given a binary tree with an integer data element; find all paths whose sum of data nodes will be equal to a given value.

Path can start or end anywhere in the tree.

Example: If the sum given is 5 and a  path is 2->3->1>-1. There you should print two paths here: 2->3 and 2->3->1>-1.

Approach

Initial thoughts might be to go from every node and see if the path sums to the given value and print it. However you will still needs to go till the end to take care of the second path above.

A better cleaner solution will be to have a path array also passed along.

From every level, we will see if any path till that element gives the sum and print them.

To pass along the path, we need to assume that we know the depth as we need to create the path array with a size equal to depth.

Solution

void findPath(TreeNode n, int sum, int[] path, int level)

{

  path[level] = n.data;

  int s = 0;

  for(int i = level; i>=0; i--)

  {

    s = s + path[i];

    if( s == sum) print (path, i , level);

  }

 

  findPath(n.left, sum, path, level+1);

  findPath(n.right, sum, path, level + 1);

}

print (path, i , level) will print the elements of path array from location i to level.

this method can be invoked as:

int[] path = new int[depth];

findPath(root, sum, path, 0);

Complexity

Time and space complexity will be O(n logn).