Flatten binary search to in order singly linked li

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

Below is the Java code if someone is interested:

public static Node bTreeToLinkedList(TreeNode root) {
    Node list1 = root.getLeftChild() != null ? bTreeToLinkedList(root.getLeftChild()) : null;
    Node list2 = root.getRightChild() != null ? bTreeToLinkedList(root.getRightChild()) : null;
    Node list3 = ll.new Node((int) root.getData());

    list3.setNext(list2);
    if (list1 == null)
        return list3;

    Node last = list1;
    while (last.getNext() != null)
        last = last.getNext();
    last.setNext(list3);

    return list1;
}

Answer 2

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 3

There is also non-recursive solution for the problem here.

It gives you O(n) time complexity and O(1) space complexity. With recursive solution you can get stack overflow if e.g. you apply it to its own output for a big node set.

Answer 4

Why dont you do inorder traversal and add values to list in a way.  

public List<Integer> inorderToList(TreeNode<Integer> node, List<Integer> list) {
        if(node == null) {
            return list;
        } 
        if (node != null) {
            list = inorderToList(node.getLeft(), list);
            list.add(node.getValue());
            list = inorderToList(node.getRight(), list);
        }
        return list;
    }

Answer 5

We can use recurssion where we build a linked list for each level in the tree and add the list to a vector of lists. With this solution we need to keep a track of which level we are on, so if we have a linked list already for a level and we visit a node on a level visited before we can just add to that list.

I have not added any code for my own node class as its not relevant to the question, also no memory clean up is being demonstrated, however a better solution would be to use boost::shared_ptr to handle clean up.

void generateLists(vector<list<node*>* >*& lists, node* root, int level)
{
    //base case
    if(root == NULL)
        return;

    //if we have don't have a linked list at this level so create this
    if((int)lists->size() == level)
    {
        list<node*>* ls = new list<node*>();
        ls->push_back(root);
        lists->push_back(ls);
    }
    else
    {
        //re-use existing list
        list<node*>* ls = lists->at(level);
        if(ls != NULL)
            ls->push_back(root);
    }

    //in order traversal
    generateLists(lists, root->left, level+1);
    generateLists(lists, root->right, level+1);
}

int main(void)
{
    //create a test binary tree
    node root(6);
    node n2(3);
    node n3(9);
    node n4(2);
    node n5(5);
    node n6(8);
    node n7(9);

    root.left = &n2;
    root.right = &n3;
    n2.left = &n4;
    n2.right=&n5;
    n3.left=&n6;
    n3.right=&n7;

    //will hold a vector of lists for each level in the tree
    vector<list<node*>* >* lists = new vector<list<node*>* >();
    int level=0;
    generateLists(lists, &root, level);
    vector<list<node*>* >::iterator it;

    //convert each level in the tree to a single linked list
    list<node*> flattened;
    for(it = lists->begin(); it != lists->end(); it++)
    {
        list<node*>* linkedList = (*it);
        list<node*>::iterator itNode;
        for(itNode = linkedList->begin(); itNode != linkedList->end(); itNode++)
            flattened.push_back(*itNode);
    }

    //output the tree as a linked list
    list<node*>::iterator itNode;
    for(itNode = flattened.begin(); itNode != flattened.end(); itNode++)
        cerr<<(*itNode)->val<<" ";
}

Answer 6

 private static BSTNode head;
 private static BSTNode tail;
 public static void inorderTraversal(BSTNode node) {
        if(node.left != null) {
            inorderTraversal(node.left);
        }
        System.out.print(node.data + " ");
        constructLinkedList(node.data);
        if(node.right != null) {
            inorderTraversal(node.right);
        }
    }

public static void constructLinkedList(int data) {
        if(head == null) {
            head = new BSTNode(data);
            head.left = null;
            tail = head;
        } else {
            BSTNode node = new BSTNode(data);
            tail.right = node;
            tail.left = null;
            tail = node;
        }
   }

   public static void linkedListToString() {
        BSTNode curr = head;
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while(curr.right != null) {
            sb.append(curr.data).append("->");
            curr = curr.right;
        }
        if(curr.right == null)
            sb.append(curr.data).append("->NULL");
        sb.append("]");
        System.out.print(sb.toString());

   }