[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.
[AMAZON] Vertical sum of nodes
Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines. Examples: 1 / \ 2 3 / \ / \ 4 5 6 7 The tree has 5 vertical lines Vertical-Line-1 has only one node 4 => vertical sum is 4 Vertical-Line-2: has only one node 2=> vertical sum is 2 Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12 Vertical-Line-4: has only one node 3 => vertical sum is 3 Vertical-Line-5: has only one node 7 => vertical sum is 7 So expected output is 4, 2, 12, 3 and 7
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.