List Unflattening

MattCruikshank · March 29th, 2010, 10:15 PM

On page 49, the book shows an example of how to unflatten. I feel that it is an odd choice to select recursion to do the work, especially considering the many references to memory efficiency. By using recursion, the algorithm can reach a peak memory inefficiency of O(n).

Instead, you can start from the tail, looking to prev until you find an element that has a child. Then, adjust the tail to point to the prev of the child.

Code:

void unflatten(Node** head, Node** tail)
{
    if (!(*tail)) return;
    Node* track = *tail;
    while (track)
    {
        if (track->child)
        {
            *tail = track->child->prev;
            track->child->prev = NULL;
            (*tail)->next = NULL;
        }
        track = track->prev;
    }
}

In my examples, I continued to pass a Node** for both head and tail, allowing the implementation to choose which variables to possibly update, but I realize that is a matter of taste.

Also, in your example code, you changed the name head to start, in this example only.

Regards,
Matt

KennyS · April 11th, 2010, 11:41 AM

Yes! I'm glad to have found your comment to validate what I was already thinking. It seems to me that the key insight is that the flattening and unflattening problems (pages 44-49) are symmetric and invertible. The algorithm you posted is the inverse of the author's flattening solution. It is simpler and more efficient than the recursive unflattening presented in the book. I'm surprised that the authors overlooked it.

lebanman · February 10th, 2013, 07:24 AM

The suggested alternative solution that does not use recursion is nice. It is suitable for a specific flattening order that the authors used specifically.

I expect that the authors wanted to solve the unflattening problem regardless of the order of the flattened list. The authors suggested another ordering in which child elements appear after their parents in the flattened list. The suggested alternative solution not using recursion does not work for this ordering for example.

techmania · June 16th, 2013, 05:06 PM

If you see the code for

Code:

exploreAndSeparate

,
there seems to be a potential null pointer access problem in cases where traversal will revisit the nodes multiple times with children whose back pointers are already snipped off by a previous traversal. So it seems prudent to add the following check before snipping the links:

Code:

...
if (curNode->child) 
{
   if (curNode->child->prev) {   //add check for null
      curNode->child->prev->next=NULL;
      curNode->child->prev=NULL;
   }
}
...

What do you say?

wmy512 · November 10th, 2013, 07:05 PM

Quote:

Originally Posted by lebanman

The suggested alternative solution that does not use recursion is nice. It is suitable for a specific flattening order that the authors used specifically.

I expect that the authors wanted to solve the unflattening problem regardless of the order of the flattened list. The authors suggested another ordering in which child elements appear after their parents in the flattened list. The suggested alternative solution not using recursion does not work for this ordering for example.

But if the ordering in which child elements appear after their parents in the flattened list. The recursion does not work neither..

yevvi · May 25th, 2014, 11:02 PM

Quote:

Originally Posted by lebanman

The suggested alternative solution that does not use recursion is nice. It is suitable for a specific flattening order that the authors used specifically.

I expect that the authors wanted to solve the unflattening problem regardless of the order of the flattened list. The authors suggested another ordering in which child elements appear after their parents in the flattened list. The suggested alternative solution not using recursion does not work for this ordering for example.

Maybe i don't fully understand the problem, but i don't see how the list can be unflattened at all (unambiguously) if the child list inserted after the parent node. E.g. in the author's example if we insert 6,25,6 after 5 (assume 6,25,6 has no children) the it will be 5, 6, 25, 6, 33, 17, ... Then how do we know that the child list of 5 has only 3 elements and not more?

yevvi · May 25th, 2014, 11:10 PM

What about this alternative solution without recursion:

Traverse list from the start. If a node has a child, set the child's prev pointer to null (but do not change the next pointer of the node pointing to this child yet so we can continue to traverse).
Also during traversing, keep track of both current and previous nodes. If current->prev is null, set previous->next to null as well.

Entertainment Unit · December 19th, 2014, 05:03 PM

Quote:

Originally Posted by wmy512

But if the ordering in which child elements appear after their parents in the flattened list. The recursion does not work neither..

I came to this conclusion as well.

I've been attempting the problems before I read how the author would solve them, so I flattened the list in a child-to-next algorithm instead of the author's child-to-end. I'm not sure that it's impossible to unflatten a list that's been flattened child-to-next, but certainly a lot harder since you're scrambling the sublists up.

My takeaway here is if the interview asks you to do something, expect that they might ask you to reverse it in a subsequent question.

yamaryl · March 14th, 2016, 11:45 AM

Quote:

Originally Posted by lebanman

I expect that the authors wanted to solve the unflattening problem regardless of the order of the flattened list.

Correct me if I'm wrong, but I don't think it is possible to find an algorithm that unflattens independently of the flattening algorithm.