*@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
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
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,
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
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.
--
@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
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
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*
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
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
10 matches
Mail list logo
