# 50106. Construct a Binary Search Tree

## I'm a slow walker, but I never walk backwards.

Write a function to construct a binary search tree according to the weight or the height.

You are given $N$ students’ names, heights and weight. You need to construct a binary search tree according to the compiler flag.

• If the flag HEIGHT is defined, you need to construct the binary search tree according to the students’ heights.
• If the flag WEIGHT is defined, you need to construct the binary search tree according to the students’ weights.

For example, we are given students’ informations as follows:

Name Height Weight
John 175 70
Tom 160 80
Mary 165 45

If we compile with flag -DHEIGHT, we need to construct the binary search tree according to the students’ heights as follows:

figure

And, If we compile with flag -DWEIGHT, we need to construct the binary search tree according to the students’ weights as follows:

figure

## Note

It is guaranteed that all the heights and all the weights are different. You need to construct the binary search tree in the order of the students appear in the input. Exactly one of the HEIGHT and WEIGHT flag will be defined. All pointers that do not link to any node must be set to NULL.

The binary search tree sample code from the textbook: bstree.c

Please construct the binary search tree in the function, Node *ConstructBSTree( … ), then return the pointer of the root. The main program and the prototype of function ConstructBSTree are as followed:

### construct.h

1234567891011#ifndef CONSTRUCT#define CONSTRUCTtypedef struct Node{    char name[16];    int height;    int weight;    struct Node *left, *right;} Node; Node *ConstructBSTree(int N, char name[][16], int height[], int weight[]);#endif


### main.c

12345678910111213141516171819202122232425262728#include <stdio.h>#include "construct.h" #define MAXN 1024char name[MAXN][16];int height[MAXN];int weight[MAXN]; void PrintBSTree( Node *root ){    if (root == NULL)        return;    printf("%s\n", root->name);    PrintBSTree(root->left);    PrintBSTree(root->right);    return;} int main(){    int N;    scanf("%d", &N);    for (int i=0; i<N; i++)        scanf("%s %d %d", name[i], &height[i], &weight[i]);     Node *tree = ConstructBSTree( N, name, height, weight );     PrintBSTree( tree );    return 0;}


## Compile

gcc -std=c99 -O2 -DHEIGHT main.c construct.c -o test1  gcc -std=c99 -O2 -DWEIGHT main.c construct.c -o test2


• 10 points: There is only one student.
• 20 points: There are no more than three students.
• 70 points: There is no guaranteed on the number of students.

## Input Format

The input contains only one test case. The first line contains an integers $N$, representing the number of student. For the following $N$ lines, each line contains a string and two integers which are the student’s name, height and weight.

• $0 \lt N \lt 1025$
• The length of a student’s name is less than 16, and the name doesn't contain any whitespaces.

## Output Format

Print all the names of nodes in the binary search tree by pre-ordering, and each node in a line.

## Sample Input 1

Compile with flag -DHEIGHT

3John 175 70Tom 160 80Mary 165 45


## Sample Output 1

JohnTomMary


## Sample Input 2

Compile with flag -DWEIGHT

3John 175 70Tom 160 80Mary 165 45


## Sample Output 2

JohnMaryTom