Adobe Interview Question
Computer ScientistsDid you try to run this.
This code does not clears the pPath array so after first leaf path it will produce incorrect path.
Correct me if I am missing something.
I think calling it separately for left sub tree and right sub tree will solve this issue.
@Upt: I doubt that u understand the recursion. Trace it properly u'll come to know. BTW its tested code.
I think you are correct. Can you post some link from where I can learn about recursion. I searched and found lots of them. Just asking in case if you have bookmark of any.
What I was thinking is we have a pointer to pPath which is an array and we never delete any element from it. Also the printing is done from 0 to index. So say if we consider right sub tree it should give correct results but when it comes to the left sub tree what will happen?
Try to help me that where I am going wrong.
Here is a working function code that prints all paths from root to the leaves :
Note I have created a dummy main() to test the function.
#include<iostream> /* Generic Headers */
using namespace std;
typedef unsigned int Uint;
struct node{
string val;
node* leftChild;
node* rightChild;
} *root, *A,*B,*C,*D,*E,*F,*G;
void printPath(node *p,string path)
{
if(p->leftChild==NULL&&p->rightChild==NULL)
{ cout<<(path+"->"+p->val)<<endl; return; }
if(p->leftChild!=NULL)
printPath(p->leftChild,(path+"->"+p->val));
if(p->rightChild!=NULL)
printPath(p->rightChild,(path+"->"+p->val));
}
int main()
{
A = new node; A->val = "A";
B = new node; B->val = "B";
C = new node; C->val = "C";
D = new node; D->val = "D";
E = new node; E->val = "E";
F = new node; F->val = "F";
G = new node; G->val = "G";
A->leftChild = B; A->rightChild = D;
B->leftChild = NULL; B->rightChild = C;
C->leftChild = NULL; C->rightChild = NULL;
D->leftChild = E; D->rightChild = F;
E->leftChild = NULL; E->rightChild = G;
F->leftChild = NULL; F->rightChild = NULL;
G->leftChild = NULL; G->rightChild = NULL;
root = A;
printPath(root,"Start");
}
Working tested code....
int printpath(tree *root)
{
static int count;
int i;
if(!root)
{
return 0;
}
if(root->left == NULL && root->right==NULL)
{
a[count++]= root->data;
for(i=0;i<count;i++)
printf("__%d__",a[i]);
printf("\n");
return 0;
}
a[count++]= root->data;
if(root->left!=NULL)
{
printpath(root->left);
count--;
}
if(root->right!=NULL)
{
printpath(root->right);
count--;
}
return 0;
}
{
#include "iostream"
using namespace std;
struct node
{
node* left;
node* right;
string val;
node(string data )
{
val=data;
left=NULL;
right=NULL;
}
};
void printPaths(node* nd, string path)
{
if(nd==NULL)
return;
if(path.empty())
path = nd->val;
else
path+= nd->val;
if(nd->left==NULL && nd->right==NULL)
{
unsigned int i = 0;
while(i<path.size())
{
cout << path[i];
i+=1;
}
cout << endl;
return;
}
printPaths(nd->left,path);
printPaths(nd->right,path);
}
int main()
{
node* root = new node("A");
root->left=new node("B");
root->right=new node("C");
root->left->left=new node("D");
root->left->right=new node("K");
root->right->left=new node("Z");
root->right->right=new node("E");
printPaths(root,"");
}
}
- Anonymous June 15, 2011