Convert a binary tree to linked list, breadth first, constant storage/destructive
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
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
tailstarting from the left child ofroot:- swap the left child of
tailwith the right child ofroot, - loop (O(n) queue insertion), with
bubble-tostarting fromrootandbubble-fromalways the left child ofbubble-to,- swap the right child of
bubble-towith the right child of ´bubble-from`, - advance
bubble-toandbubble-fromto their left children, - until
bubble-fromreachestail,
- swap the right child of
- advance
tailto its left child, - while
tailis not null.
- swap the left child of
- Finally, return
head. The single linked list now runs along the left children.
- takes a reference to the root node as parameter
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)