@bittu: Can we modify the tree to store extra info?
On Mon, Mar 28, 2011 at 4:16 PM, bittu shashank7andr...@gmail.com wrote:
@all try to understand the question as usual we have to do it in min.
time space complexity ..in mean Time O(n) space o(1) At-most
just tell em after doing in-order
What exactly the median of a Binary Tree means?
On Mon, Mar 28, 2011 at 4:38 PM, Anurag Bhatia abhati...@gmail.com wrote:
@bittu: Can we modify the tree to store extra info?
On Mon, Mar 28, 2011 at 4:16 PM, bittu shashank7andr...@gmail.com wrote:
@all try to understand the question as
@all try to understand the question as usual we have to do it in min.
time space complexity ..in mean Time O(n) space o(1) At-most
just tell em after doing in-order traversal where u will store the
elements either in array or in set isn'tit it will take O(n) extra
space why not looks fro O(1)
median is defined for a sorted list of numbers.. i cannot understand how you
can traverse in O(n) in a normal binary tree.
@raunak plz explain the solution
On Mon, Mar 28, 2011 at 4:16 PM, bittu shashank7andr...@gmail.com wrote:
@all try to understand the question as usual we have to do it in
I am assuming that the median is the sum of all the values stored in the
nodes divided by 2.
So I am traversing all the nodes recursivelyand finding the median of
them.
On Mon, Mar 28, 2011 at 5:12 PM, kunal srivastav kunal.shrivas...@gmail.com
wrote:
median is defined for a sorted list
This is mean not the median
On Mon, Mar 28, 2011 at 8:42 PM, Raunak Agrawal raunak.ra...@gmail.comwrote:
I am assuming that the median is the sum of all the values stored in the
nodes divided by 2.
So I am traversing all the nodes recursivelyand finding the median of
them.
On Mon,
@all
wake up geeks
Thanks
Shashank
--
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
Hi,
This is one approach to it:
1) Go to the first node in inorder traversal. Let the pointer be LP.
(Push the intermediate nodes to Lstack while doing this )
2) Go to the last node in inorder traversal. Let the pointer be RP.
(Push the intermediate nodes to Rstack while doing this )
We can do it in a recursive manner:
public int getRecursiveMedian(Node node)
{
int leftMedian = 0;
int rightMedian = 0;
if(node.getLeft() != null)
{
leftMedian = getRecursiveMedian(node.getLeft());
}
if(node.getRight() != null)
{
rightMedian =
while(LP-data RP-data){
The condition is wrong and would work only for BST. We could probably change
it to
while(LP != RP Lprev != RP)
Thanks,
Balaji.
On Sun, Mar 27, 2011 at 8:03 PM, Balaji Ramani rbalaji.psgt...@gmail.comwrote:
Hi,
This is one approach to it:
1) Go to the first
You could do any order traversal to get the list of values. - O(n)
Apply the kth order statistic (where k = numNodes/2) to get the value - O(n)
Adjust the median depending on whether numNode is odd or even
On Sun, Mar 27, 2011 at 8:03 PM, Balaji Ramani
rbalaji.psgt...@gmail.com wrote:
Hi,
11 matches
Mail list logo