Inplace binary tree from spiral order traversal given in a doubly linked list

/* 
Example:

Spiral order traversal:
1-2-3-4-5-6-7-8

Tree:
            1
         /    \
       3       2
     /  \    /   \
   4     5  6     7
                   \
                    8

Algorithm:
  Using deque, push in one end and pop from other end, when the level 
  changes, change the directions of push and pop
*/

#include <cstdio>
#include <deque>

struct DoublyLinkedListNode
{
  int el;
  DoublyLinkedListNode *left;
  DoublyLinkedListNode *right;

  explicit DoublyLinkedListNode(int _el) : 
              el(_el), left(NULL), right(NULL) {}
};

typedef DoublyLinkedListNode* DoublyLinkedList;
typedef DoublyLinkedListNode* Tree;

struct DequeNode
{
  DoublyLinkedListNode *dlNode;
  int level;

  DequeNode(DoublyLinkedListNode *_dlNode, int _level) : 
                      dlNode(_dlNode), level(_level) {}
};

void spiralDoublyLinkedList2BinaryTree(DoublyLinkedList d) 
{
  if (!d) return;

  std::deque<DequeNode> q;

  q.push_back(DequeNode(d, 0));

  DoublyLinkedListNode *right, 
                       *left,
                       *iter = d;

  bool rightToLeft = true;

  int currentLevel = 0;

  while(!q.empty()) {

    DequeNode dqNode = rightToLeft ? q.back() : q.front();

    if (dqNode.level != currentLevel) {
      rightToLeft = !rightToLeft;
      dqNode = rightToLeft ? q.back() : q.front();
      currentLevel = dqNode.level;    
    }

    if (rightToLeft) {
      q.pop_back();
    } else {
      q.pop_front();
    }

    DoublyLinkedListNode *tmpDlNode = dqNode.dlNode;

    if (iter == NULL) {
      tmpDlNode->right = tmpDlNode->left = NULL;
    } else {

      left = iter->right;
      right = left ? left->right : NULL;

      if (rightToLeft) {
        tmpDlNode->left = right;
        tmpDlNode->right = left;

        if (left) {
          q.push_front(DequeNode(left, currentLevel + 1));
        }

        if (right) {
          q.push_front(DequeNode(right, currentLevel + 1));
        }

      } else {

        tmpDlNode->left = left;
        tmpDlNode->right = right;

        if (left) {
          q.push_back(DequeNode(left, currentLevel + 1));
        }

        if (right) {
          q.push_back(DequeNode(right, currentLevel + 1));
        }
      }

      iter = right;
    }
  }
}

void spiralOrderTraversal(Tree t)
{
  if (!t) return;

  std::deque<DequeNode> q;

  q.push_back(DequeNode(t, 0));

  bool rightToLeft = true ;

  int currentLevel = 0;

  while(!q.empty()) {

    DequeNode dqNode = rightToLeft ? q.back() : q.front();

    if (dqNode.level != currentLevel) {
      rightToLeft = !rightToLeft;
      dqNode = rightToLeft ? q.back() : q.front();
      currentLevel = dqNode.level;    
    }

    if (rightToLeft) {
      q.pop_back();
    } else {
      q.pop_front();
    }

    DoublyLinkedListNode *tmpDlNode = dqNode.dlNode;

    printf("%d", tmpDlNode->el);

    if (rightToLeft) {

      if (tmpDlNode->left) {
        q.push_front(DequeNode(tmpDlNode->left, currentLevel + 1));
      }

       if (tmpDlNode->right) {
        q.push_front(DequeNode(tmpDlNode->right, currentLevel + 1));
      }

    } else {

     if (tmpDlNode->right) {
        q.push_back(DequeNode(tmpDlNode->right, currentLevel + 1));
      }

      if (tmpDlNode->left) {
        q.push_back(DequeNode(tmpDlNode->left, currentLevel + 1));
      }
    }
  }
  printf("\n");

}

DoublyLinkedList makeList(int n) 
{
  DoublyLinkedListNode *d = new DoublyLinkedListNode(1);

  DoublyLinkedListNode *tmpDlNode = d;

  for (int i = 2; i <= n; ++i) {
    tmpDlNode->right = new DoublyLinkedListNode(i);
    tmpDlNode->right->left = tmpDlNode;
    tmpDlNode = tmpDlNode->right;
  }

  return d;
}

void printList(DoublyLinkedList d)
{
  while (d) {
    printf("%d", d->el);
    d = d->right;
  }

  printf("\n");
}

int main(int argc, char const *argv[])
{
  DoublyLinkedList d = makeList(8);

  printf("Before spiralOrderTraversal : ");
  printList(d);
  spiralDoublyLinkedList2BinaryTree(d);

  printf("After  spiralOrderTraversal : ");
  spiralOrderTraversal(d);

  return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s