#include <iostream.h>

struct TreeNode
{
    int        info;     // data stored
    int        size;     // size of subtree (root included)
    TreeNode * left;     // left subtree
    TreeNode * right;    // right subtree

    TreeNode(int val, TreeNode * lptr, TreeNode * rptr)
	: info(val),
	  size(1), left(lptr), right(rptr)
    { }	  
};

void Print(TreeNode * t)
{
    if (t != NULL)
    {
	Print(t->left);
	cout << " [ " << t->info << " " << t->size << " ]";
	Print(t->right);
    }
}

void SetSize(TreeNode * t)
// precondition:  t != NULL
// postcondition: The size field of every node in the tree t
//                has been set to the size of that node's subtree    
{
    int leftSize  = 0;   // size of left subtree
    int rightSize = 0;   // size of right subtree
    
    if (t != NULL)
    {
	SetSize(t->left);
	SetSize(t->right);

	if (t->left != NULL)  leftSize  = t->left->size;
	if (t->right != NULL) rightSize = t->right->size;

	t->size = leftSize + rightSize + 1;
    }
}

int FindKth(TreeNode * t, int k)
// precondition:  t is not NULL, the size fields of all nodes in t
//                are correctly initialized.
//                1 <= k <= t->size
// postcondition: returns the kth value in t
{
    int leftSize = 0;
    if (t->left != NULL) leftSize = t->left->size;

    if       (k == leftSize + 1) return t->info;
    else if  (k <  leftSize + 1) return FindKth(t->left,k);
    else                         return FindKth(t->right,
						k - (leftSize + 1));
}

int main()
{
    TreeNode * t = new TreeNode(50,
		       new TreeNode(25,
			   new TreeNode(12,NULL,NULL),
			   new TreeNode(37,
			       new TreeNode(30,NULL,NULL),
			       NULL)),
				    
		       new TreeNode(75,
			   new TreeNode(62,NULL,NULL),
			   new TreeNode(88,NULL,NULL)));

    cout << "before sizing " << endl;
    Print(t);

    cout << endl << "after sizing " << endl;
    SetSize(t);
    Print(t);

    cout << endl;


    int k, kthValue;
    while (true)
    {
	cout << "enter k for k-th value (0 to exit) ";
	cin >> k;
	if (k == 0) break;
	
	kthValue = FindKth(t,k);
	cout << k << "-th value = " << kthValue << endl;
    }
}