Can we do this ? We use one pointer 'a' to point to the root of the tree. An integer 'b'. Another pointer 'c' to perform inorder traversal and count the number of nodes. Calculate median which will be ceil(n/2). and using 'c' perform inorder traversal again, until we have scanned ceil(n/2) nodes. In total of 4 variables. So complexity is still O(n) and memory requirement is O(1).
On Mon, Mar 8, 2010 at 8:11 PM, Ralph Boland <[email protected]> wrote: > This can be done without the parent pointer though the method > may not be wise. As you traverse the tree downward you set > the child pointer you traverse to point to the parent (grandparent > of the child). When you > traverse upward you reset the pointer of the node you traverse > to point to its original child. Now no parent pointers are needed > and no recursion either. The catch is that if your code does > not complete for any reason the tree is cooked. > Charcoal anyone? > > On Mar 8, 5:37 am, Terence <[email protected]> wrote: > > 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]<algogeeks%[email protected]> > > > > > > <mailto:algogeeks%[email protected]<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]<algogeeks%[email protected]> > > > > > > <mailto:algogeeks%[email protected]<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]<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]. > To unsubscribe from this group, send email to > [email protected]<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]. 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.
