Amazon Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
if(min_so_far > sum) {
min_so_far = sum;
min_path = cur_path;
}
this code will execute when we reaches leaf node.
after this it will pop leaf node from the stack cur_path and then pop operation will keep on executing until stack gets empty.
bcozzz of if else{} condition it will not execute it right path.
this code will show left most path of the tree.
plzz tell me if i getting it wrong..
Thanks
thanks for pointing out! it should be like this:
void min_sum(node *t, int sum) {
cur_path.push(t);
sum += t->val;
if(t->left == 0 && t->right == 0) { // found a leaf node
if(min_so_far > sum) {
min_so_far = sum;
min_path = cur_path;
}
}
if(t->left != 0) {
min_sum(t->left, sum);
}
if(t->right != 0) {
min_sum(t->right, sum);
}
cur_path.pop(t);
}
ok just see this every time decision involved weather u have to go left or right so just first check the minimum sum from t->left as root and t->right as a root which is less go there code for this algo
void PrintMinPath(struct node *T)
{
int ls,rs;
if(!T)
return;
printf("%d\n",T->info);
ls=GetMinSum(T->left);
rs=GetMinSum(T->right);
if(ls<=rs)
PrintMinPath(T->left);
else
PrintMinPath(T->right);
}
int GetMinSum(struct node *T)
{
int ls,rs;
if(!T)
return 0;
ls=GetMinSum(T->left)+T->info;
rs=GetMinSum(T->right)+T->info;
if(ls<=rs)
return ls;
else
return rs;
}
nice...ur code with some corrections
void PrintMinPath(struct node *T)
{
int ls=999,rs=999;
if(!T)
return;
printf("%d\n",T->info);
if(T->left) ls=GetMinSum(T->left);
if(T->right)rs=GetMinSum(T->right);
if(ls<=rs)
PrintMinPath(T->left);
else
PrintMinPath(T->right);
}
int GetMinSum(struct node *T)
{
int ls,rs;
if(!T)
return 0;
ls=GetMinSum(T->left)+T->info;
rs=GetMinSum(T->right)+T->info;
if(ls<=rs)
return ls;
else
return rs;
}
i guess now it runs perfectly
Sure but you're calling GetMinSum potentially many times for each node. How about, 2 extensible arrays that are the depth of the tree (or stacks), and a globally least/greatest path sum, and one of the stacks for the best path so far.
Traverse the tree, keeping the sum-so-far on the way down at each node, and pushing the current node into the temporary stack, as you go (pop it on the way back up of course). At the leaf nodes, see whether the sum-so-far is greater / less than the global one, and if so copy the temporary stack to the global one.
At the end, print the global stack.
int maxLen = 0;
node* targetLeaf;
list<char> crt, final;
void findMAXPath(node* root, int length)
{
if(!root->lchild && !root->rchild)
{
if(length + root->element > maxLen)
{
targetLef = root;
maxLen = length + root->element;
final = crt;
return;
}
}
if(!root->lchild)
{
crt.pushback('L');
findMaxPath(root->lchild, length + root->elem);
}
if(!root->rchild)
{
crt.pushback('R');
findMaxPath(root->rchild, length + root->elem);
}
crt.popback();
return;
}
nice and easy ))
here is the code:
- practice coding October 10, 2011