Write code for converting a tree in to Doubly Linked List using existing nodes only in single traversal.
Logic:
Do the inorder traversal of the list and update the pointers keeping track of the last visited node.
createDLL( struct node * root, struct node ** last_node, struct node ** head)
{
if(root == NULL) return;
if(root->left == NULL and root->right == NULL && *head == NULL)
{
*last_node = root;
*head = root;
return;
}
createDLL(root->left);
if(*last_node = NULL)
{
*head = root;
*last_node = root;
return;
}
(*last_node)->right = root;
root->left = *last_node;
*last_node = root;
createDLL(root->right);
}
// head points to the final doubly link list
In main make the last node right point to the head
and head left point to last node.
Subscribe to:
Post Comments (Atom)
use postorder???
ReplyDeleteHi.. Ur code fails for test cases like
ReplyDelete1.)23 has right child 45
2.)25 has children 20 n 28
20 has left child 15
15 has right child 18
i.e. since u r returning after examining d leftmost child, it fails if that child has a right child.....
u can chk my code...
// BST to Circular Doubly Linked List
// Logic: Do inorder traversal and modify the pointers
void BSTtoCDbl(List *root,List **head,List** last)
{
if(!root) return;
BSTtoCDbl(root->left,head,last);
if(*last == NULL)
{
*head = root;
*last = *head;
}
else
{
(*last)->right = root;
root->left = *last;
*last = root;
}
BSTtoCDbl(root->right,head,last);
}
This comment has been removed by the author.
ReplyDeleteI need the answer of the algorithm for implementation of the creating the circular double linked list.
ReplyDeleteRaj
Nabarangpur.
Implementation of Doubly Circular linked list here :)
ReplyDelete