[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.

Comments

  1. 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.

    ReplyDelete
  2. Here is the code.It involves iterative inorder traversal using STL Stack.

    http://codepad.org/CRssSfjg

    ReplyDelete
  3. @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)..

    ReplyDelete
  4. Thanx Sir,
    I 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.

    ReplyDelete

Post a Comment

Popular posts from this blog