TADM2E 3.22

From Algorithm Wiki
Revision as of 18:13, 11 September 2014 by Algowikiadmin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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>