Amazon Interview Question
Software Engineer / DevelopersTeam: RCX
Country: United States
Interview Type: In-Person
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).
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.
- Akshat January 09, 2012void 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);
}