@payal : what will be be the structure of the augmented tree , i add 2 to
the given input. so input become.
ar[]={3,5,1,6,7,8,2};
On Sun, Mar 11, 2012 at 11:07 PM, payal gupta <gpt.pa...@gmail.com> wrote:
> 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.
>
--
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.
