The recursion invariant is that calling
convert(root, list)
will return a list that is the tree root converted to a singly linked
list connected by 'left' pointers, with list appended at the end.
So if the tree is empty, the corresonding list is empty, so appending
argument 'list' on the end means just returning the argument.
> if (root == NULL) return list;
Otherwise the tree is not empty. So we first convert the right
subtree with 'list' appended at its end and attach it to the root's
left pointer, which is now the "next" pointer.
> root->left = convert(root->right, list);
But this overwrites root->left, and we still need the old value, so
insert:
> NODE *left_subtree = root->left;
This is the root of the left subtree.
Now convert the left subtree to a list with the list having 'root' as
its first node appended at the end.
> return convert(left_subtree, root);
Sorry in my original post I had a typo.
On May 27, 9:54 am, atul anand <atul.87fri...@gmail.com> wrote:
> @Gene :
>
> NODE *convert(NODE *root, NODE *list)
> {
> if (root == NULL) return list;
> NODE *left_subtree = root->left;
> root->left = convert(root->right, list);
> return convert(left_subtree, root);
>
> }
>
> what *tree(left_subtree, root)* function doing here??
>
>
>
> On Sun, May 27, 2012 at 7:12 PM, Gene <gene.ress...@gmail.com> wrote:
> > 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.- Hide quoted text -
>
> - Show quoted text -
--
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.
