Convert Binary Tree to Double Linked List in Zig-Zag Order

Question: given a binary tree, write an algorithm to convert the tree into a double-linked list. The list must be as if the tree is traversed in zig-zag and level order.

Solution: let's first understand what the objective is. By zig-zag level order, the question means that we need to traverse the tree in level order, a.k.a breadth first, such that the next level is traversed in the oposite direction to the current level. For example, take a look at this tree:

A zig-zag level-order traversal creates the list 1, 2, 3, 5, 4. It doesn't matter which direction the root is printed because there is only one node. However, since the second level is printed left to right, 2 then 3, the third level is printed from right to left, 5 then 4.

Now we understand the question, let's figure out how to solve this problem. Well, the only tricky part is to traverse the tree in zig-zag order. The other part, adding nodes to a linked list, is easy.

To solve this problem, we need two stacks. One stack stores nodes of levels that traversed from left to right. The other stores nodes of levels that traversed from right to left. The idea is to add the children of each node of the same level into a different stack than their parent. Thus, all children of the same level are in the same stack, separating one level from another. These children nodes are also pushed in the stack in the same direction with each other but opposite direction with their parents, so they can be traversed in the opposite direction to their parents. Moreover, as we traverse the tree, we add each node into a double linked list. Here is the implementation in C++:

struct Node* bt2ZigZagDoubleLinkedList(struct Node* root)
{
  if (root == NULL)
    return NULL;

  struct Node* head = root;
  struct Node* listIT = NULL;
  struct Node* prevNode = NULL;
  
  stack left2RightStack;
  stack right2LeftStack;

  left2RightStack.push(root);
  
  while (!left2RightStack.empty())
  {
    //add nodes from left to right to the list
    while (!left2RightStack.empty())
    {
      //set previous node
      prevNode = listIT;
    
      //pop a node in left2RightStack and add it to list
      listIT = left2RightStack.top(); 
      left2RightStack.pop();

      //add child nodes of the newly node in right to left direction
      if (listIT->left != NULL)
        right2LeftStack.push(listIT->left);
      
      if (listIT->right != NULL)
        right2LeftStack.push(listIT->right);

      //set left pointer of current node to the node in front of it
      listIT->left = prevNode; 

      //the previous node points to the current node in list
      if (prevNode != NULL)
        prevNode->right = listIT;
    }

    //add nodes from right to left to the list
    while (!right2LeftStack.empty())
    {
      prevNode = listIT;
      
      listIT = right2LeftStack.top();

      right2LeftStack.pop();

      if(listIT->right != NULL)
        left2RightStack.push(listIT->right);
        
      if(listIT->left != NULL)
        left2RightStack.push(listIT->left);

      listIT->left = prevNode;

      if (prevNode != NULL)
        prevNode->right = listIT;
    }
  }

  //connect linked the end node of list to NULL and the node in front of it
  listIT->right = NULL;
  listIT->left = prevNode;
  
  return head;
}

Code explanation: the method accepts the tree's root node as its parameter and return the head node to the double linked list.

1. First two lines check for null node, empty tree. If the tree is empty, we return an empty linked list.
2. The next three lines declare three pointers to tree nodes. head points to the head node of the linked list. We initialize it to the root node because the root node will be the first node in the list. listIT will be the iterator to traverse the tree. prevNode points to the last node visited by listIT. We need it to construct the double linked list since we must point the previous node to the current node and the current node back to previous node.
3. We also create two stacks that contain pointers to tree nodes. left2RightStack contains nodes in left to right order while right2LeftStack contains nodes in right to left order.
4. We then initialize left2RightStack by pushing the root node inside it.
5. There are three different while loops. The first while loop makes sure that we visit all nodes in the tree and add them into our double linked list. The two inner while loops make sure that we add the nodes level by level and in opposite directions. We do the following in the first inner while loop:
   • First, we pop a node off the left2RightStack and assign it to listIT.
   • Then, we add listIT's left child into the right2LeftStack before adding listIT's right child into the same stack. This guarantees that when we pop those children off the right2LeftStack they will be poped in the opposite order to their parent.
   • After that, we add listIT into the linked list. Pointing its left pointer to the node before it, prevNode
   • Finally, we point the right pointer of the prevNode to listIT. Remember we're making a double linked list, that's why we need to point the node in front of listIT, which is prevNode, to listIT.
   • The while loop runs until there is no nodes left in left2RightStack.
6. After the first inner loop traverses a level from left to right, the second inner while loop traverses the next level from right to left. The process is similar to that of left-to-right traversal. The only difference is that we add right children to the stack before left children.
7. Once all nodes have been added into the double linked list, we'll connect the end node of the list to the node before it and to a null node as the node after it.
8. Lastly, we return head. In the beginning, we have already assigned head to the root node which is the first node of the list, so head is point at the first node in the list.

That's all for this problem. If you find any mistake or have better solution, please feel free to let me know. Thanks for reading :)