#include <iostream>

using namespace std;
int op_select = 0;
struct NodeT
{
	int data;
	NodeT* left;
	NodeT* right;
	int size;

};

int size(NodeT* p)
{
	if (p == NULL)
		return 0;
	else
		return(size(p->left) + 1 + size(p->right));
}
 NodeT* newNode(int data)
 {
	 NodeT*  p= new NodeT();
	 p->data = data;
	 p->left = NULL;
	 p->right = NULL;
	 return p;
 }
 NodeT* buildPBT(int a[], int start, int end)
 {
	 if (end >= start)
	 {
		 int mid = (start + end + 1) / 2;
		 NodeT* root = newNode(a[mid]);
		 root->left = buildPBT(a, start, mid - 1);
		 root->right = buildPBT(a, mid + 1, end);
		return root;
	 }
	 return NULL;
  }

 void preOrder(NodeT* p)
 {
	 if ( p== NULL)
		 return;
	 cout << p->data << " ";
	 preOrder(p->left);
	 preOrder(p->right);
 }
 void printInorder(NodeT* p)
 {
	 if (p == NULL)
		 return;
	 printInorder(p->left);
	 cout << p->data << " ";
	 printInorder(p->right);
 }
 NodeT* OS_SELECT(NodeT* tree, int index)
 {
	 int r = size(tree->left)+ 1;
	 op_select++;
	 if (index == r)
	 {
		 return tree;
		 op_select++;
	 }
	 else if (index < r)
	 {
		 return OS_SELECT(tree->left, index);
		 op_select++;
	 }
	 else
	 {
		 return OS_SELECT(tree->right, index);
		 op_select++;
	 }
 }
NodeT* minValueNode(NodeT* node)
{
	 NodeT* current = node;
	 /* loop down to find the leftmost leaf */
	 while (current && current->left != NULL)
		 current = current->left;
	 return current;
}
 NodeT* OS_DELETE(NodeT* tree, int index)
 {
	 NodeT* p = OS_SELECT(tree, index);
	 if (tree == NULL) return tree;
	 // If the key to be deleted is smaller than the root's key,
	 // then it lies in left subtree
	 if (p->data < tree->data)
		 p->left = OS_DELETE(p->left, index);
	 // If the key to be deleted is greater than the root's key,
	 // then it lies in right subtree
	 else if (p->data > tree->data)
		 p->right = OS_DELETE(p->right, index);
	 // if key is same as root's key, then This is the node
	 // to be deleted
	 else
	 {
		 // node with only one child or no child
		 if (p->left == NULL)
		 {
			 NodeT* temp = p->right;
			 free(p);
			 return temp;
		 }
		 else if (p->right == NULL)
		 {
			 NodeT* temp = p->left;
			 free(p);
			 return temp;
		 }
		 // node with two children: Get the inorder successor (smallest
		 // in the right subtree)
		 NodeT* temp = minValueNode(p->right);
		 // Copy the inorder successor's content to this node
		 p->data = temp->data;
		 // Delete the inorder successor
		 p->right = OS_DELETE(p->right, temp->data);
	 }
	 return p;
 }
 void demoBuildTree()
 {
	 int a[11] = { 1,2,4,6,7,9,11,15,17,18,23 };
	 cout << "Convert List to PBT" << "\n";
	 NodeT* root = buildPBT(a, 0, 10);
	 printInorder(root);
	 cout << "\n";
 }
 void demoOS_Select()
 {
	 int a[11] = { 1,2,4,6,7,9,11,15,17,18,23 };
	 NodeT* root = buildPBT(a, 0, 10);
	 printInorder(root);
	 cout << OS_SELECT(root, 9)->data;
 }
 int main()
 {
	 demoBuildTree();
	// demoOS_Select();
 }