C++ | Two Solutions
Solution 1 - using array\n1. Iterate through nodes\n2. Add current node to array\n3. If the node has a child traverse the child\n4. At the end we will have an a
## Solution 1 - using array\n1. Iterate through nodes\n2. Add current node to array\n3. If the node has a child traverse the child\n4. At the end we will have an array in the order we want.\n5. Iterate through array  and set next and prev pointer correctly also remove child nodes\n\nLet\'s take an example\n``` \n1---2---3---4---5---6--NULL\n         |\n         7---8---9---10--NULL\n             |\n             11--12--NULL\n```\nFor the above example our array will be\n{1} , {1,2}, {1,2,3}. Now three has a child go to child\n{1,2,3,7}, {1,2,3,7,8}. 8 has a child.\n{1,2,3,7,8,11}, {1,2,3,7,8,11,12}. Now the next element is NULL return and we will be at 9\n{1,2,3,7,8,11,12,9,10} again NULL return we will be at 4\n{1,2,3,7,8,11,12,9,10,4,5,6}\nThis is the order we want.\nIterate over the array and set prev and next pointers.\n\nCODE: \n\n```\n// Helper method to insert node in array - iteration\n    void TravNodes(Node* head, vector<Node*>& ans){\n        ans.push_back(head);   // Insert the current node\n\t\t // if node has a child recursive call to the child\n        if(head->child) TravNodes(head->child,ans);  \n        if(!head->next) return;  // if next node is NULL return\n        TravNodes(head->next,ans);  // Traverse the next node\n    }\n    \n    Node* flatten(Node* head) {\n        if(!head) return head;  // If there is node head return\n        vector<Node*>ans;  // ans array to store nodes in order\n        ans.push_back(NULL); // Let the first element be NULL as head->prev = NULL;\n        TravNodes(head,ans);  // Helper function call\n\t\t// Iterate from the second element till second last element (1st ele is NULL)\n        for(int i = 1;i<ans.size()-1;i++){ \n            ans[i]->prev = ans[i-1];   // set prev ele\n            ans[i]->next = ans[i+1];  // set next ele\n            ans[i]->child = nullptr;  // remove child ptr\n        }\n\t\t// Set next and prev for last element\n        ans[ans.size()-1]->prev = ans[ans.size()-2];  \n        ans[ans.size()-1]->next = NULL;\n        ans[ans.size()-1]->child = NULL;\n        return ans[1];  // Return the head stored in ans[1]\n    }\n```\n\n## Solution 2 - Recursion without array\n1. Iterate through the nodes\n2. If node has child save the next node to a variable; call recursive function call on child (Will return child as head)\n3. Set next of current node to child\n4. Remove child ptr from current node\n5. Iterate through the child node sequence to get last node\n6. Set next of last child sequence node to the variable we saved in step 2\n7. Set next of this node to the next we saved on step 2\n8. If that next was not NULL then set its previous to this last node\n9. Return head\n```\n    Node* flatten(Node* head) {\n        if(!head) return NULL;\n        Node* trav = head;\n        while(trav){\n            if(trav->child){\n                Node* next = trav->next;\n                Node* child = flatten(trav->child);\n                trav->child = NULL;\n                trav->next = child;\n                child->prev = trav;\n                Node* lastNode = child;\n                while(lastNode->next) lastNode = lastNode->next;\n                lastNode->next = next;\n                if(next) next->prev = lastNode;\n            }\n            trav = trav->next;\n        }\n        return head;\n    }\n```\nHope this helps! Happy Coding :)
[]