[algogeeks] Re: BST Problem
@arvind: had i knwn would hv posted it On Aug 23, 8:59 am, "R.ARAVINDH" wrote: > @giri: > > can u post d correct answer?? -- 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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST Problem
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?? > > -- > 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. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- 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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST Problem
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 answer??
>
> --
> 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.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
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.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST Problem
@giri: can u post d correct answer?? -- 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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST Problem
@giri: thnx frnd...sorry ppl . ignore my post :( -- 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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST Problem
frnd check ur code.. t contains much errors..
consider the following eg.:
k=5;3
1 4
2 5
On Aug 22, 2:30 pm, "R.ARAVINDH" wrote:
> can v do like this???
>
> findnodes(root,sum)
> {
> if(root==abs(sum-root->data))
> print (the data is root->data, sum-(root->data));
> else
> if(rootdata))
> findnodes(root->right,sum-root->data)
> else if(root>abs(sum-root->data))
> findnodes(root->left,sum-root->data)
> else if(root->left==NULL || root->right==NULL) print(root,sum-root);
>
>
>
> }
--
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.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST Problem
for the above post i have assumed that the two nodes whose sum is k is present in the BST... so correct me if m wrong -- 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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST Problem
can v do like this???
findnodes(root,sum)
{
if(root==abs(sum-root->data))
print (the data is root->data, sum-(root->data));
else
if(rootdata))
findnodes(root->right,sum-root->data)
else if(root>abs(sum-root->data))
findnodes(root->left,sum-root->data)
else if(root->left==NULL || root->right==NULL) print(root,sum-root);
}
--
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.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST Problem
@Sekin Yes that's true.. -- 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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST Problem
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 this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- 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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST Problem
@Sekin. Sort the elements (increasing order). This has already been mentioned. So, answer will be 1, 100. -- 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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST Problem
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 how implement your idea on a basic BST, I would like to hear it.
Thanks,
Seckin
On Fri, Aug 6, 2010 at 2:56 AM, sharad kumar wrote:
> do the inorder traversal of the bst ...this gives the sorted array..
> from that use
>
> int i=0,j=length(array)
> while(i {
> if(array[i]+array[j]>sum)
> --j;
> else if(array[i]+array[j] ++i;
> else if((array[i]+array[j])==sum)
> return i,j
> else
> ++i,--j;
> }
>
>
> On Fri, Aug 6, 2010 at 3:10 PM, Chonku wrote:
>
>> 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 <
>> manjunath.n...@gmail.com> wrote:
>>
>>> 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.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> 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.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> yezhu malai vaasa venkataramana Govinda Govinda
>
> --
> 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.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
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.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST Problem
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 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 < > manjunath.n...@gmail.com> wrote: > >> 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. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > 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. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- yezhu malai vaasa venkataramana Govinda Govinda -- 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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST Problem
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..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. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- 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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST Problem
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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST Problem
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 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;
>> while i > {
>> if a[i] > k, then output: "No such node"
>> else if(a[i]==k)
>> {
>>if (a[i+1] ==0)
>> output: "Two nodes found" BREAK;
>>else
>> output: "No such node." BREAK.
>>
>> }
>>
>> else if(a[i] > {
>> if(a[i]+a[i+1]==k)
>>output: "Two nodes found" BREAK.
>> else if(a[i]+a[i+1] >k)
>>output: "No such node" BREAK
>> else if(a[i] +a[i+1] < k)
>> i++ ;
>> }
>> }//End of while-loop.
>>
>> --
>> 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.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
--
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.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST Problem
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;
> while i {
> if a[i] > k, then output: "No such node"
> else if(a[i]==k)
> {
>if (a[i+1] ==0)
> output: "Two nodes found" BREAK;
>else
> output: "No such node." BREAK.
>
> }
>
> else if(a[i] {
> if(a[i]+a[i+1]==k)
>output: "Two nodes found" BREAK.
> else if(a[i]+a[i+1] >k)
>output: "No such node" BREAK
> else if(a[i] +a[i+1] < k)
> i++ ;
> }
> }//End of while-loop.
>
> --
> 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.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
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.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST Problem
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;
while i k, then output: "No such node"
else if(a[i]==k)
{
if (a[i+1] ==0)
output: "Two nodes found" BREAK;
else
output: "No such node." BREAK.
}
else if(a[i] k)
output: "No such node" BREAK
else if(a[i] +a[i+1] < k)
i++ ;
}
}//End of while-loop.
--
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.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
