Convert a binary tree to linked list, breadth firs

Question

This is not homework, and I don't need to answer it, but now I have become obsessed :)

The problem is:

• Design an algorithm to destructively flatten a binary tree to a linked list, breadth-first. Okay, easy enough. Just build a queue, and do what you have to.
• That was the warm-up. Now, implement it with constant storage (recursion, if you can figure out an answer using it, is logarithmic storage, not constant).

I found a solution to this problem on the Internet about a year back, but now I've forgotten it, and I want to know :)

The trick, as far as I remember, involved using the tree to implement the queue, taking advantage of the destructive nature of the algorithm. When you are linking the list, you are also pushing an item into the queue.

Each time I try to solve this, I lose nodes (such as each time I link the next node/add to the queue), I require extra storage, or I can't figure out the convoluted method I need to get back to a node that has the pointer I need.

Even the link to that original article/post would be useful to me :) Google is giving me no joy.

Edit:

Jérémie pointed out that there is a fairly simple (and well known answer) if you have a parent pointer. While I now think he is correct about the original solution containing a parent pointer, I really wanted to solve the problem without it :)

The refined requirements use this definition for the node:

struct tree_node
{
  int value;
  tree_node* left;
  tree_node* right;
};

Answer 1

This is my answer which works. I now realise this is the same approach as Svante's solution(!), although I build the tree to the right.

For the record, here is the C# code:

// Flatten a tree into place in BFS order using O(1) space and O(n) time.
// Here is an example of the transformation (the top-row indicates the
// flattened parts of the tree.
//  
//  a
//  |---.
//  b   c
//  |-. |-.
//  d e f g
//  
//  becomes
//  
//  a-b-c
//  | | |-.
//  d e f g
//  
//  becomes
//  
//  a-b-c-d-e-f-g
//  
public static void FlattenBFS(Tree<T> t)
{
    var a = t; // We "append" newly flattened vertices after 'a'.
    var done = (t == null);
    while (!done)
    {
        done = true;
        var z = a; // This is the last vertex in the flattened part of the tree.
        var i = t;
        while (true)
        {
            if (i.L != null)
            {
                var iL = i.L;
                var iLL = iL.L;
                var iLR = iL.R;
                var aR = a.R;
                i.L = iLL;
                a.R = iL;
                iL.L = iLR;
                iL.R = aR;
                a = iL;
                done &= (iLL == null) & (iLR == null);
            }
            if (i == z)
            {
                break; // We've flattened this level of the tree.
            }
            i = i.R;
        }
        a = (a.R ?? a); // The a.R item should also be considered flattened.
    }
}

Answer 2

Here is my appoach to the problem;

struct TreeNode
{
    TreeNode(int in) : data(in)
    {
        left = nullptr;
        right = nullptr;
    }
    int data;
    TreeNode* left;
    TreeNode* right;
};


//Converts left pointer to prev , right pointer to next
// A tree which is like              5 
//                                 11  12

//will be converted to double linked list like 5 -> 12 -> 11 
void finalize(TreeNode* current, TreeNode* parent)
{
    if (parent == nullptr)
    {
        current->left = nullptr;
        return;
    }

    if (parent->left == current)
    {
        if (parent->right == nullptr)
        {
            parent->right = current;
            current->left = parent;
        }
        current->left = parent->right;
    }
    else
    {
        current->left = parent;
        parent->right = current;
        current->right = parent->left;
    }
}


void traverser(TreeNode* current, TreeNode* parent)
{
    if (current->left != nullptr)
        traverser(current->left, current);
    if (current->right != nullptr)
        traverser(current->right, current);

    finalize(current, parent);
}

void start(TreeNode* head)
{
    if (head == nullptr || (head->left == nullptr && head->right == nullptr))
        return;

    traverser(head, nullptr);
}


int main()
{
    TreeNode* n1 = new TreeNode(5);
    TreeNode* n2 = new TreeNode(11);
    TreeNode* n3 = new TreeNode(12);



    n1->left = n2;
    n1->right = n3;

    start(n1);
}

Answer 3

Just for the record, the recursive version is beautiful (this is in C#):

[Edited: as st0le points out, my first version contains 'new's! Forgive me, I've spent the last twenty years coding in declarative languages. Here is the corrected version.]

[Edit: double rats. This isn't breadth first.]

public static Tree<T> Flatten(Tree<T> t, Tree<T> u = null)
{
    if (t == null) return u;
    t.R = Flatten(t.L, Flatten(t.R, u));
    t.L = null;
    return t;
}

Answer 4

wat about this solution

temp=root;
struct node*getleftmost(struct node* somenode)
{
   while(somenode->left)
   somenode=somenode->left;
   return somenode;
}

 while(temp)
 {
 if(temp->right){
 (getletfmost(temp))->left=temp->right;
 temp->right=NULL;}
 temp=temp->left;
 }

Answer 5

First of all, I'll assume your nodes have a "parent" field that points to their parent. It's either that, or you need a stack to be able to move back up in the tree (and thus can't achieve that O(1) auxiliary memory requirement).

There is a well-known in-order iteration which is both iterative and in O(1) space. Suppose for instance you'd want to print items in order. Basically, when you traverse a binary tree, you have to decide at any given moment, in any given node, whether you want to move UP (to the parent), LEFT (to the left child) or RIGHT. The idea for this algorithm is to base this decision on where you come from:

1. if you come down from the parent, then clearly you are visiting the node for the first time, so you go LEFT;
2. if you come up from the left child, then you have visited all nodes that are smaller than the current node, so you can print (remember we want to print nodes in order here) the current node, and then go RIGHT;
3. finally, if you come up from the right child, that means you have visited the entire subtree rooted at this particular node, and so you can back UP to the parent.

OK: so this is the algorithm that you take for a base. Now, clearly, if you are destructively modifying this into a linked list, you should only modify a node once you aren't going to visit it anymore. That is when you are coming up from the right. At that point, you have to decide what the successor of that node is going to be... ?

Well, you need to keep track, at all times, of two pointers: one to the smallest node you have visited, and one to the largest node you have visited in the current rooted subtree. You use the smallest as the successor for nodes you last visit when you come up from the right child, and use the largest as the successor for nodes you last visit coming up from somewhere else, because they happen to not have a right child!

EDIT 1: I forgot to say that I implicitly consider that the "parent" field in the binary tree becomes the "next" field in the linked list---that is what I modify in the last step.

EDIT 3: The following part of my answer has turned out to not quite answer the original question (but what preceded is still pertinent).

---

EDIT 2: Following Svante's understandable wish that I explicit my suggestion of using left rotations into some code:

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

typedef struct node *node;

struct node
{
  int value;
  node left;
  node right;
};

node new_node(int value, node left, node right)
{
    node n = (node) malloc(sizeof(struct node));
    n->value = value; n->left = left; n->right = right;
    return n;
}

int rotate_right(node tree)
{
    if(tree != NULL && tree->left != NULL)
    {
        node
            a = tree->left->left,
            b = tree->left->right,
            c = tree->right;
        int tmp = tree->value;
        tree->value = tree->left->value;
        tree->left->value = tmp;

        tree->left->left = b;
        tree->left->right = c;
        tree->right = tree->left;

        tree->left = a;
        return 1;
    }
    return 0;
}

The rotation function is not elegant, but as it is easy to get mixed up, I tried to follow the exact same naming as used in Wikipedia's article on rotations. The nodes A, B, C are named as such in my code; the nodes P and Q are not, and since I chose not to use pointers of pointers, I instead resorted to the trick of switching values of P and Q---in lieu of switching places. With "rotation_right" at our disposal, the conversion algorithm is quite simple:

void convert_to_list(node tree)
{
    if(tree != NULL) {
        while(rotate_right(tree) != 0);
        convert_to_list(tree->right);
    }
}

The resulting tree is a sorted linked-list, where the next pointer of the list is what used to be the right pointer in the tree. Finally, here is a test program:

int main()
{
    node t =
        new_node(4,
              new_node(2, NULL, new_node(3, NULL, NULL)),
              new_node(8, new_node(5, NULL, NULL), NULL));
    convert_to_list(t);
    for(; t != NULL; t = t->right)
        printf("%d, ", t->value);
    return 0;
}

Answer 6

There is a simple java implementation with the first method described.

http://www.dsalgo.com/BinaryTreeToLinkedList.php