Ternary Search Tree

[littlehug]

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

Task Description

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.

figure

We define a tree node as follows.

typedef 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.

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

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

#include <stdio.h>
#include "construct.h"
#define MAXN 32768
int 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.

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

Subtasks

• 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, s0, s1, … , sn-1, representing the value of index.

• N < 32768

  Output Format

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

Sample Input 1

1
9

Sample Output 1

-1 9

Sample Input 2

2
9 5

Sample Output 2

5 9

Sample Input 3

4
9 5 2 7

Sample Output 3

5 9
-1 2
-1 7

Sample Input 4

6
5 1 18 20 42 22

Sample Output 4

1 5
18 20
22 42