the algo vich i thought of is as follows-
struct node{
int data;
struct node *left,*right;
int lsum; //for storing the leftsum
int k; // for storing the storing the reqd sum which is leftsum + sum of
the elements traversed till now on the path
};
Algo for insertion of nodes in bst->
1. add the new node with data as the value ,lsum set to 0 and k set to 0
2.continue adding further nodes and update the value of 'k' by the data to
be added whenever value is added to theleft subtree of the node
3. on adding the node to the right of the root set the value of leftsum to
be summation of rootvalue+k of the nodes considered during traversal
(3,0,0)
\
(5,3+0,0)
(3,0,1)
/ \
(1,0,0) (5,3+0,0)
(3,0,1)
/ \
(1,0,0) (5,3+0,0)
\
(6,1+5+3,0)
(3,0,1)
/ \
(1,0,0) (5,3+0,0)
\
(6,1+5+3,0)
\
(7,1+5+3+6,0)
(3,0,1)
/ \
(1,0,0) (5,3+0,0)
\
(6,1+5+3,0)
\
(7,1+3+5+6,0)
\
(8,3+1+5+6+7,0)
where the node-(data,leftsum,k)
On Sun, Mar 11, 2012 at 7:06 PM, sanjiv yadav <sanjiv2009...@gmail.com>wrote:
> u r right payal but
> can u expln o(n) time complexity......
>
>
> On Sun, Mar 11, 2012 at 6:10 PM, payal gupta <gpt.pa...@gmail.com> wrote:
>
>> By Augmented BST-
>> TC-O(n)
>>
>>
>> On Sun, Mar 11, 2012 at 3:08 PM, Gaurav Popli <gpgaurav.n...@gmail.com>wrote:
>>
>>> given an array of size n...
>>> create an array of size n such that ai where ai is the element in the
>>> new array at index location i is equal to sum of all elements in
>>> original array which are smaller than element at posn i...
>>>
>>> e.g
>>> ar[]={3,5,1,6,7,8};
>>>
>>> ar1[]={0,3,0,9,15,22};
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@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 algogeeks@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.
>>
>
>
>
> --
> Regards....
>
> Sanjiv Yadav
>
> MobNo.- 8050142693
>
> Email Id- sanjiv2009...@gmail.com
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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 algogeeks@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.
