Find the Least Length Path Which Sums to S
Given a BST and a number 'N' there can be several paths from root of the bst to leaves such that sum of data of all the nodes will make number 'N'. Suggest an efficient algorithm to find out the path of least length.
//Assumption - path always starts from root.
ReplyDeleteOne stack for inorder traversal and other one for storing path .
Use iterative Inorder DFS traversal on BST where the size of stack denotes the path length at any time and store the cumulative sum found till now.
if (sum_found == N and cur_path_len < prev_path_len)
store the path and path_length in path stack.
Other optimization can be - don't store the complete path , just store the last node of the path.We can trace back from root since it is a BST.
Time->O(n)
Stack space->O(n)in case of skewed BST else O(lg n)
Please check.
@naveen first thing no need to use two stacks and here you are not using any property of BST while looking for the path..you can simply use reverse preorder to find the path and the first path that you will find will be the shortest one, because you are traversing on the nodes with larger value first.please figure it out with an example..
ReplyDelete@Admin
ReplyDeleteIn reverse pre-order,we visit the right subtree,then left subtree then root.
Will then be the path contiguous.I can't get it.Please explain ur approach a little more.
In my 2nd optimized approach -> i m using only one stack.Just for inorder traversal.
We can use reverse inorder also to get the smallest path sooner.