CODEWITHSUNDEEP
algorithmtreebinary-tree
user1992592
user1992592

Reputation: 21

path with max sum in tree

Given a Binary tree with -ve and +ve value's. print all path's froom root to any node with max sum.do it in O(n). only one traversal of tree.

Efforts :) 1) http://www.geeksforgeeks.org/find-the-maximum-sum-path-in-a-binary-tree/ is entirely different problem .

2) O(n) + O(n) is not accepted .

my approach .

1)

i) find max sum possible . ii) traverse preorder keeping current path and sum . if(curr_sum == max_sum) print path.

2) i) find max sum possible . ii) traverse preorder keeping current path and sum . if(curr_sum == max_sum) print path. also save address of this node in a node array Arr. next time when curr_sum==max_sum just check in Arr[] if path is already printed

problem : this will print some paths multiple time's . more over interviewer wanted one traversal . this takes 2. one to find max sum . other to print paths.

Upvotes: 0

Views: 4403

Answers (1)

Philip
Philip

Reputation: 5917

Do a Depth-First-Search on the tree, computing sums for all sub-paths and store them in a sorted array of lists containing sub-paths of equal length. It's easy to see that this can be done in O(n), traversing the graph exactly once.

The result is an array a where a[i] contains a list of paths of length i. Keep record of the largest index j and eventually print all paths in the list a[j].

Upvotes: 2

Related Questions