BST to CLL

Code which convert Binary search tree to Sorted Single Circular Linked List.










SOLUTION


tree *convert_bst_to_scll(tree *root){
return bst_2_cll(root)->right;
}

tree * bst_2_cll(tree *ptr){
int a;
if (ptr == NULL) return NULL;
node *ltail = bst_2_cll(ptr->left); // return last node of SCLL of left subtree
node *rtail = bst_2_cll(ptr->right); // return last node of SCLL of right subtree

node *lhead=NULL, *rhead=NULL;

ptr->left = NULL;

if ( ltail && rtail) {
lhead = ltail->right;
ltail ->right = ptr;
rhead = rtail->right;
rtail->right = lhead;
ptr->right= rhead;
return rtail;
}

else if ( ltail){
lhead = ltail->right;
ltail ->right = ptr;
ptr->right = lhead;
return ptr;
}
else if ( rtail) {
rhead = rtail->right;
ptr->right= rhead;
rtail->right = ptr;
return rtail;
}
else {
ptr->right = ptr;
return ptr;
}
}