Convert Binary Tree in Zigzag order to a Doubly linked list

Ii have a problem. i have to convert a Binary Tree in its zigZag format to a doubly linked list.

 Given BT:
                 [1]
          [2]                  [3]
      [4]      [5]         [6]        [7]
    [8]  [9] [10] [11] [12] [13] [14] [15]


ZigZag order of BT in DLL:
      [1] [3] [2] [4] [5] [6] [7] [15] [14] [13] [12] [11] [10] [9] [8]
    

Here is my pseudocode:

DLLNode* ConvertBTToZigZgDLL(Node* root)
{
  DLLNode* start=createDLLNode(root->data);
  DLLNode* tail=start;
  Stack<Node> stack1, stack2;
  stack1.push(root->left);
  stack1.push(root->right);
  while( !stack1.Empty() || !stack2.Empty() )
  {
     while(stack1.HasElement())
     {
       Node* temp=stack1.Pop();
       stack2.push(temp->right);
       stack2.push(temp->left);
       tail=Attach(tail,createDLLNode(temp->data));
       tail=tail->next;
     }
     while(stack2.HasElement())
     {
       Node* temp=stack2.Pop();
       stack1.push(temp->left);
       stack1.push(temp->right);
       tail=Attach(tail,createDLLNode(temp->data));
       tail=tail->next;
     }
  }
  return start;

} Here TimeComplexity O(N), where N is the no of nodes in the given Binary Tree.

  DLLNode* Attach(DLLNode* source, DLLNode* dest)
  {
     source.Next=dest;
     dest.prev=source;
     return source;
  }

  DLLNode* CreateDLLNode(int data)
  {
    DLLNode* res=malloc(sizeof(struct DLLNode));
    res->data=data;
    res->prev=NULL;
    res->next=NULL;
    return res;
   }

All i want to know what is wrong in the logic of my code.

One of friend is saying the above code wont work and its wrong. i couldn't able to find any usecase where my logic will fail (Exclude null check/null/empty nodes)

Just check the logic of my code and let me know.

My Logic is simple: use 2 stacks. In stack1 i always pushes the Left child first and then the right child and in stack2 i always pushes the right child first and left child second. initially loads stack1 while stack1 is non empty pop and pushes the corresponding right/left child nodes in stack2. For the above example my stack states should be like s1-B[2,3]T s2-B[7,6,5,4]T s1-B[8,9,10,11,12,13,14,15]T B-stack bottom T-Stack top. Pls check again. thanks.

Algorithm:

Use a modified BFS algorithm where instead of a single fifo queue two stacks are used stack1 is used to contain the nodes in the levels that are to be visited right-to-left, while stack2 contains the nodes that are to be visited left-to-right.

The list is initialized with the root node, and the first level (closest to root) is stored in stack1. So the first pass through stack1 will pull the first level in the appropriate order.

For the general case proof, assuming that the elements in stack1 are stored in the right order, pulling the nodes from stack1 for level N ensures that they are processed in right-to-left order. For each so processed node, the subtrees are stored in stack2 in first right, then left. This guarantees that the list of nodes as retrieved from stack2 for level N+1 has left-to-right order. The while loop completes when there are no more nodes at level N. At this point extracting the nodes from stack2 will retrieve all the nodes from level N+1 in left-to-right order.

Conversely, when pulling nodes from stack2 in each left-to-right level, stores the child nodes in stack1 first left, then right, ensuring that when they are pulled out in the next iteration in right-to-left order.

So basically the algorithm is proven to be sound. Now that does not ensure that the implementation is. In particular you are adding all NULL pointers to the stacks and that means that you will retrieve them, and then try to read through them.

This is already covered in another question.

See this stackoverview set of answers.