Another approach is to form a singly linked, NULL-terminated list (connected e.g. by 'left' pointers). This is a harder problem, and it might be required if you have a purpose for the other (right) pointer. If you need a doubly linked list it's easy to walk down the singly linked one, creating 'previous' pointers as you go. The converter accepts both a tree and list that's already in the correct order, which should be appended at the end of the converted tree. The result of the append operation should be returned.
NODE *convert(NODE *root, NODE *list) { if (root == NULL) return list; NODE *left_subtree = root->left; root->left = convert(root->right, list); return tree(left_subtree, root); } I like this solution because it's so simple. Initiate it with convert(tree, NULL); If you really need the double links: void adjust(NODE *head) { NODE *p, *q; for (q = NULL, p = head; p; q = p, p = p->next) p->right = q; head->right = q; q->right = head; } On May 26, 3:07 am, jalaj jaiswal <jalaj.jaiswa...@gmail.com> wrote: > Both the explanations above are wrong . It is true that BST can be > converted to a Doubly linked list by doing inorder traversal. > > But the approach mentioned in the stanford link follows a postorder > Approach , it is better because it avoids useage of a static/global > variable which is required in inorder Approach. > "recursively changing the small and large sub-trees into lists, and then > append those lists together with the parent node to make larger lists" - > quoted from the stanford page. (parent is visited after the subtrees) > > Explanation of the postorder Approach :- > > refer to the drawing in the page. > FIrst of all it makes the node named 1 as a an independent node after that > as in postorder it makes node 3 as an independent node . Independent here > means > root->left=root->right=NULL. > > After that it comes to node 2 . ( Note that it is happening in postorder > fashion) . > then it makes node 2 as independent and append it with the list returned > from left side(which is independent node 1) and list returned from right > side *(which is independent node 3) and make the left side returned node as > head and follows the process recursively . The order is similar to inorder > apptoach which is O(n). > > *IF you want to know the inorder approach as well, Here it is :-* > > void BSTTODLL( node *root){ > static int count = 0 ; > static node * temp = NULL: > if(root != NULL){ > BSTTODLL(root->left); > if(count == 0) { > temp = root; > count++; > } > temp->right= root; > root->left = temp; > temp = root; > BSTTODLL(root->right); > } > > } > > // explanation is trivial , its just keeping a temp pointer to previous > node and adjusting pointers in inorder fashion keeping the list sorted. > > Hope it Helps ! > > On Thu, May 24, 2012 at 11:46 PM, sanjay pandey > <sanjaypandey...@gmail.com>wrote: > > > > > > > > > > > the main code is dis function only:::::i will explain dis > > > static Node treeToList(Node root) { > > Node aList, bList; > > > if (root==NULL) return(NULL);* > > /* the below next two lines are just lyk inorder traversal...u mst hv > > done dis*/* > > aList = treeToList(root->small); > > bList = treeToList(root->large); > > > */* this is for breaking the links of its left n right child nodes n > > pointing to itself*/* > > root->small = root; > > root->large = root; > > > * /* Appending leftchild parent n rightchild together in doublylinked > > list form */* > > aList = append(aList, root); > > aList = append(aList, bList); > > > return(aList); > > } > > > -- > > 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 > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > Regards, > > Jalaj Jaiswal > Software Developer, > Adobe Systems > +91-9019947895 > * > * > FACEBOOK <http://www.facebook.com/jalaj.jaiswal89> > LINKEDIN<http://www.linkedin.com/profile/view?id=34803280&trk=tab_pro> -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.