CareerCup

How do we define a path? If we are assuming that the path in the tree starts from a root and can stop any where in the tree. A simple depth first search can solve this question.

void dfs(root,sum,path) {
if(!root) return;
if(sum ==0 ) { print path; return; }
if(sum < 0) { return; }
dfs(root->left,sum-root->value,path+","+root->value);
dfs(root->right,sum-root->value,path+","+root->value);
}

A path may not start from root, right? So in that case we need to find a connected component in this tree (where only one of the outgoing links from a node is considered) whose values sum up to 'k'.
Please correct me if my understanding is wrong.

simple recursive algo: solu( subroot, target) = solution (subroot->left, target) union solution(subroot->right, target) uniton { solu(subroot->left, s1) union solu (subroot->right, s2) ,such that s1+s2 == target - subroot->value )

with recursive dfs one could pass an array around:

checksum
    print all in array

    push(node);
    walk(node->left);
    walk(node->right);
    pop(node);

obviously this uses double the space needed, 1 for the actual stack and one for the passed around one. an alternative is to use stack based dfs, but theres a catch in doing it the convventional way (you cant pop the parent before going right).