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.

List* flattenToLL(Node* root) {
    ...
}

I just can't seem to figure out how to flatten it to a singly linked list. I have seen a lot of other threads and sites discussing a conversion of a binary search tree to a doubly or circular linked list, but none about copying the values into a singly linked list. If anyone can offer up suggestions on how I can accomplish this I would really appreciate it. This is for a homework assignment, so if you can also provide a small explanation to help me learn that would be great.

Answer 1

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;
}

Answer 2

You need to do an in-order traversal, adding each element in turn to the list.

The pseudo-code for this is:

def traverse (node, list):
    if node == NULL: return       # Ignore empty subtrees.
    traverse (node.left, list)    # Do left subtree first.
    list.append (node.data)       # Then current node.
    traverse (node.right, list)   # Then right subtree.

list = new List()                 # Create empty list.
traverse (root, list)             # Collapse tree to list.

That's it, as simple as it gets. Step 1, process the left subtree. Step 2, add the data. Step 3, process the right subtree.

The only "clever" bit is correct handling of empty subtrees in a way that makes the code succinct.

---

Keep in mind that, for maximum efficiency, appending to a linked list may be a relatively expensive operation if the pointer to the final element (tail) is not cached somewhere. That will entail having to find the tail for each element being added, something that will turn your flattening algorithm into an O(n2) one.

Since inserting an element at the start of a linked list is almost invariably O(1) by virtue of the fact you must maintain a head pointer, it's often more efficient to do a reverse in-order traversal instead:

def traverse (node, list):
    if node == NULL: return       # Ignore empty subtrees.
    traverse (node.right, list)   # Do right subtree first.
    list.insert (node.data)       # Then current node at list start.
    traverse (node.left, list)    # Then left subtree.

This keeps the flattening operation at O(n).