Re: [algogeeks] MS Question -> Median of a BST without using extra space and in O(n)
convert bst to doubly linked list inorder and find middle element using slow and fast pointer concept On Tue, Sep 27, 2011 at 2:18 PM, Ankur Garg wrote: > I was thinking of making the tree balanced with equal no of nodes in left > and right subtree > > Median will be root in this case > > > Regards > Ankur > > -- > 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.
Re: [algogeeks] MS Question -> Median of a BST without using extra space and in O(n)
int bstMedian(node *root, int n, int &x)
{
if (node->left) return bstMedian(root->left, n, x);
x++;
if (x == n/2) return node->val;
if (node->right) return bstMedian(root->right, n, x);
}
call bstMedian(root, n, 0);
--
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.
Re: [algogeeks] MS Question -> Median of a BST without using extra space and in O(n)
keep a global pointer and a global variable "check=0" do inorder traversal..instead of printing the value do if(check==0) save pointer check==1 else check==0; correct me if m wrong On Tue, Sep 27, 2011 at 2:22 PM, anshu mishra wrote: > do the inorder traversal as soon as reached at n/2th element that will be > median. > > -- > 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. > -- *Dheeraj Sharma* Comp Engg. NIT Kurukshetra -- 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.
Re: [algogeeks] MS Question -> Median of a BST without using extra space and in O(n)
@Anshu Will u be using extra space to store ur nodes in traversal ? On Tue, Sep 27, 2011 at 2:22 PM, anshu mishra wrote: > do the inorder traversal as soon as reached at n/2th element that will be > median. > > -- > 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.
Re: [algogeeks] MS Question -> Median of a BST without using extra space and in O(n)
do the inorder traversal as soon as reached at n/2th element that will be median. -- 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.
[algogeeks] MS Question -> Median of a BST without using extra space and in O(n)
I was thinking of making the tree balanced with equal no of nodes in left and right subtree Median will be root in this case Regards Ankur -- 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.
