TADM2E 3.22
For this problem, an easy solution is to do an in order traversal of the binary tree. Instead of printing the node value, push the value into a LIFO queue. When the traversal is done, you can create the linked list by popping the items one after the other while progressively creating the Linked List. This algorithm has a complexity of O(n).
An other solution is to use the rotate clockwise method described link here
Code Snippet. O(n) reusing tree nodes without using additional containers.
<pre> // push a flattened tree to the right of another flattened tree void push_right(node *pN, node *pR) {
assert(pN->left == NULL); if(pN->right)
push_right(pN->right, pR);
else
pN->right = pR; }
// return the head of a linked list composed of flattened nodes // flattened left + pN + flattened right node *flatten(node *pN) {
node *L = NULL, *R = NULL;
if(pN->left) {
L = flatten(pN->left); pN->left = NULL;
}
if(pN->right) {
R = flatten(pN->right); pN->right = NULL;
} if(L != NULL)
push_right(L, pN);
else
L = pN;
if(R != NULL)
push_right(L, R);
return L;
}
// example output
Printing Tree: 0 (0): 28 --(1): 12
(2): 0
(3): 8
(2): 22
--(1): 84
(2): 40
(3): 34
(3): 64
(2): 89
Flatten ... Printing Tree: 0 (0): 0 --(1): 8
(2): 12
(3): 22
(4): 28
(5): 34
(6): 40
(7): 64
(8): 84
(9): 89
</pre>
