[AMAZON]Find two nodes which sums equal to 'K'
Given a binary search tree of n nodes, find two nodes whose sum is equal to a given number k in O(n) time and constant space.
Given an integer n, write a function that returns count of trailing zeroes in n!. Examples: Input: n = 5 Output: 1 Factorial of 5 is 20 which has one trailing 0. Input: n = 20 Output: 4 Factorial of 20 is 2432902008176640000 which has 4 trailing zeroes. Input: n = 100 Output: 24
It can be converted to the array sum problem.
ReplyDeleteDo simultaneous inorder and reverse-inorder traversal on the bst.
at any point,
while( inorder_element!= reverse_inorder_element)
{
if( elment_inorder + element_reverse_inorder = k ) print & return;
else if( sum > k ) move to next element in reverse inorder traversal
else if( sum < k ) move to next element in inorder traversal.
}
return NULL;
Time Complexity = O(n)
Space Complexity = O(n) , due to inorder recursion stack
Please check.
Here is the code.It involves iterative inorder traversal using STL Stack.
ReplyDeletehttp://codepad.org/CRssSfjg
@naveen yes your logic is correct and working but you are using extra space and complexity is o(n) which is fine.I would suggest convert ur BST to doubly linked list which is o(n), o(1) space , find the pair of number (again single traversal) and convert it back to BST(again o(n) and o(1) space)..
ReplyDeleteThanx Sir,
ReplyDeleteI thought of the BST to DLL conversion logic,but it is changing the tree structure.If the tree is read-only ,we can't use it.