Amazon Interview Question Analysts
int findMinSum(struct node* root)
{
static int minSum = INT_MAX;
int Sum;
if(root == NULL)
{
return 0;
}
if( !root->left && !root->right )
{
if(Sum < minSum)
minSum = Sum;
}
Sum = root->data + findMinSum(root->left);
Sum = root->data + findMinSum(root->right);
return minSum;
}
Please let me know whether this is fine
I realized Sum and Path should have passed as argument.
Signature will become
void findMinSum(struct node* root, int Sum, int path[], int len)
{
static int minSum = INT_MAX;
if(root == NULL)
return ;
Sum = root->d + Sum;
path[len++] = root->d;
if( root->left == NULL && root->right == NULL)
{
if(Sum < minSum)
{
minSum = Sum;
for (int i = 0 ; i < len ; ++i)
cout << path[i] << endl;
}
}
findMinSum(root->left, Sum, path, len);
findMinSum(root->right, Sum, path, len);
}
int paths[100];
Call findMinSum(root, 0, paths, 100);
Am I corrected here ? Appreciate if you point to coding error.
void getMinSumAndPath
(
node* root, int* curPath, int* path,
int curSum, int& minSum, int level
)
{
if(root==0) return;
curPath[level]=root->data;
curSum += root->data;
getMinSumAndPath(root->left,curPath,path,curSum,minSum,level+1);
getMinSumAndPath(root->right,curPath,path,curSum,minSum,level+1);
if(minSum>curSum)
{
minSum=curSum;
path[0]=level;/*length of the path*/
for(int i=0;i<level;i++)
{
path[i+1]=curPath[i];
}
}
}
void printMinSumAndPath(node* root)
{
int path[100]={0};
int curPath[100]={0};
int minSum=~(1<<31), curSum=0;
getMinSumAndPath(root,curPath,path,curSum,minSum,0);
cout<<"Min Sum"<<minSum<<endl;
for(int i=0;i<path[0];i++)
{
cout<<path[i+1]<<" ";
}
cout<<endl;
}
Perform a simple depth first traversal of the tree (Pre-order traversal).
Keep a global sum variable and increment it when u move down the tree and decrement when u move up.
Here's the pseudocode :-
int gsum = 0;
int globalsum = 10000; //global sum variable used to store sum
smallestsum(node *root)
{
gsum += root->data;
if(root->left==NULL && root->right==NULL)// on encountering a leaf node
{
if(globalsum > gsum)
globalsum = gsum;
gsum -= root->data;
}
smallestsum(root->left);
smallestsum(root->right);
}
cout<<globalsum;
Perform a simple depth first traversal of the tree (Pre-order traversal).
Keep a global sum variable and increment it when u move down the tree and decrement when u move up.
Here's the pseudocode :-
int gsum = 0;
int globalsum = 10000; //global sum variable used to store sum
smallestsum(node *root)
{
gsum += root->data;
if(root->left==NULL && root->right==NULL)// on encountering a leaf node
{
if(globalsum > gsum)
globalsum = gsum;
gsum -= root->data;
}
smallestsum(root->left);
smallestsum(root->right);
}
cout<<globalsum;
- abrham July 18, 2011int findMinSum(struct node* root) { if(root == NULL) }