/*
 * Author: Titus Winters <titus@cs.ucr.edu>
 * 
 * This is a sample solution for the treeToList problem assigned in CS 14
 * during Fall 2003.  It implements a function that recursively transmutes
 * a Binary Search Tree into a sorted, circular, doubly-linked list.
 *
 */

#include <iostream>

using namespace std;

#define NUMNODES 8

class Node
{
public:
  int val;
  Node* prev;
  Node* next;
};

// If we are given two circular, sorted, doubly-linked lists
// such that everything in "small" is less than everything in "large"
// then this is awful easy.
Node* merge(Node* small, Node* large)
{
  // So we don't dereference anything we shouldn't have
  if (small == NULL) return large;
  if (large == NULL) return small;

  // Get pointers to the maximum elements.  This is simple
  // because of the structure of the linked lists
  Node* sMax = small->prev;
  Node* lMax = large->prev;

  // Now merge the two loops together into one.  Draw it on paper
  // if you don't see why this works.
  sMax->next = large;
  large->prev = sMax;

  small->prev = lMax;
  lMax->next = small;

  // And we're done
  return small;
}

// Given a BST, convert it into a circular, sorted, doubly-linked
// list and return a pointer to the minimum element of that list.  
// (There is no head, so min is a useful choice.)
Node* treeToList(Node* tree)
{
  // Base case for nothing in the tree
  if (tree == NULL) return tree;

  // Base case for a simple, single tree.  This is perhaps not
  // strictly necessary with the above base case and 
  // careful code, but I think it works better this way.
  if (tree->prev == NULL and tree->next == NULL)
    {
      tree->prev = tree;
      tree->next = tree;
      return tree;
    }

  // Now do the conversion on the child trees, and store the return
  // values from those calls.  Remember that the return values there
  // are the minimum element of the circular, sorted, doubly-linked list
  Node* left = treeToList(tree->prev);
  Node* right = treeToList(tree->next);
  
  // Now make the current node a circular sorted doubly-linked list . . .
  tree->prev = tree;
  tree->next = tree;

  // . . . so we can call merge on it and the left side
  left = merge(left, tree);

  // Then we merge the (now extended) left side with the right side and
  // we are done

  return merge(left, right);
}


Node* insert(Node* root, int val)
{
  // Base case: we've fallen off the tree, do the insertion.
  if (root == NULL) 
    {
      Node* newNode = new Node;
      newNode->val = val;
      return newNode;
    }
  // If we need to insert on the left side . . .
  if (val < root->val)
    {
      root->prev = insert(root->prev, val);
      return root;
    }
  // This else isn't needed, but I place it here for symmetry so the
  // code "looks" right.  If the two operations weren't symmetric, I
  // wouldn't do this.
  else
    {
      root->next = insert(root->next, val);
      return root;
    }
}

int main()
{
  // This code is only here for testing purposes.  The actual 
  // portion that was important for this assignment is treeToList
  // and merge.

  // Create a binary tree using our little tree insertion function above
  Node* root = insert(NULL, 10);
  root = insert(root, 5);
  root = insert(root, 3);
  root = insert(root, 6);
  root = insert(root, 15);
  root = insert(root, 20);
  root = insert(root, 25);
  root = insert(root, 30);

  // Convert it
  Node* head = treeToList(root);

  // Print it out forward
  for (int i = 0; i < NUMNODES; ++i)
    {
      cout << head->val << endl;
      head = head->next;
    }
  
  // Back up one (so we aren't at the head again)
  head = head->prev;

  // Print it out backward.
  for (int i = 0; i < NUMNODES; i++)
    {
      cout << head->val << endl;
      head = head->prev;
    }
}