CareerCup

With a BST we have an added advantage that we know all the nodes on the left is less than the current node and all the nodes on the right are greater than the current node.

So, while doing a DFS to search for a minLen path in a BST we actually can take informed decision at each node to either go left or right based on the remaining sum to search and hence cutting down the search space in half in average case. This will guarantee finding the minimum length path because -

1) If current node value is equal to sum and it is a leaf node than we have a complete path. If it is not a leaf then we need to find a zero sum minLen path along one of its subtrees.

2) If current node value is greater than (or equal to) the remaining sum i.e. value>=(sum-value) then we should search for new sum=(sum-value) in the left sub tree because - if a path exists in the left subtree, it must be the shorter than any possible path in the right subtree, since all nodes at left is smaller than those at right.

3) Similarly, If current node value is smaller than the remaining sum i.e. value<(sum-value) then we should search for new sum=(sum-value) in the right sub tree because - if a path exists in the right subtree, it must be the shorter than any possible path in the right subtree, since all nodes at right is greater than those at left.

So, average case complexity will be improved to O(lgn) with a complete BST. However, the worst case complexity will be O(n) in case where we have to search both left and right subtree for the remaining sum.

private int minLenSumPathBST(final TreeNode root, final int sum, final int len) {
    if (root == null) {
        return Integer.MAX_VALUE;
    }

    // find the remaining sum as we are including current node in the current path
    final int remainingSum = sum - root.key;
    // If remaining sum is zero and it is a leaf node then we found a complete path from root to a leaf.
    if (remainingSum == 0 && root.left == null && root.right == null) {
        return len + 1;
    }
    // If remaining sum is less than current node value then we search remaining in the left subtree.
    else if (remainingSum <= root.key) {
        int l = minLenSumPathBST(root.left, remainingSum, len + 1);
        // if search in left subtree fails to find such path only then we search in the right subtree
        if (l == Integer.MAX_VALUE) {
            l = minLenSumPathBST(root.right, remainingSum, len + 1);
        }

        return l;
    }
    // If remaining sum is greater than current node value then we search remaining in the right subtree.
    else {
        int l = minLenSumPathBST(root.right, remainingSum, len + 1);
        // if search in right subtree fails to find such path only then we search in the left subtree
        if (l == Integer.MAX_VALUE) {
            l = minLenSumPathBST(root.left, remainingSum, len + 1);
        }

        return l;
    }
}

DFS, always search the larger subtree first.
In BST, you can skip the other subtree if its value is too big. Thus the time complexity can be O(n) in best case.

In BT we have to search every path to get the final result, because we do not know any info about subtrees. But in BST, as long as we find a path meeting the requirement we can stop the searching process:
(0)say now we encounter node p, with its value being p->value, then we perform targetSum -= p->value.
(1)If targetSum < 0 now
our first choice would be going on with the left subtree, because:
if a path exists along the left subtree, it must be shorter than any possible path along the right, since all nodes at left is smaller than those at right.
If there is no such path along the left, then we check p->value, if it is negative, then we go on searching right subtree,
else we stop current searching because all nodes at right(larger than p->value) is positive, which can not have a negative sum.
(2)If targetSum > 0 now
similar with (1), yet our first choice would be going on with right subtree, because:
if the path exists along the right subtree, it must be shorter than any possible path along the left, since all nodes at right is greater than those at left.
If there is no such path along the right, then we check p->value, if it is positive, then we go on searching left subtree,
else we stop current searching because all nodes at left(smaller than p->value) is negative, which can not have a positive sum.
(3)If targetSum = 0 now
if p is not a leaf, then current path is a dead end, no need to search deeper;
else the shortest path is found!
Following is code in C++:

struct TreeNode
{
	int value;
	TreeNode* left;
	TreeNode* right;
};
int getShortestPathWithSumInBST(TreeNode* root, int sum)
{
	if(root == NULL) return -1;

	int res;
	if(helper(root, sum, 0, res)) return res;
	return -1;
}
bool helper(TreeNode* p, int sum, int prevLen, int& res)
{
	sum -= p->value;
	++prevLen;
	if(sum < 0){
		return p->left != NULL && helper(p->left, sum, prevLen, res) ||
	    	   p->value < 0 && p->right != NULL && helper(p->right, sum, prevLen, res);
	}
	else if(sum > 0){
	    return p->right != NULL && helper(p->right, sum, prevLen, res) ||
	    	   p->value > 0 && p->left != NULL && helper(p->left, sum, prevLen, res);
	}
	else{
		if(p->left != NULL || p->right != NULL) return false;
		res = prevLen;
		return true;
	}
}

This the Java version inspired by uuuouou. Thanks.

public class Test{
	public class Node{
		int value;
		Node left;
		Node right;
		
		public Node(int value){
			this.value = value;
			this.left = null;
			this.right = null;
		}
	}
	
	public int findMinimumLength(Node root, int rest){
		if(root == null){
			return Integer.MAX_VALUE;
		}
		rest -= root.value;
		int minValue = Integer.MAX_VALUE;
		//if rest is less than 0, then if we go to left child, we may be faster since all
		//the values in the left subtree are less than that in the right subtree.
		if(rest < 0){
			if(root.left != null){
				int value = findMinimumLength(root.left, rest);
				minValue = Math.min(minValue, value);
			}
			if(minValue == Integer.MAX_VALUE && root.right != null){
				minValue = Math.min(minValue, findMinimumLength(root.right, rest));
			}
		}else if(rest > 0){//same thing with right tree.
			if(root.right != null){
				int value = findMinimumLength(root.right, rest);
				minValue = Math.min(minValue, value);
			}
			if(minValue == Integer.MAX_VALUE && root.left != null){
				minValue = Math.min(minValue, findMinimumLength(root.left, rest));
			}
		}else{//find the sum and this node is the leaf node.
			if(root.left == null && root.right == null){
				minValue = 0;
			}
		}
		//try to avoid integer overflow
		if(minValue == Integer.MAX_VALUE){
			return Integer.MAX_VALUE;
		}else{
			return minValue + 1;
		}
	}
	
	public static void main(String[] args){
		Test test = new Test();
		
		Node root = test.new Node(10);
		root.left = test.new Node(2);
		root.right = test.new Node(5);
		root.left.left = test.new Node(3);
		
		System.out.println(test.findMinimumLength(root, 15));
		
	}
}

hey

play.google.com/store/apps/details?id=com.couponkart.couponcodes

try this out . might be useful

For a general tree:

static int minlen=Integer.MAX_VALUE;
public int minRootToLeafPathLength(TreeJ root,int len,int Sum, int val){
		if(root==null){
			return 0;
		}
		int p=val+Integer.parseInt(root.val.toString());
		if(p==Sum && (root.left==null && root.right==null)){
			if(len<minlen){
				minlen=len+1;
			}
		}
		minRootToLeafPathLength(root.right,len+1,Sum,p);
		minRootToLeafPathLength(root.left,len+1,Sum,p);
		
		return minlen;
	}

Call this: System.out.println(tf.minRootToLeafPathLength(root, 0, 21, 0));
Create tree:

public void makeSimpleTree(){
		root=new TreeJ<Integer>(5);
		root.right=new TreeJ<Integer>(6);
    	root.right.left=new TreeJ<Integer>(2);
		root.right.right=new TreeJ<Integer>(4);
		root.right.right.left=new TreeJ<Integer>(7);
		root.right.right.left.right=new TreeJ<Integer>(1);
		
		root.left=new TreeJ<Integer>(8);
		root.left.left=new TreeJ<Integer>(5);
		root.left.right=new TreeJ<Integer>(4);
		root.left.left.left=new TreeJ<Integer>(3);
		root.left.right.left=new TreeJ<Integer>(6);
		
	}

int find_sum(Item* root, sum) {
  if (!root && !sum)
    return 0;
  if (!root || root->i > sum)
    return -1;
  int new_sum = sum - root->i;
  int rs = -1;
  if (new_sum > root->i)
    rs = find_sum(root->right, new_sum);
  if (rs == -1)
    find_sum(root->left, new_sum);
  return rs + 1;
}