*@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
*whil
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 algogeek
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
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)
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 wrote:
> @anshu
> can middle element can be found if the no. of nodes are not given...
>
>
> On Tue
@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 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 p
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 wrote:
> its not o(n) it is O(max height of tree) :P
> i have not seen the constraint.
--
You received this message
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
algoge
This requires O(n) extra space.
On Sep 27, 7:43 am, anshu mishra 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 b
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 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
10 matches
Mail list logo
