Algowikiadmin: Recovering wiki

2014-09-11T18:22:30Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:13:13Z

Recovering wiki

New page

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 [http://inder-gnu.blogspot.com/2007/04/tree-to-linked-list.html 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>

@@ Line 5: / Line 5: @@
 '''Code Snippet.''' O(n) reusing tree nodes without using additional containers.
-&lt;pre&gt;
+<pre>
 // push a flattened tree to the right of another flattened tree
 void push_right(node *pN, node *pR) {
-   assert(pN-&gt;left == NULL);
+   assert(pN->left == NULL);
-   if(pN-&gt;right)
+   if(pN->right)
-	push_right(pN-&gt;right, pR);
+	push_right(pN->right, pR);
    else
-	pN-&gt;right = pR;
+	pN->right = pR;
+}
@@ Line 19: / Line 19: @@
 node *flatten(node *pN) {
    node *L = NULL, *R = NULL;
-   if(pN-&gt;left) {
+   if(pN->left) {
-	L = flatten(pN-&gt;left);
+	L = flatten(pN->left);
-	pN-&gt;left = NULL;
+	pN->left = NULL;
+   }
-   if(pN-&gt;right) {
+   if(pN->right) {
-	R = flatten(pN-&gt;right);
+	R = flatten(pN->right);
-	pN-&gt;right = NULL;
+	pN->right = NULL;
+   }
    if(L != NULL)
@@ Line 62: / Line 62: @@
 ----------------(8): 84
 ------------------(9): 89
-&lt;/pre&gt;
+</pre>

TADM2E 3.22 - Revision history

Algowikiadmin: Recovering wiki

Algowikiadmin: Recovering wiki