Amazon Interview Question SDE-2s
Country: India
Interview Type: In-Person
#include<stdio.h>
#include<limits.h>
#define FALSE 0
#define TRUE 1
/* A tree node structure */
struct node
{
int data;
struct node *left;
struct node *right;
};
// A utility function that prints all nodes on the path from root to target_leaf
int printPath (struct node *root, struct node *target_leaf)
{
if(root==NULL)
return FALSE;
if (root == target_leaf || printPath(root->left, target_leaf) ||
printPath(root->right, target_leaf) )
{
printf("%d ", root->data);
return TRUE;
}
return FALSE;
}
// This function Sets the target_leaf_ref to refer the leaf node of the maximum
// path sum. Also, returns the max_sum using max_sum_ref
void getTargetLeaf (struct node *node, int *max_sum_ref, int curr_sum,
struct node **target_leaf_ref)
{
if(node == NULL)
return ;
curr_sum = curr_sum + node->data;
if(node->left==NULL && node->right==NULL)
if(curr_sum < *max_sum_ref){
*max_sum_ref = curr_sum;
*target_leaf_ref = node;
}
getTargetLeaf(node->left,max_sum_ref,curr_sum,target_leaf_ref);
getTargetLeaf(node->right,max_sum_ref,curr_sum,target_leaf_ref);
}
// Returns the maximum sum and prints the nodes on max sum path
int maxSumPath (struct node *node)
{
if (node == NULL)
return 0;
struct node *smallest_path;
int min_path = INT_MAX;
getTargetLeaf(node,&min_path,0,&smallest_path);
printPath(node,smallest_path);
return min_path;
// base case
}
/* Utility function to create a new Binary Tree node */
struct node* newNode (int data)
{
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
/* Driver function to test above functions */
int main()
{
struct node *root = NULL;
/* Constructing tree given in the above figure */
root = newNode(10);
root->left = newNode(-2);
root->right = newNode(7);
root->left->left = newNode(8);
root->left->right = newNode(-4);
printf ("Following are the nodes on the maximum sum path \n");
int sum = maxSumPath(root);
printf ("\nSum of the nodes is %d ", sum);
getchar();
return 0;
}
#include<stdio.h>
#include<limits.h>
#define FALSE 0
#define TRUE 1
/* A tree node structure */
struct node
{
int data;
struct node *left;
struct node *right;
};
// A utility function that prints all nodes on the path from root to target_leaf
int printPath (struct node *root, struct node *target_leaf)
{
if(root==NULL)
return FALSE;
if (root == target_leaf || printPath(root->left, target_leaf) ||
printPath(root->right, target_leaf) )
{
printf("%d ", root->data);
return TRUE;
}
return FALSE;
}
// This function Sets the target_leaf_ref to refer the leaf node of the maximum
// path sum. Also, returns the max_sum using max_sum_ref
void getTargetLeaf (struct node *node, int *max_sum_ref, int curr_sum,
struct node **target_leaf_ref)
{
if(node == NULL)
return ;
curr_sum = curr_sum + node->data;
if(node->left==NULL && node->right==NULL)
if(curr_sum < *max_sum_ref){
*max_sum_ref = curr_sum;
*target_leaf_ref = node;
}
getTargetLeaf(node->left,max_sum_ref,curr_sum,target_leaf_ref);
getTargetLeaf(node->right,max_sum_ref,curr_sum,target_leaf_ref);
}
// Returns the maximum sum and prints the nodes on max sum path
int maxSumPath (struct node *node)
{
if (node == NULL)
return 0;
struct node *smallest_path;
int min_path = INT_MAX;
getTargetLeaf(node,&min_path,0,&smallest_path);
printPath(node,smallest_path);
return min_path;
// base case
}
/* Utility function to create a new Binary Tree node */
struct node* newNode (int data)
{
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
/* Driver function to test above functions */
int main()
{
struct node *root = NULL;
/* Constructing tree given in the above figure */
root = newNode(10);
root->left = newNode(-2);
root->right = newNode(7);
root->left->left = newNode(8);
root->left->right = newNode(-4);
printf ("Following are the nodes on the maximum sum path \n");
int sum = maxSumPath(root);
printf ("\nSum of the nodes is %d ", sum);
getchar();
return 0;
}
What if there are two paths with same hight ? , I think this could be solved recursivelly but I'm pretty sure it would be more efficient by using a queue instead of an stack, since you are looking for the min height you could traverse the tree using Breadth-first. and break , this means to keep track on path
public static void findMin(Node r, String path, Integer weight, MinWeight minInt)
{
if(r == null) return;
path = path + "->" + r.data;
weight = weight + r.data;
if(r.left == null && r.right == null)
{
System.out.println(path + "->" + weight);
minInt.weight = weight < minInt.weight ? weight : minInt.weight;
}
findMin(r.left, path, weight, minInt);
findMin(r.right, path, weight, minInt);
}
public void smallestPathOfAll() {
List<List<Integer>> list = new ArrayList<List<Integer>>();
_allPaths(root, 0, 0, list, new ArrayList<Integer>());
//now compute sum of all paths and find min sum
List<Integer> minpath = null;
int minsum = Integer.MAX_VALUE;
for (List<Integer> ll : list) {
int sum = 0;
for (Integer data : ll) {
sum += data;
}
if (sum < minsum) {
minsum = sum;
minpath = ll;
}
}
String appendix = "";
for (Integer data : minpath) {
System.out.print(appendix + data);
appendix = "->";
}
System.out.println("===" + minsum);
}
private void _allPaths(TreeNode node, int pathLocation,
int pathsize, List<List<Integer>> list,
List<Integer> tmplist) {
if (node == null) {
return;
}
tmplist.add(pathLocation, node.data);
pathsize++;
if (node.left == null && node.right == null) {
fillPath(pathsize, list, tmplist);
pathsize--;
}
_allPaths(node.left, pathLocation + 1, pathsize, list, tmplist);
_allPaths(node.right, pathLocation + 1, pathsize, list, tmplist);
}
apologies @ EPavlova its just a typo the code actually prints the min path and min value,
#include<stdio.h> #include<limits.h> #define FALSE 0 #define TRUE 1 /* A tree node structure */ struct node { int data; struct node *left; struct node *right; }; // A utility function that prints all nodes on the path from root to target_leaf int printPath (struct node *root, struct node *target_leaf) { if(root==NULL) return FALSE; if (root == target_leaf || printPath(root->left, target_leaf) || printPath(root->right, target_leaf) ) { printf("%d ", root->data); return TRUE; } return FALSE; } // This function Sets the target_leaf_ref to refer the leaf node of the minimum // path sum. Also, returns the minimum sum using min_sum_ref void getTargetLeaf (struct node *node, int *min_sum_ref, int curr_sum, struct node **target_leaf_ref) { if(node == NULL) return ; curr_sum = curr_sum + node->data; if(node->left==NULL && node->right==NULL) if(curr_sum < *min_sum_ref){ *min_sum_ref = curr_sum; *target_leaf_ref = node; } getTargetLeaf(node->left,min_sum_ref,curr_sum,target_leaf_ref); getTargetLeaf(node->right,min_sum_ref,curr_sum,target_leaf_ref); } // Returns the mininmun sum and prints the nodes on max sum path int minSumPath (struct node *node) { if (node == NULL) return 0; struct node *smallest_path; int min_path = INT_MAX; getTargetLeaf(node,&min_path,0,&smallest_path); printPath(node,smallest_path); return min_path; // base case } /* Utility function to create a new Binary Tree node */ struct node* newNode (int data) { struct node *temp = (struct node*)malloc(sizeof(struct node)); temp->data = data; temp->left = NULL; temp->right = NULL; return temp; } /* Driver function to test above functions */ int main() { struct node *root = NULL; /* Constructing tree given in the above figure */ root = newNode(10); root->left = newNode(-2); root->right = newNode(7); root->left->left = newNode(8); root->left->right = newNode(-4); printf ("Following are the nodes on the minimum sum path \n"); int sum = minSumPath(root); printf ("\nSum of the nodes is %d ", sum); getchar(); return 0; }explanation :-
- saurabh March 14, 2016the function minSumPath starts from root and explore each branch of the tree leading to a leaf node
i.e
10
/ \
-2 7
/ \
8 -4
for above three it will go like this
step 1 )
10+(-2)+(8) = 16 and the root now points to 8
now root reaches leaf as 8 is a leaf node there will be a check whether curr_sum (here
16 ) is less than min_sum (INT_MAX) which stands true
*min_sum_ref = curr_sum;(i.e min_sum = 16)
*target_leaf_ref = node; (i.e target_leaf_ref points to 8 )
step 2)
step 1 is repeated for all the branches (i.e 10->(-2)->(-4),10->7)
at last the min_sum= 4 (i.e 10+(-2)+(-4))
and target_leaf_ref points to 4
step 3) printPath function checks whether root == target_leaf_ref no in this case so it recursively moves left and right once it becomes equal to 4 it starts printing backwards data
that is -4 -2 10
hence you print the path and the min_sum is returned as 4
--------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------
in case the explanation doesn't clicks you please let me know i won't mind giving one more try
kudo:)