Re: [algogeeks] Re: MS Question - Median of a BST without using extra space and in O(n)
*@all to median of BST time O(n) space O(1) (modified code of nitin to get median) medianBST*(node, n) int x = 0; *while* hasleftchild(node) *do* node = node.left *do* x++; if (x == n/2) return node-val; *if* (hasrightchild(node)) *then* node = node.right *while* hasleftchild(node) *do* node = node.left *else* *while* node.parent ≠ *null* *and* node == node.parent.right *do* node = node.parent node = node.parent *while* node ≠ *null* @dheeraj u U can get the number of elements by just traversing the who tree by above method -- 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] Re: MS Question - Median of a BST without using extra space and in O(n)
And you have to use the pointer-reversing trick to traverse the tree because you don't have space for a stack. On Sep 27, 4:52 am, anshu mishra anshumishra6...@gmail.com 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.
[algogeeks] Re: MS Question - Median of a BST without using extra space and in O(n)
This requires O(n) extra space.
On Sep 27, 7:43 am, anshu mishra anshumishra6...@gmail.com wrote:
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] Re: MS Question - Median of a BST without using extra space and in O(n)
its not o(n) it is O(max height of tree) :P i have not seen the constraint. -- 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] Re: MS Question - Median of a BST without using extra space and in O(n)
a simple one is rabit-tortoise method, and using stackless traversal, facing a lot of corner cases in coding this, can someone check this as well? On Sep 27, 6:41 pm, anshu mishra anshumishra6...@gmail.com wrote: its not o(n) it is O(max height of tree) :P i have not seen the constraint. -- 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] Re: MS Question - Median of a BST without using extra space and in O(n)
@anshu can middle element can be found if the no. of nodes are not given... On Tue, Sep 27, 2011 at 8:34 PM, vikas vikas.rastogi2...@gmail.com wrote: a simple one is rabit-tortoise method, and using stackless traversal, facing a lot of corner cases in coding this, can someone check this as well? On Sep 27, 6:41 pm, anshu mishra anshumishra6...@gmail.com wrote: its not o(n) it is O(max height of tree) :P i have not seen the constraint. -- 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* -- 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] Re: MS Question - Median of a BST without using extra space and in O(n)
Recursion also requires space, so the problem is how to traverse without extra space. Once this is done, nothing is left in the problem. Sanju :) On Tue, Sep 27, 2011 at 8:35 AM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: @anshu can middle element can be found if the no. of nodes are not given... On Tue, Sep 27, 2011 at 8:34 PM, vikas vikas.rastogi2...@gmail.comwrote: a simple one is rabit-tortoise method, and using stackless traversal, facing a lot of corner cases in coding this, can someone check this as well? On Sep 27, 6:41 pm, anshu mishra anshumishra6...@gmail.com wrote: its not o(n) it is O(max height of tree) :P i have not seen the constraint. -- 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* -- 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] Re: MS Question - Median of a BST without using extra space and in O(n)
Do inorder traversal, to find out the total no. of nodes. Next time, do the inorder traversal but keeping the count of nodes visited and stop when you visit n/2 nodes. Non recursive In-order Traversal - *inorder*(node) *while* hasleftchild(node) *do* node = node.left *do* visit(node) *if* (hasrightchild(node)) *then* node = node.right *while* hasleftchild(node) *do* node = node.left *else* *while* node.parent ≠ *null* *and* node == node.parent.right *do* node = node.parent node = node.parent *while* node ≠ *null* Source: Wikipedia On Tue, Sep 27, 2011 at 9:13 PM, Sanjay Rajpal srn...@gmail.com wrote: Recursion also requires space, so the problem is how to traverse without extra space. Once this is done, nothing is left in the problem. Sanju :) On Tue, Sep 27, 2011 at 8:35 AM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: @anshu can middle element can be found if the no. of nodes are not given... On Tue, Sep 27, 2011 at 8:34 PM, vikas vikas.rastogi2...@gmail.comwrote: a simple one is rabit-tortoise method, and using stackless traversal, facing a lot of corner cases in coding this, can someone check this as well? On Sep 27, 6:41 pm, anshu mishra anshumishra6...@gmail.com wrote: its not o(n) it is O(max height of tree) :P i have not seen the constraint. -- 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* -- 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. -- Nitin Garg Personality can open doors, but only Character can keep them open -- 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] Re: MS Question - Median of a BST without using extra space and in O(n)
Since we are given pointer to root node, we can easily find the minimum element in the tree. This will be the first node in the inorder traversal, now use method to find the inorder successor of a each node. Do it iteratively. Complexity will be O(n log n) and O(n) if tree is skewed. Correct me if m wrong. Sanju :) On Tue, Sep 27, 2011 at 8:49 AM, Nitin Garg nitin.garg.i...@gmail.comwrote: Do inorder traversal, to find out the total no. of nodes. Next time, do the inorder traversal but keeping the count of nodes visited and stop when you visit n/2 nodes. Non recursive In-order Traversal - *inorder*(node) *while* hasleftchild(node) *do* node = node.left *do* visit(node) *if* (hasrightchild(node)) *then* node = node.right *while* hasleftchild(node) *do* node = node.left *else* *while* node.parent ≠ *null* *and* node == node.parent.right *do* node = node.parent node = node.parent *while* node ≠ *null* Source: Wikipedia On Tue, Sep 27, 2011 at 9:13 PM, Sanjay Rajpal srn...@gmail.com wrote: Recursion also requires space, so the problem is how to traverse without extra space. Once this is done, nothing is left in the problem. Sanju :) On Tue, Sep 27, 2011 at 8:35 AM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: @anshu can middle element can be found if the no. of nodes are not given... On Tue, Sep 27, 2011 at 8:34 PM, vikas vikas.rastogi2...@gmail.comwrote: a simple one is rabit-tortoise method, and using stackless traversal, facing a lot of corner cases in coding this, can someone check this as well? On Sep 27, 6:41 pm, anshu mishra anshumishra6...@gmail.com wrote: its not o(n) it is O(max height of tree) :P i have not seen the constraint. -- 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* -- 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. -- Nitin Garg Personality can open doors, but only Character can keep them open -- 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.
[algogeeks] Re: MS Question - Median of a BST without using extra space and in O(n)
morris Inorder traversal can do the task i think -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/TujHItNRKowJ. 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.
