I am not sure if I am repeating the answer:
The problem will reduce to find the pair of elements which will sum up to a
particular number. Then read the below article,
http://www.rawkam.com/?p=345
On Mon, Aug 23, 2010 at 9:29 AM, R.ARAVINDH wrote:
> @giri:
>
> can u post d correct answer??
>
Perform inorder traversal and store in an array.
low = 0, high = size-1
while(low<=high)
{
if ( a[low] + a[high] < sum)
low++;
else if (a[low] + a[high] > sum)
high--;
else
return a[high] and [low]
}
On Mon, Aug 23, 2010 at 9:29 AM, R.ARAVINDH wrote:
> @giri:
>
> can u post d correct
Avik, yes the answer is obvious but your code doesn't find that.
that 2 pointer approach is the correct one.
On Tue, Aug 10, 2010 at 12:07 AM, Avik Mitra wrote:
> @Sekin.
>
> Sort the elements (increasing order). This has already been mentioned.
> So, answer will be 1, 100.
>
> --
> You received
Chonku, you can do that only when you have the links to parent nodes. I
couldn't come up with a way of doing what you said on a basic BST(nodes
having pointers only to their 2 children) that is why I suggested using an
array. It doesn't change the overall complexity but if you have an idea
about ho
do the inorder traversal of the bst ...this gives the sorted array..
from that use
int i=0,j=length(array)
while(isum)
--j;
else if(array[i]+array[j] wrote:
> Two inorders would achieve the same thing without using an array. One
> pointer running inorder with LDR and other pointer running ino
Two inorders would achieve the same thing without using an array. One
pointer running inorder with LDR and other pointer running inorder with RDL.
Compare the sum at the two nodes and then adjust them accordingly.
On Fri, Aug 6, 2010 at 2:11 PM, Manjunath Manohar
wrote:
> the solution elegant..bu
the solution elegant..but is there any on the fly method by just exploiting
the BST propertyby using left and right pointers
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
as a hint, convert the BST to a sorted array and take two pointers one
pointing to the first number and the other pointing to the last. Then, move
pointers appropriately to find the two numbers summing up to k.
complexity: O(n)
2010/8/5 Seçkin Can Şahin
> what about the case:
> array : 1 3 10 1
what about the case:
array : 1 3 10 100 and k = 101. Your code doesn't find it I suppose.
On Thu, Aug 5, 2010 at 11:15 PM, Avik Mitra wrote:
>
> Inorder traversal of the BST will give elements in sorted way. Let us
> assume that the sorted elements are in an array A of length N.
> set i=1;
> whi