It can be converted to the array sum problem. Do 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.
@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)..
Implement a function getbits, that returns the(right adjusted) n bits that begin at position p of an integer. Assume bit position 0 is at the right end and that n and p are sensible positive values.
You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.
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.