Time limit: 5000ms
Memory limit: 256mb

Description:
In this exercise, you are required to fulfill the following two tasks.

1. Construct a binary search tree(BST).
Initially, the BST is empty. Then given a sequence of distinct integers, you need to insert them into the BST one by one. Lecture notes show more details on insertion.

2. Output each tree node's level in preorder.
We define the level of a node(u) as follows:
If u is the root, u.level = 1;
Otherwise, for a node u with parent node v, u.level = v.level + 1.
Here we print in preorder(i.e., root, left_subtree, then right_subtree) because the recursion used to calculate each node's level is the same as preorder traversal. Precisely, parent nodes determine their children's level, so the root must be visited before subtrees.

The main function has been provided. It first asks the user to input the integers and constructs the BST at the same time. Then it invokes the recursive function print_level to calculate and output each node's data and level in preorder. 

You need to complete three functions.

Tree searchPoint(Tree root, int key);

Tree insert(Tree root, int key);

void print_level(Tree root);

Sample Input 1:
5
10 20 30 50 40

Sample Output 1:
Input the number of integers:
Input these integers:
10 1
20 2
30 3
50 4
40 5

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

Sample Output 2:
Input the number of integers:
Input these integers:
2 1
1 2
0 3
4 2
3 3
10 3
5 4
7 5
6 6
8 6
9 7


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 level;
} 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...
    */
}

void print_level(Tree root)
{
    printf("%d %d\n", root->data, root->level);
    /*
        Fill in your code here...
        Calculate children's level and then make recursive calls.
    */
}

int main()
{
    int n, key;
    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);
    }
    root->level = 1;
    print_level(root);
    return 0;
}