@web-hav
*I think the actual problem is in place changing a bst into a DLL(Doubly
linked list) without using extra space .*
If you are allowed to use extra space then problem is pretty simple and your
code solves its purpose.
Shrish Chandra Mishra
CSE NIT,Allahabad
On Wed, Mar 31, 2010 at 3:38 PM, web-hav <vaibhav...@gmail.com> wrote:
> Algorithm :
>
> 1 Do inorder traversal and at the time of reading data from tree, add
> data to doubly link list.
> (Inorder traversal will give you sorted order data and it can be
> added to DLL. Thus, we can get sorted DLL.)
>
>
> Code :
>
>
> struct node
> {
> struct node *left;
> int data;
> struct node *right;
> };
>
> struct dllist {
> int number;
> struct dllist *next;
> struct dllist *prev;
> };
>
> struct dllist *head, *tail, *listnode;
>
> void bstToDLL(struct node *treenode) {
>
> treeTraverse(treenode);
>
> for(listnode = head; listnode != NULL; listnode = listnode->next) {
> printf("%d\n", listnode->number);
> }
>
> }
>
>
>
> void treeTraverse(struct node *treenode)
> {
>
> if(treenode!=NULL)
> {
> treeTraverse(treenode->left);
> listnode = (struct dllist *)malloc(sizeof(struct dllist));
> listnode->number = treenode->data;
> appendToDoublyLinkList(listnode);
> treeTraverse(treenode->right);
> }
> else
> return;
> }
>
>
>
> void appendToDoublyLinkList(struct dllist *listnode) {
>
> if(head == NULL) {
> head = listnode;
> listnode->prev = NULL;
> }
> else {
> tail->next = listnode;
> listnode->prev = tail;
> }
>
> tail = listnode;
> listnode->next = NULL;
> }
>
>
>
>
>
> On Mar 28, 3:13 pm, Piyush Verma <114piy...@gmail.com> wrote:
> > how to convert a BST into a sorted doubly linked list.
> > is there any solution of this question.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> 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 algoge...@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.
