Flatten binary search to in order singly linked list [C]

Question

I am trying to flatten a binary search tree to a singly linked list. Binary search tree: ``` 6 / \ 4 8 / \ \ 1 5 11 / 10 ``` Flattened Singly Linked List: ``` 1 -> 4 -> 5 -> 6 -> 8 -> 10 -> 11 ``` I can't seem to figure this out for some reason. I have a struct for the tree nodes: ``` typedef stuct node { int key; struct node *left; struct node *right; } Node; ``` I have a function to create and allocate memory to the tree node: ``` Node* newNode (int key) { Node *new = malloc (sizeof(Node)); new->left = NULL; new->right = NULL; new->key = key; return new; } ``` I have a struct for the list nodes: ``` typedef struct list { int key; struct list* next; } List; ``` I have a function to create the list node: ``` List* newListNode (int key) { List *new = malloc(sizeof(List)); new->key = key; new->next = NULL; return new; } ``` And I have working functions to create the binary search tree, to insert the values, etc., but now I need to create a function to flatten the tree to a list. ``` Lis…

Accepted Answer

This is relatively simple to do recursively:

- Check the node on the left; if there is something there, flatten the left to a list #1

- Check the node on the right; if there is something there, flatten the right to a list #2

- Create a single-node list #3 with the key of the current node

- Concatenate the lists in the order #1 -> #3 -> #2

- Return the concatenated list as your result

Here is how you can code it up:

```
List* flattenToLL(Node* root) {
    List *list1 = (root->left) ? flattenToLL(root->left) : NULL;
    List *list2 = (root->right) ? flattenToLL(root->right) : NULL;
    List *list3 = newNode(root->key);
    // The "middle" list3 cannot be NULL; append list2 to list3
    list3->next = list2; // If list2 is NULL, it's OK
    if (!list1) return list3; // Nothing to prepend
    List *last = list1;
    while (last->next) last=last->next; // Go to the end of list1
    last->next = list3; // Append list3+list2 to the end of list1
    return list1;
}
```

Flatten binary search to in order singly linked list [C]

Solution

Problem