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.

// 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