Oh, great. Yesterday I flattened a bush; today you want me to un-flatten it?
This is going to require a bit of recursion, I can just tell. That's fine, I love recursion.
I kept all the child pointers when I flattened the bush, so that will tell me where the children start. I'll just traverse the list, and anytime I find a child pointer, I'll disconnect the child and all its siblings, reconnecting them as the child of the parent.
Hmmm. Only one small problem: how will I know when to stop disconnecting the child? The first parent that I encounter will get the child, and the remainder of the list afterwards, as its children.
Maybe I'd better rewrite Flatten to use a different algorithm. Certainly the interviewer would have steered me toward a solution with recognizable ends. Wouldn't he?
Continue reading "Interview Day 6: Unflattening a Bush" »