CareerCup

public static ArrayList<linkedlist> printTheMaxSumPathOfBinaryTree(treeNode root){

if(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;
}
}

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.

You can use BFS in order to solve this problem.

traverse just once? does recursive solution count as once?

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);
	}
}

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);
}

}

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)

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);
    }
}

This problem can be solved by using parent pointer.

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);
	}
}