What is the storage structure of your BST?
If each node contains pointers to its left child, right child and
parent, then we can traverse through the tree without recursive or stack.
in_order_traverse()
{
p = root;
last = root->parent = NULL;
while(p) {
if (last == p->parent) { // enter
if(p->left) {
last = p; p = p->left;
} else if(p->right) {
process(p);
last = p; p = p->right;
} else {
process(p);
last = p; p = p->parent;
}
} else if (last == p->left) {
process(p);
if(p->right) {
last = p; p = p->right;
} else if(p->right) {
last = p; p = p->parent;
}
} else {
last = p; p = p->parent;
}
}
}
Combine this with Rahul Singh's algorithm lead to a solution with O(n)
time and O(1) memory
On 2010-3-8 15:11, Nikhil Agarwal wrote:
@all: you cannot traverse through the tree recursively because it has
been mentioned that no extra memory (in recursive calls or stack ) is
allowed.
On Mon, Mar 8, 2010 at 8:42 AM, gaurav gupta
<[email protected] <mailto:[email protected]>> wrote:
Median of BST means : median of Sorted array of elements? is it?
Convert BST into Hight Balance Search Tree then root node will be
your median.
On Sun, Mar 7, 2010 at 2:42 AM, Nik_nitdgp
<[email protected] <mailto:[email protected]>> wrote:
Given a BST (Binary search Tree) how will you find median in that?
Constraints:
-No extra memory.
Algorithm should be efficient in terms of complexity.
Write a solid secure code for it.
No extra memory--u cannot use stacks to avoid recursion.
No static,global--u cannot use recursion and keep track of the
elements visited so far in inorder.
--
You received this message because you are subscribed to the
Google Groups "Algorithm Geeks" group.
To post to this group, send email to
[email protected] <mailto:[email protected]>.
To unsubscribe from this group, send email to
[email protected]
<mailto:algogeeks%[email protected]>.
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 [email protected]
<mailto:[email protected]>.
To unsubscribe from this group, send email to
[email protected]
<mailto:algogeeks%[email protected]>.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks & Regards
Nikhil Agarwal
Junior Undergraduate
Computer Science & Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
