Easy Preorder Traversal of Binary Tree Approach (with diagram)
Consider the following Multilevel Linked List, with N denotes next pointer, P denotes previous pointer and C denotes Child Pointer!\n\n\n\nIn this example, the 
Consider the following Multilevel Linked List, with N denotes next pointer, P denotes previous pointer and C denotes Child Pointer!\n\n![image](https://assets.leetcode.com/users/images/c5b1c12e-3eab-486d-a518-dcbec3a04d1b_1662059476.432131.png)\n\nIn this example, the answer will be [1,2,3,4,5,6,7]\n\nThis given multilevel linked list can be think of binary tree with left Child as Child pointer and right pointer as next pointer.\n![image](https://assets.leetcode.com/users/images/5593ee40-78ce-41e4-8f6d-eda0a3212791_1662059510.5635684.png)\n\n\nPreorder traversal of this tree gives us the same result as of multilevel linked list. [1,2,3,4,5,6,7], hence applying preorder traversal.\n```\npublic Node flatten(Node head) {\n        if(head == null) return null;\n\t\t\n        Node left = flatten(head.child);\n        Node right = flatten(head.next);\n        \n        Node temp = head;\n        head.next = left;\n        \n        if(left != null) {\n            left.prev = head;\n            head.child = null;\n        }\n        \n        while(temp.next != null) {\n            temp = temp.next;\n        }\n        \n        temp.next = right;\n        \n        if(right != null) {\n            right.prev = temp;\n        }\n        \n        return head;\n    }\n```\n\n## Explanation\n- In given solution, we are recursively building linked list from left and right subtree. \n- Flatten function returns the head of linked list created. When we apply recursion, we consider what needs to be done at a given node, considering left and right subtree call will provide the required solution.\n- Now we have left and right linked list and a node.\n- We have added `head.next` to head of linked list returned from left subtree and if left linked list exists, we have added `left.prev = head`\n- After left linked list is attached to head, we traverse the linked list and reach to end, from there we are linking the right linked list from end of first linked list\n- `head.child = null` deletes the child pointer
['Depth-First Search', 'Recursion', 'C', 'Binary Tree', 'Java']