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

Print ancestors of a given binary tree node without recursion

#include <stdio.h>
#include <stack>

struct TreeNode
{
  TreeNode *left, *right;
  int el;

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

typedef TreeNode* Tree;

struct StackNode
{
  TreeNode *node;
  bool visited;

  explicit StackNode(TreeNode *t) : node(t), visited(false) {}

  ~StackNode() {
    delete node;
  }

  private:
  StackNode(const StackNode &);
  StackNode operator=(const StackNode &);


};

void printAncestor(Tree t, int key) 
{
  std::stack<StackNode *> stack;

  if (!t || t->el == key) return;

  stack.push(new StackNode(t));

  TreeNode *tmp = t->left;

  while (!stack.empty()) {

    if (tmp) {

      if (tmp->el == key) {
        //Key found print the ancestors
        while (!stack.empty()) {
          StackNode *s = stack.top();
          printf("%d ", s->node->el);
          stack.pop();
        }
      } else {
        stack.push(new StackNode(tmp));
        tmp = tmp->left;
      }
    } else {
      //Traverse the right subtree, if not traversed
      StackNode *s = stack.top();
      if (!s->visited) {
        s->visited = true;
        tmp = s->node->right;
      } else {
        stack.pop();
      }
    }
  }

}

Tree newTree() 
{
  TreeNode *root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);
  root->left->left = new TreeNode(4);
  root->left->right = new TreeNode(5);
  root->right->left = new TreeNode(6);
  root->right->right = new TreeNode(7);
  root->left->left->left = new TreeNode(8);
  root->left->right->right = new TreeNode(9);
  root->right->right->left = new TreeNode(10);

  return root;
}

int main(int argc, char const *argv[])
{
  Tree t  = newTree();

  for (int i = 1; i <= 11; ++i) {
    printf("%d: ", i);
    printAncestor(t, i);
    printf("\n");
  }
  
  return 0;
}