Binary Search Tree to Circular Doubly Linked List

bst_to_cdll.c

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
        int data;
        struct Node* left;
        struct Node* right;
} Node;

void add_tree(Node **root, int v) {
        if (*root == NULL) {
                *root = malloc(sizeof(Node));
                (*root)->data = v;
                (*root)->left =(*root)->right = NULL;
        }
        else if (v < (*root)->data)
                add_tree(&((*root)->left), v);
        else
                add_tree(&((*root)->right), v);
}

void print_tree(Node *root) {
        if (root == NULL) return;
        print_tree(root->left);
        printf("%d\n", root->data);
        print_tree(root->right);
}

void tree_to_list_aux(Node* root, Node **start, Node **last) {
        if (root == NULL) return;

        // Bottom-left child
        if (*start == NULL && root->left == NULL && root->right == NULL) {
                *start = root;
                *last = root;
                return;
        }

        tree_to_list_aux(root->left, start, last);

        // Connect previous and current node
        (*last)->right = root;
        root->left = *last;
        *last = root;

        tree_to_list_aux(root->right, start, last);
}

void tree_to_list(Node *root, Node **start) {
        Node *end = NULL;
        tree_to_list_aux(root, start, &end);
        // Connect first and last node
        if (*start != NULL) {
                (*start)->left = end;
                end->right = *start;
        }
}

void print_list(Node *start) {
        if (start == NULL) return;
        Node *first = NULL;
        while (start != first) {
                printf(">> %d\n", start->data);
                if (first == NULL) first = start;
                start = start->right;
        }
}

void clean(Node *start) {
        if (start == NULL) return;
        // Break the circle
        start->left->right = NULL;
        while (start != NULL) {
                Node *temp = start;
                start = start->right;
                free(temp);
        }
}

int main(void) {
        Node* root = NULL;
        add_tree(&root, 10);
        add_tree(&root, 5);
        add_tree(&root, 7);
        add_tree(&root, 3);
        add_tree(&root, 17);
        print_tree(root);

        Node *start = NULL;
        tree_to_list(root, &start);
        print_list(start);

        clean(start);

        return 0;
}