Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
My idea is similar to the Vincent above. You have to use the parent pointer to save the time complexity. The whole idea explains as followings:
1) when constructing the tree, each node saves these information:
value, left pointer, right pointer, and an additional parent pointer.
2) Use BFS trick to traversing the tree, and calculate the sum of path from root to current node. If the node:
a. has all child node(s) non-positive
b. has no child node
then store this node to the candidate array. (This is because that only these two types of node can be the maximum path.)
3. After the traverse, we found the maximum, then traverse the candidate array, and print the maximum path(s) following the parent link.
Note that the size of candidate array is smaller than N.
The total time complexity is O(N).
As we go from parent node to it's child node in binary tree, we send current path sum to all it's childern, we maintain two global variable one is max_sum and another is count, we set count to be zero and now start from root node, it send it's node value to it's childern, then add it with their value and send final sum to their childerns, whenever someone reaches to end(leaf node), it check weather it's sum is greater or equal or less, if equal then it increment count, if less, then do nothing, if greater then set count = 1 and max_sum to it's sum.
so after one tree trival we get both max_sum and count.
Now if we want to print the paths also then we do following
as we know how many max_sum path exist, Now we create that many arrays of integer element, each array have some unique Id, now we start again with the same procedure but with one difference, we send current sum to childern nodes, but we want something from them, what we want is a structure which contain a integer(which tells how many path having max_sum are having current node in comman) and id's of all arrays., once we get these data from all it;s childerns, then we print the node value in all those arrays, and return total sum and all array's id, which we get from both or one of it's childern. if we get zero as integer value from all childern then we return zero.
but ya here we visit all nodes on the tree 3 times, once when we find out max_count, and second time when we go forward to locate leaf node of all the paths whose sum is max_sum and thrid time when we return from all these leaf node to root node.
Every node in the tree has exactly one path. The trick here for best time complexity is to calculate the sum at each node as you're traversing. Preorder traversal seems like the best option. Here is a solution you can test out. This includes updates for all three of the requirements of the problem.
The time complexity of this algorithm is O(n). Required space will be equal to the size of the binary tree plus the size of each max path. The worst (and rare) case for space requirements would be if all nodes in the tree were equal to zero, as a linked list must be stored for every path.
public class Main {
public static class ListNode {
public int value;
public ListNode nextLink;
//Link constructor
public ListNode(int d1) {
value = d1;
}
//Print ListNodedata
public void printLink() {
System.out.print(value + " ");
}
}
public static class LinkedList {
private ListNode first;
//LinkedList constructor
public LinkedList() {
first = null;
}
//Returns true if list is empty
public boolean isEmpty() {
return first == null;
}
//Inserts a new ListNode at the first of the list
public void insert(int d1) {
ListNode link = new ListNode(d1);
link.nextLink = first;
first = link;
}
//Deletes the ListNode at the first of the list
public ListNode delete() {
ListNode temp = first;
first = first.nextLink;
return temp;
}
//Prints list data
public void printList() {
ListNode currentLink = first;
while(currentLink != null) {
if(currentLink.nextLink != null)
currentLink.printLink();
currentLink = currentLink.nextLink;
}
System.out.println("");
}
}
public static class TreeNode {
public TreeNode leftChild = null;
public TreeNode rightChild = null;
int mValue;
TreeNode(int v) {
mValue = v;
}
public int getValue() {
return mValue;
}
}
public static class BinaryTree {
public TreeNode root;
public int currentMax = 0;
public ArrayList<LinkedList> pathsToMax;
public BinaryTree(int rootValue) {
root = new TreeNode(rootValue);
/* Test case */
fillTestTree();
pathsToMax = new ArrayList<LinkedList>();
}
public void fillTestTree() {
root.leftChild = new TreeNode(4);
root.rightChild = new TreeNode(-1);
root.leftChild.leftChild = new TreeNode(1);
root.rightChild.leftChild = new TreeNode(5);
root.leftChild.rightChild = new TreeNode(0);
root.rightChild.rightChild = new TreeNode(6);
}
public LinkedList appendToNewList(LinkedList l, int value) {
LinkedList newList = new LinkedList();
ListNode currentLink = l.first;
while(currentLink != null) {
newList.insert(currentLink.value);
currentLink = currentLink.nextLink;
}
newList.insert(value);
return newList;
}
public void printPaths() {
System.out.println("Max paths are: ");
for(int i = 0; i < pathsToMax.size(); i++) {
pathsToMax.get(i).printList();
}
}
public void getMaxSum(TreeNode n, int currentSum, LinkedList l) {
//Visit current node
if(n == null) {
//throw...
}
int sumAtCurrentNode = n.getValue() + currentSum;
if(sumAtCurrentNode >= currentMax) {
if(sumAtCurrentNode > currentMax) {
pathsToMax = null;
pathsToMax = new ArrayList<LinkedList>();
}
currentMax = sumAtCurrentNode;
//Blow away our current set of paths due to the new max
pathsToMax.add(appendToNewList(l, n.getValue()));
}
//Traverse left
if(n.leftChild != null) {
getMaxSum(n.leftChild, sumAtCurrentNode, appendToNewList(l, n.leftChild.getValue()));
}
//Traverse right
if(n.rightChild != null) {
getMaxSum(n.rightChild, sumAtCurrentNode, appendToNewList(l, n.rightChild.getValue()));
}
}
}
public static void main(String[] args) {
//Test list and tree
BinaryTree btree = new BinaryTree(-1);
LinkedList l = new LinkedList();
btree.getMaxSum(btree.root, 0, btree.appendToNewList(l, -1));
btree.printPaths();
System.out.println("Max sum is: " + btree.currentMax);
}
}
You're right. I specified at the end to be sure to store away the path to the node with the maxSum and to be prepared to store multiple paths. You'd just pass a linked list (with a getTail() method) as you went through the traversal along with the currentSum. And you would need a way to distinguish two nodes that had the same value, so you would want to make sure that each node had a unique identifier. Either that, or you could just store an array of directions like "Left Right Right".
there are n nodes. so there can be n path's . how will you store all n path's in O(n).
you'll need to copy linked list [path] for both childs of a parent . ie. O(n)
in for every parent node . thus making it O(n^2)
The time complexity is O(n), which is what I believe the interviewer was asking for. I don't think it is possible to store all possible combinations of LinkedLists to each node with storage space of O(n). Consider the case where every node is equal to zero.
does this count as once? basically you are traversing the node and get back to it later. not sure whether this is what the author means.
This is a standard preorder traversal. Every node is visited exactly one time. When I say "visited", for this problem, I mean it is examined, the value of the path is calculated, and the currentMax is updated. This is, indeed, O(n) time complexity. If you're not convinced, drop my program in Eclipse and set a break at "int sumAtCurrentNode = n.getValue() + currentSum;". It will be hit n times.
I know it's preorder and supposed to be O(n). I'm just confused with why it specifies twice doesn't count as O(n). You know when you do recursive functions, you are storing the state in the stack so that you can get back to it later. you are not calculating the sum twice but technically you are visiting the same node more than once. I probably misunderstood the statement.
ArrayList path = new Arraylist();
StringBuffer a = new Stringbuffer();
int max = 0;
Maxsumpath(head,sum,i)
{
if(head == null) return null;
sum = sum+head.value;
path.add(head.value);
if(head.left == null && head.right == null)
{
if(max< sum)
{
max = sum;
s = append(i,false);
}
if(max == sum)
s = append(build,true);
}
maxsumpath(head.left,++i);
maxsumpath(head.right,++i);
return s;
}
append(i,flag)
{
if(!flag)
s ="";
for(int j =0;j<i;j++)
{
s= s+path.get(j);
}
}
Small correction
if(max< sum)
{
max = sum;
s = append(i,false);
}
if(max == sum)
s = append(i,true);
}
append function should take i as the input parameter
Since the question is for finding the max path, max path can be formed only when we traverse till the leaf node..
Correct if i am wrong
Here is solution of multiple path & single path.
char PATH[N];//N = (Number of Node in BT)X(Max Number of Leaf in BT)
int PATH_Len=0;
int path_cunt=0
int max_sum = 0;
void main()
{
char path[N];
int sum = 0, l = 0;
NODE *BT == CreateBT(4,6,1,3,9,20,56,88,21,22,15);
path[0]='R'; l=1;
MaxPath(BT, sum, path, l);//This will evalute one path.
printf("\nMax Sum: %d, PATH: %s", max_sum, PATH);
memset(PATH, 0, N);
path[0]='R'; l=1; max_sum=0; path_cunt=0;
Multi_MaxPath(BT, sum, path, l);//This will evalute multiple path of same max.
for(int i=0, int temp=0; i<path_cunt; i++){
int temp_l=strlen(PATH+temp);
printf("Max Sum: %d, PATH: %s", max_sum, PATH+temp);
temp += temp_l+1;
}
}
void MaxPath(NODE *Root, int sum, char path[], int l)
{
if(!Root) return;
sum += Root->info;
if(sum>max_sum){
strcpy(PATH, path, l);
max_sum = sum;
}
path[l] = 'L';
MaxPath(Root->Left, sum, path, l+1);
path[l] = 'R';
MaxPath(Root->Left, sum, path, l+1);
}
void Multi_MaxPath(NODE *Root, int sum, char path[], int l)
{
if(!Root) return;
sum += Root->info;
if(sum == max_sum){
PATH[PATH_Len] = '\0'; PATH_Len++;
strcpy(PATH+PATH_Len, path, l);//Appending multiple Path String
PATH_Len += l;
path_cunt++;
} else if(sum>max_sum){
strcpy(PATH, path, l);
max_sum = sum;
path_cunt=1;
PATH_Len=l;
}
path[l] = 'L';
MaxPath(Root->Left, sum, path, l+1);
path[l] = 'R';
MaxPath(Root->Left, sum, path, l+1);
}
T(N) = O(N)
S(N) = (Number of Node in BT)X(Max Number of Leaf in BT)
.
some issues :
1) you can traverse tree only once .
2) you'll print some path's multiple time .[paths which don't end at leaf . u'll print them for both child branches ].
3) you are not supposed to print 'L' 'R' array. [as u are consedering strcpy() O(1) . which is actually O(n) ]
making your algo O(n^2).
how about my code with c++ ,and i think i can print well the path .
I use a vector to store the path
int max_sum = 0;
vector< vector<int> > max_sum_path;
void getMaxSum(struct node *head , int curr_sum ,vector<int> &path)
{
curr_sum += head->x;
if(curr_sum > max_sum){
max_sum = curr_sum;
max_sum_path.erase(max_sum_path.begin() , max_sum_path.end());
}
if(head->l ){
path.push_back(1);// 1 :left 2 :rigth
getMaxSum(head->l , curr_sum , path);
path.pop_back();
}
if(head->r ){
path.push_back(2);// 1 :left 2 :rigth
getMaxSum(head->r , curr_sum , path);
path.pop_back();
}
if(curr_sum == max_sum){
max_sum_path.push_back(path);
}
}
My solution:
import java.util.ArrayList;
import java.util.List;
public class MaxPathTree {
public static void main(String[] args) {
TreeItem root = init();
List<MaxPath> result = findMaxPath(root);
System.out.println(result);
}
private static List<MaxPath> findMaxPath(TreeItem root) {
int max = 0;
List<MaxPath> maxPaths = new ArrayList<>();
if (root.left != null) {
List<MaxPath> leftPaths = findMaxPath(root.left);
for (MaxPath maxPath : leftPaths) {
if (maxPath.sum > max) {
maxPaths.clear();
maxPaths.add(maxPath);
max = maxPath.sum;
} else if (maxPath.sum == max) {
maxPaths.add(maxPath);
}
}
}
if (root.right != null) {
List<MaxPath> rightPaths = findMaxPath(root.right);
for (MaxPath maxPath : rightPaths) {
if (maxPath.sum > max) {
maxPaths.clear();
maxPaths.add(maxPath);
max = maxPath.sum;
} else if (maxPath.sum == max) {
maxPaths.add(maxPath);
}
}
}
if (maxPaths.size() == 0) {
MaxPath maxPath = new MaxPath();
maxPaths.add(maxPath);
}
for (MaxPath maxPath : maxPaths) {
maxPath.sum += root.value;
maxPath.path.add(root);
}
return maxPaths;
}
private static TreeItem init() {
TreeItem A = new TreeItem("A", 1);
TreeItem B = new TreeItem("B", 2);
TreeItem C = new TreeItem("C", 3);
TreeItem D = new TreeItem("D", 4);
TreeItem E = new TreeItem("E", 5);
TreeItem F = new TreeItem("F", 6);
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.right = F;
return A;
}
public static class MaxPath {
public int sum;
public List<TreeItem> path = new ArrayList<>();
}
public static class TreeItem {
public TreeItem left;
public TreeItem right;
public int value;
public String id;
public TreeItem(String id, int value) {
this.id = id;
this.value = value;
}
@Override
public String toString() {
return id;
}
}
}
void printList(int arr[], int len, int *maxSum)
{
int i, sum=0;
for(i=0;i<len;i++)
{
sum+=arr[i];
fprintf(stderr,"%d ",arr[i]);
}
if(sum>*maxSum)
*maxSum = sum;
fprintf(stderr,"\n");
}
allThePaths(struct node *root, int *path, int pathLen, int *maxSum)
{
if(root == NULL)
return;
path[pathLen] = root->data;
pathLen++;
if((!(root->left)) && (!(root->right)))
printList(path,pathLen,maxSum);
else
{
allThePaths(root->left, path,pathLen, maxSum);
allThePaths(root->right, path,pathLen, maxSum);
}
}
allThePaths(struct node *root, int *path, int pathLen, int *maxSum)
Here *path is actually pointer to array passed from main function.
Do let me know if there is anything wrong or to improve with the code.
@drv
please read problem statement again . your solution is not doing what is needed.
this is an entirely different problem. do not get confused.
<http://www.geeksforgeeks.org/find-the-maximum-sum-path-in-a-binary-tree/>
1) Find path from root to any node with max sum.
==>This is stored in maxSum passed from main.
2) As there can be many path's find all of them.
==>Traversing all paths are printed..
3) Print all such paths
==> Printing all the paths.
What else ?
public static ArrayList<linkedlist> printTheMaxSumPathOfBinaryTree(treeNode root){
- sl2574@cornell.edu January 27, 2013if(root == null) return null;
ArrayList<linkedlist> l = printTheMaxSumPathOfBinaryTree(root.left);
ArrayList<linkedlist> r = printTheMaxSumPathOfBinaryTree(root.right);
if(l == null && r == null) {
linkedlist n = new linkedlist();
n.appendToTheFront(root.data);
ArrayList<linkedlist> arr = new ArrayList<linkedlist>();
arr.add(n);
return arr;
}else if(l == null && r != null){
for(int i=0;i<r.size();i++){
r.get(i).appendToTheFront(root.data);
}
return r;
}else if(l != null && r == null){
for(int i=0;i<l.size();i++){
l.get(i).appendToTheFront(root.data);
}
return l;
}else{
if(l.get(0).sum > r.get(0).sum) {
for(int i=0;i<l.size();i++){
l.get(i).appendToTheFront(root.data);
}
return l;
}else if(l.get(0).sum < r.get(0).sum){
for(int i=0;i<r.size();i++){
r.get(i).appendToTheFront(root.data);
}
return r;
}else{
for(int i=0;i<l.size();i++){
l.get(i).appendToTheFront(root.data);
}
for(int i=0;i<r.size();i++){
r.get(i).appendToTheFront(root.data);
}
l.addAll(r);
return l;
}
}