Data structure, Thanks. 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. 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. 2. Output each tree node’s level in preorder. Here we print in preorder(i.e., root, left_subtree, then right_subtree). 2. Output each tree node’s level in postorder. Here we print in postorder(i.e., left_subtree, root, then right_subtree). Could refer to slides 19-25 in Chapter 5. 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 preorder and postorder to calculate and output each node’s data and level in preorder and postorder respectively. You need to complete four functions. Tree searchPoint(Tree root, int key); Tree insert(Tree root, int key); void preorder(Tree root); void postorder(Tree root); Sample Input 1: 5 10 20 30 50 40 Sample Output 1: preorder 10 1 20 2 30 3 50 4 40 5 postorder 40 5 50 4 30 3 20 2 10 1 Sample Input 2: 11 2 1 4 10 3 5 7 8 9 6 0 Sample Output 2: preorder 2 1 1 2 0 3 4 2 3 3 10 3 5 4 7 5 6 6 8 6 9 7 postorder 0 3 1 2 3 3 6 6 9 7 8 6 7 5 5 4 10 3 4 2 2 1 Code Template: #include #include 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 preorder(Tree root) { /* Fill in your code here… print in the format of printf(“%d %dn”, root->data, root->level); */ } void postorder(Tree root) { /* Fill in your code here… print in the format of printf(“%d %dn”, root->data, root->level); */ } 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 { scanf(“%d”, &key); root = insert(root, key); } // pre order printf(“preordern”); preorder(root); // post order printf(“postordern”); postorder(root); return 0; }