Time limit: 5000ms
Memory limit: 256mb

Description:
This is an optional problem. You won't lose any mark if you skip it.

In this exercise, you are required to complete the function kthsmallest based on the first exercise(Binary Search Tree).

int kthsmallest(Tree root, int k);
Return the k-th smallest integer in the BST. You can assume that the answer must exist (1<=k<=n).

In the tree_node structure, the field "size" means the number of nodes in the subtree rooted by the node, including the subtree root.

Sample Input 1:
5
10 20 30 50 40
3

Sample Output 1:
Input the number of integers:
Input these integers:
30

Sample Input 2:
11
2 1 4 10 3 5 7 8 9 6 0
1

Sample Output 2:
Input the number of integers:
Input these integers:
0

Hint:
You may need to invoke another function cal_size first to initialize each node's size. Anyway, you could design and implement it as you like.

Code Template:

#include <stdio.h>
#include <stdlib.h>

typedef struct tree_node{
    struct tree_node *left_child;
    struct tree_node *right_child;
    int data;
    int size;
} Node;

typedef Node* Tree;

Tree searchPoint(Tree root, int key)
{
    /*
        Fill in your code here...
    */
}

Tree insert(Tree root, int key)
{
    Tree ptr, point;
    point = searchPoint(root, key);
    /*
        Fill in your code here...
    */
}

int kthsmallest(Tree root, int k)
{
    /*
        Fill in your code here...
    */
}

int main()
{
    int n, key, k;
    Tree root = NULL;
    printf("Input the number of integers:\n");
    scanf("%d", &n);
    printf("Input these integers:\n");
    for(int i=0; i<n; i++)
    {
        scanf("%d", &key);
        root = insert(root, key);
    }
    //cal_size(root);
    scanf("%d", &k);
    key = kthsmallest(root, k);
    printf("%d\n", key);
    return 0;
}