Yahoo Interview Question
Software Engineer / DevelopersWill this work?
Assuming there are n children for every node
void printPath(int []path, int pathLen, tree *root)
{
if(root==NULL) return;
path[pathLen++]=root->data;
if(root->p1==NULL && root->p2==NULL & .... & root->pn==NULL)
{
for(int i=0;i<pathLen;i++)
print("%d\t",path[i]);
printf("\n");
}
printPath(path,pathLen,root->p1);
printPath(path,pathLen,root->p2);
printPath(path,pathLen,root->p3);
...
printPath(path,pathLen,root->pn);
}
perform an inorder tree traversal with maintaining 2 lists(pathSoFar and finalPath) to record and maintain the path. Both the lists are filled until the last node, for the last node only fill in the finalPath and print it and end the recursive call there.. the previous will have a pathSoFar minus the recently visited node.. continue for the rest of the tree..
The solution is space constrained.. needs extra space but at a speed of O(n)
Well this problem can be solved by taking a path[] array and storing all the elements in the array while moving to a particular path and as soon as we reach a leaf node just print the path array. Here is the working code.
- Spock July 07, 2012