Please take a look at this solution: 1) Assumption : We know the number of node in the tree. if n is odd the median is (n+1)/2 else if n is even its avg of n/2 and (n+2)/2.
Know to find these nodes without recursion we can do the following: Find the minimum of the tree. i.e the Left most node of the tree. Once we find the minimum of the tree we find the successor of each node by incrementing a counter value. When this counter value is equal to (n+1)/2 then that would be the median of the tree. 2) We do not know the size of the tree or the number of nodes.Then we can modify the data structure to store the inorder index. Algorithm: Find the minimum of the tree. i.e the Left most node of the tree. Once we find the minimum of the tree we find the successor of each node and at each node we set the index and also keep the count of the total number of nodes in the tree. Once we parse the entire tree, we do a search on the tree to find the node whose inorder index value would be equal to (n+1)/2 if n is odd or n/2 and (n+2)/2 if n is even. 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. > > -- With Regards, Yashwanth Vempati -- 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.
