HI
Do an inorder traversal on that bst n form a sorted array...then u can
search for that 2 elements in O(n)
On Mon, Jun 27, 2011 at 2:01 PM, manish kapur manishkapur.n...@gmail.comwrote:
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
do inorder traversal of tree and store values in an array.
Now find pairs by applying binary search on array..
On 6/27/11, manish kapur manishkapur.n...@gmail.com wrote:
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
@Bharath : Cud u plz explain how r u searching the elements in O(n) time?
Because if we use binary search, it will have O(n*log n ) worst case
time complexity. One way in which I think it cud be made O(n) is that
we can use a hash table, with a good hash function apart frm the
array. And then for
(for array sorted in ascending order)
take 2 indexes i and j pointing to 1st and last element of the array
respectively...
now if(arr[i]+arr[j] == x)
print(arr[i]);
print(arr[j];
else if(arr[i]+arr[j]x)
j--;
else
i++;
I think this should work...(i've not checked)
correct me if i m wrong
On
@ankit: no need to use hash table for that.
simply run two pointers one from 0 and second from n - 1.
On Mon, Jun 27, 2011 at 2:51 PM, ankit sambyal ankitsamb...@gmail.comwrote:
@Bharath : Cud u plz explain how r u searching the elements in O(n) time?
Because if we use binary search, it will
Instead of using an array...we can do this by converting the BST into a
doubly linked list...but this will definitely modify the BST..
On Mon, Jun 27, 2011 at 3:01 PM, varun pahwa varunpahwa2...@gmail.comwrote:
@ankit: no need to use hash table for that.
simply run two pointers one from 0 and
@varun: where does the algo stops?
when the two pointer crosses over or both of them reaches other
opposite end.
On Mon, Jun 27, 2011 at 3:04 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote:
Instead of using an array...we can do this by converting the BST into a
doubly linked
