# 50113. Ternary Search Tree

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

Build a ternary search tree with an array of distinct positive integers.

You are given an array of $N$ unique and positive integers. Please convert the array into a ternary search tree.

Each node of a ternary search tree stores at most two integers -- the smaller $S$ and the larger $L$. Each node has three pointers, left, mid, and right, and each pointer points to a subtree. All integers in the left subtree are smaller than $S$, all integers in the mid subtree are larger than S and smaller than L, and all integers in the right subtree are larger than L. Note that if a node stores only one integer k, you need to store it as the larger one, and set the small one to -1.

When the integer sequence is {9, 5, 2, 7}, we build the ternary tree as follows. Note that all pointers that do not link to any node must be set to NULL.

example

We define a tree node as follows.

1234typedef struct node{    int small,large;    struct node *left,*mid,*right;} Node;


Please write a function to construct the ternary tree. The prototype of the function is as followed.

1Node*ConstructTree(int sequence[],int N);


You may use the following main function to test your program.

12345678910111213141516171819202122#include <stdio.h>#include "construct.h"#define MAXN 32768int sequence[MAXN];void PrintTree( Node *root ){    if (root == NULL)        return;    printf("%d %d\n", root->small, root->large);    PrintTree(root->left);    PrintTree(root->mid);    PrintTree(root->right);    return;}int main(){    int N;    scanf("%d", &N);    for (int i=0; i<N; i++)        scanf("%d", &sequence[i]);    Node *tree = ConstructTree( sequence, N );    PrintTree( tree );    return 0;}


The construct.h is as followed.

12345678#ifndef CONSTRUCT#define CONSTRUCTtypedef struct node{    int small,large;    struct node *left,*mid,*right;}Node;Node*ConstructTree(int sequence[],int N);#endif


• 10 points: $N = 1$.
• 10 points: $N = 2$.
• 20 points: $N = 4$.
• 60 points: Nothing is guaranteed.

## Input Format

The input contains only one test case. The first line contains one integers $N$, representing the number of sequence. The second line contains $N$ integers, $s_{0}$, $s_{1}$, … , $s_{n-1}$, representing the value of index.

• $0 \lt N \lt 32768$.

## Output Format

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

## Compile

gcc -std=c99 -O2 -c construct.cgcc -std=c99 -O2 -c main.c -lmgcc -std=c99 -O2 main.o construct.o


## Sample Input 1

19


## Sample Output 1

-1 9


## Sample Input 2

29 5


## Sample Output 2

5 9


## Sample Input 3

49 5 2 7


## Sample Output 3

5 9-1 2-1 7


## Sample Input 4

65 1 18 20 42 22


## Sample Output 4

1 518 2022 42