#include <iostream>
using namespace std;
class Node
{
public:
int data;
Node * left;
Node * right;
};
class BST
{
Node * root;
Node * head; // head of list
// Utility functions
Node * newNode (int);
void insert (Node **, int);
Node * treeToList (Node *);
Node * append (Node *, Node *);
void join (Node *, Node *);
public:
BST ()
{
root = NULL;
}
// Public functions to be called from main
void insert (int);
void toList ();
void printList ();
};
Node * BST :: newNode (int data)
{
Node * node = new Node;
node -> data = data;
node -> left = NULL;
node -> right = NULL;
return node;
}
void BST :: insert (int data)
{
insert (&root, data);
}
void BST :: insert (Node ** root, int data)
{
if (!(*root))
*root = newNode (data);
else
{
if (data <= (*root) -> data)
insert (&((*root) -> left), data);
else
insert (&((*root) -> right), data);
}
}
void BST :: toList ()
{
head = treeToList (root);
}
Node * BST :: treeToList (Node * root)
{
if (!root) return NULL;
// Convert the left subtree into circular linked list
Node * left = treeToList (root -> left);
// Convert the right subtree into circular linked list
Node * right = treeToList (root -> right);
// Construct single node linked list out of root
root -> left = root;
root -> right = root;
// Append root to the list of left subtree
left = append (left, root);
// Append the list of right subtree to the list
left = append (left, right);
return left;
}
Node * BST :: append (Node * a, Node * b)
{
if (!a) return b;
if (!b) return a;
// Get last node of first list (to join with second list)
Node * aLast = a -> left;
// Get last node of second list (to join with first list)
Node * bLast = b -> left;
// Join last node of first list to the head of second list
join (aLast, b);
// Join last node of second list to the head of first list
join (bLast, a);
// a is the head of the circular list
return a;
}
void BST :: join (Node * a, Node * b)
{
// Join last node of a to head of b
a -> right = b;
// Join last node of b to head of a
b -> left = a;
}
void BST :: printList ()
{
if (!head) return;
Node * cur = head;
while (cur)
{
cout << cur -> data << " ";
cur = cur -> right;
if (cur == head)
break;
}
cout << endl;
}
int main (void)
{
BST bst;
bst.insert (8);
bst.insert (3);
bst.insert (10);
bst.insert (1);
bst.insert (6);
bst.insert (14);
bst.insert (4);
bst.insert (7);
bst.insert (13);
bst.toList ();
bst.printList ();
return 0;
}