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

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 2

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