Convert a Binary Tree into Doubly Linked List in spiral fashion - GeeksforGeeks
Given a Binary Tree, convert it into Doubly Linked List where the nodes are represented Spirally. The left pointer of the binary tree node should act as a previous node for created DLL and right pointer should act as next node.
The solution should not allocate extra memory for DLL nodes. It should use binary tree nodes for creating DLL i.e. only change of pointers is allowed
We can do this by doing a spiral order traversal in O(n) time and O(n) extra space. The idea is to use deque (Double-ended queue) that can be expanded or contracted on both ends (either its front or its back). We do something similar to level order traversal but to maintain spiral order, for every odd level, we dequeue node from the front and inserts its left and right children in the back of the deque data structure. And for each even level, we dequeue node from the back and inserts its right and left children in the front of deque. We also maintain a stack to store Binary Tree nodes. Whenever we pop nodes from deque, we push that node into stack. Later, we pop all nodes from stack and push the nodes in the beginning of the list. We can avoid use of stack if we maintain a tail pointer that always points to last node of DLL and inserts nodes in O(1) time in the end.
Read full article from Convert a Binary Tree into Doubly Linked List in spiral fashion - GeeksforGeeks
Given a Binary Tree, convert it into Doubly Linked List where the nodes are represented Spirally. The left pointer of the binary tree node should act as a previous node for created DLL and right pointer should act as next node.
The solution should not allocate extra memory for DLL nodes. It should use binary tree nodes for creating DLL i.e. only change of pointers is allowed
We can do this by doing a spiral order traversal in O(n) time and O(n) extra space. The idea is to use deque (Double-ended queue) that can be expanded or contracted on both ends (either its front or its back). We do something similar to level order traversal but to maintain spiral order, for every odd level, we dequeue node from the front and inserts its left and right children in the back of the deque data structure. And for each even level, we dequeue node from the back and inserts its right and left children in the front of deque. We also maintain a stack to store Binary Tree nodes. Whenever we pop nodes from deque, we push that node into stack. Later, we pop all nodes from stack and push the nodes in the beginning of the list. We can avoid use of stack if we maintain a tail pointer that always points to last node of DLL and inserts nodes in O(1) time in the end.
void spiralLevelOrder(Node *root){ // Base Case if (root == NULL) return; // Create an empty deque for doing spiral // level order traversal and enqueue root deque<Node*> q; q.push_front(root); // create a stack to store Binary Tree nodes // to insert into DLL later stack<Node*> stk; int level = 0; while (!q.empty()) { // nodeCount indicates number of Nodes // at current level. int nodeCount = q.size(); // Dequeue all Nodes of current level and // Enqueue all Nodes of next level if (level&1) //odd level { while (nodeCount > 0) { // dequeue node from front & push it to // stack Node *node = q.front(); q.pop_front(); stk.push(node); // insert its left and right children // in the back of the deque if (node->left != NULL) q.push_back(node->left); if (node->right != NULL) q.push_back(node->right); nodeCount--; } } else //even level { while (nodeCount > 0) { // dequeue node from the back & push it // to stack Node *node = q.back(); q.pop_back(); stk.push(node); // inserts its right and left children // in the front of the deque if (node->right != NULL) q.push_front(node->right); if (node->left != NULL) q.push_front(node->left); nodeCount--; } } level++; } // head pointer for DLL Node* head = NULL; // pop all nodes from stack and // push them in the beginning of the list while (!stk.empty()) { push(&head, stk.top()); stk.pop(); } cout << "Created DLL is:\n"; printList(head);}