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

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 2

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 3

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.