Can we do this ?
We use one pointer 'a' to point to the root of the tree.
An integer 'b'.
Another pointer 'c' to perform inorder traversal and count the number of
nodes. Calculate median which will be ceil(n/2). and using 'c' perform
inorder traversal again, until we have scanned ceil(n/2) nodes.
Please take a look at this solution:
1) Assumption : We know the number of node in the tree.
if n is odd the median is (n+1)/2 else if n is even its avg of n/2 and
(n+2)/2.
Know to find these nodes without recursion we can do the following:
Find the minimum of the tree. i.e the Left most node of t
Check the blog
http://ds-gyan.blogspot.com/2009/12/median-of-stream-of-numbers.html
You can form similar tree with node having count of left elements.
On Mar 8, 5:45 pm, Rohit Saraf wrote:
> once u do that.. the solution is trivial :P
> -Rohit
>
> On Mon, Mar 8, 2010 at 5:54 PM, Nikhil Agarwal
This can be done without the parent pointer though the method
may not be wise. As you traverse the tree downward you set
the child pointer you traverse to point to the parent (grandparent
of the child). When you
traverse upward you reset the pointer of the node you traverse
to point to its origin
With only these 2 constraints you can just insert the root of smaller tree
into bigger one and using rotations bring it to leaf.
Now attach the left and right subtrees to the inserted node.
Expected O(log n) Worst O(n)
Space O(1)
-Rohit
On Mon, Mar 8, 2010 at 5:14 AM, lalit gera wrote:
> new t
once u do that.. the solution is trivial :P
-Rohit
On Mon, Mar 8, 2010 at 5:54 PM, Nikhil Agarwal wrote:
>
>
> On Mon, Mar 8, 2010 at 5:04 PM, Rohit Saraf
> wrote:
>
>> can we assume that we have the sizes of subtree rooted at all nodes in our
>> datastructure.?
>>
>
> Yeah,that can be lead to
What is the storage structure of your BST?
If each node contains pointers to its left child, right child and
parent, then we can traverse through the tree without recursive or stack.
in_order_traverse()
{
p = root;
last = root->parent = NULL;
while(p) {
if (last == p->parent) { //
On Mon, Mar 8, 2010 at 5:04 PM, Rohit Saraf wrote:
> can we assume that we have the sizes of subtree rooted at all nodes in our
> datastructure.?
>
Yeah,that can be lead to 1 solution.well done.
>
> -Rohit
>
>
>
> On Mon, Mar 8, 2010 at 5:02 PM, sharad kumar wrote:
>
>> @gaurav :ur sol u mean l
I think you surely can modify the data structure
On 8 March 2010 17:04, Rohit Saraf wrote:
> can we assume that we have the sizes of subtree rooted at all nodes in our
> datastructure.?
>
> -Rohit
>
>
>
> On Mon, Mar 8, 2010 at 5:02 PM, sharad kumar wrote:
>
>> @gaurav :ur sol u mean like tk the
can we assume that we have the sizes of subtree rooted at all nodes in our
datastructure.?
-Rohit
On Mon, Mar 8, 2010 at 5:02 PM, sharad kumar wrote:
> @gaurav :ur sol u mean like tk the mem loc for each node and make it as
> array ?
>
> On Mon, Mar 8, 2010 at 8:42 AM, gaurav gupta
> <1989.gau
@gaurav :ur sol u mean like tk the mem loc for each node and make it as
array ?
On Mon, Mar 8, 2010 at 8:42 AM, gaurav gupta <1989.gau...@googlemail.com>wrote:
> Median of BST means : median of Sorted array of elements? is it?
>
> Convert BST into Hight Balance Search Tree then root node will be
@all: you cannot traverse through the tree recursively because it has been
mentioned that no extra memory (in recursive calls or stack ) is allowed.
On Mon, Mar 8, 2010 at 8:42 AM, gaurav gupta <1989.gau...@googlemail.com>wrote:
> Median of BST means : median of Sorted array of elements? is it?
>
number of solution to the equation
x1+x2+x3...xk=N where (x1>=1,x2>=1,...xk>=1)
On Mon, Mar 8, 2010 at 11:54 AM, Anurag Bhatia wrote:
> @Rohit: Can you explain the solution? I was unable to understand why
> the (n-1) and (k-1) instead of just n and k.
>
> Thanks and regards,
> Anurag Bhatia
what you are telling will be the median of link list. not the median of
tree. but previous solution told by Gaurav Gupta fails because we don't
have to use the extra memory and for getting height. and balancing we have
to use recurssion.
i think the question asked is correct or not.. Are u miss
14 matches
Mail list logo
