Convert a binary tree to linked list, breadth first, constant storage/destructive

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

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 2

Well, I can't quite figure right now how this helps in this situation but it might give you a lead. There's a technique called "pointer reversal" used for iteratively traversing a tree without the need to use a stack/queue for storing pointers - it was mainly used for low memory overhead garbage collectors. The idea behind this is that when you traverse to a node's child you link that pointer to the child back to the parent so you know where to go back when you finish with that node. That way the traceback information you would generally keep in a stack/queue is now embedded in the tree itself.

I have found the following slideshow with an example (unfortunately there isn't something better on google). The example here shows how to traverse a binary tree without extra storage.

Answer 3

I don't think we need parent pointers. Suppose inductively that levels 0 through k-1 plus a sentinel node have been converted to a singly-linked list on the left child pointers whose right children point to the nodes of level k. Iterate through the list, grabbing each "right child" (level k node) in turn and inserting it at the end of the list, overwriting the right pointer from which it came with its soon-to-be-overwritten left child. When we reach the initial end of the list, we have extended the inductive hypothesis to k+1.

EDIT: code

#include <cstdio>

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

// for simplicity, complete binary trees with 2^k - 1 nodes only
void Flatten(TreeNode *root) {
  TreeNode sentinel;
  sentinel.right = root;
  TreeNode *tail = &sentinel;
  while (true) {
    TreeNode *p = &sentinel;
    TreeNode *old_tail = tail;
    while (true) {
      if ((tail->left = p->right) == NULL) {
        return;
      }
      tail = p->right;
      p->right = p->right->left;
      if (p == old_tail) {
        break;
      }
      p = p->left;
    }
  }
}

int main() {
  const int n = 31;
  static TreeNode node[1 + n];
  for (int i = 1; i <= n; ++i) {
    node[i].value = i;
    if (i % 2 == 0) {
      node[i / 2].left = &node[i];
    } else {
      node[i / 2].right = &node[i];
    }
  }
  Flatten(&node[1]);
  for (TreeNode *p = &node[1]; p != NULL; p = p->left) {
    printf("%3d", p->value);
  }
  printf("\n");
}

Answer 4

The Idea:

You can build the linked list along the left children of the tree. At the same time, the right children of that list are used to hold a queue of the next subtrees to insert at the tail.

---

The algorithm in pseudo code:

(edit: rewritten for clarity)

• A node has three components: a value, a reference to its left child, and a reference to its right child. The references may be null.
• The function to transform a binary tree of such nodes into a single linked list
  • takes a reference to the root node as parameter root,
  • loops, with tail starting from the left child of root:
    • swap the left child of tail with the right child of root,
    • loop (O(n) queue insertion), with bubble-to starting from root and bubble-from always the left child of bubble-to,
      • swap the right child of bubble-to with the right child of ´bubble-from`,
      • advance bubble-to and bubble-from to their left children,
      • until bubble-from reaches tail,
    • advance tail to its left child,
    • while tail is not null.
  • Finally, return head. The single linked list now runs along the left children.

---

Illustration

The starting tree (I believe that it should be a complete tree; if nodes are missing, they should do so from the end. You could try to give meaning to other cases, but there are several different possibilities for that, and it involves a lot of fiddling):

              1
          /       \
      2               3
    /   \           /   \
  4       5       6       7
 / \     / \     / \     / \
8   9   A   B   C   D   E   F

Note that these are not necessarily the values of the nodes, they are just numbered for display purposes.

The tree after 1 iteration (note the list forming from 1 to 3 and the queue of the subtrees rooted in 4 and 5):

                head
                  v
                  1
               /    \
    tail    2         4
      v  /    \      / \
      3         5   8   9
    /   \      / \
  6       7   A   B
 / \     / \
C   D   E   F

after 3 iterations (the list is now 1 to 5, and the queue holds the subtrees rooted in 6 to 9):

                   head
                     v
                     1
                  /     \
               2          6
             /   \       / \
           3       7    C   D
          / \     / \
         4   8   E   F
        / \
tail > 5   9
      / \
     A   B

and after 8 iterations (almost done):

                       head
                         v
                         1
                        / \
                       2   B
                      / \
                     3   C
                    / \
                   4   D
                  / \
                 5   E
                / \
               6   F
              /
             7
            /
           8
          /
         9
        /
tail > A

---

Real Code (Lisp)

This is the node class:

(defclass node ()
  ((left :accessor left)
   (right :accessor right)
   (value :accessor value)))

A useful helper:

(defmacro swap (a b)
  `(psetf ,a ,b
          ,b ,a))

The conversion function (edit: rewritten for clarity):

(defun flatten-complete-tree (root)
  (loop for tail = (and root (left root)) then (left tail)
        while tail
        do (swap (left tail) (right root))
           (loop for bubble-to = root then (left bubble-to)
                 for bubble-from = (left bubble-to)
                 until (eq bubble-from tail)
                 do (swap (right bubble-to) (right bubble-from))))
  root)

---

Irreversible Operation for Jagged Trees:

I have rewritten the above to allow for arbitrary jagged trees. You cannot reconstruct the original tree from this anymore, though.

(defun flatten-tree (root)

;; The inner loop here keeps head at the root of the as-yet unflattened sub-tree,
;; i.e. the node of the first branch,
;; while at the same time ironing all from the root unbranched levels to the left.
;; It ends up nil when the tree is completely flattened.

  (loop for head = (loop for x = (or head root) then (left x)
                         do (when (and x (null (left x)))
                              (swap (left x) (right x)))
                         until (or (null x) (right x))
                         finally (return x))
        for tail = (and head (left head)) then (left tail)
        while head
        do (swap (left tail) (right head))

;; This inner loop is the O(n) queue insertion

           (loop for bubble-to = head then (left bubble-to)
                 for bubble-from = (left bubble-to)
                 until (eq bubble-from tail)
                 do (swap (right bubble-to) (right bubble-from))))

;; Finally, return the original root.

  root)

Answer 5

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 6

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