按输入顺序建立二叉搜索树，并搜索某一结点，输出其父结点。
输入格式:

输入有三行：
第一行是n值，表示有n个结点；
第二行有n个整数，分别代表n个结点的数据值；
第三行是x，表示要搜索值为x的结点的父结点。
输出格式:

输出值为x的结点的父结点的值。
若值为x的结点不存在，则输出：It does not exist.
若值为x的结点是根结点，则输出：It doesn’t have parent.
输入样例:

2
20
30
20

输出样例:

It doesn’t have parent.

输入样例：

2
20
30
30

输出样例:

20

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int n;

int tr[N], fa[N];
bool st[N];

void buildTree(int x, int u) {
    if (tr[u] == 0) {
        tr[u] = x;
        fa[x] = tr[u / 2];
        return;
    }

    if (tr[u] <= x)
        buildTree(x, u << 1 | 1);
    else
        buildTree(x, u << 1);

}

int main() {
    cin >> n;

    for (int i = 1; i <= n; ++ i) {
        int x;
        cin >> x;

        buildTree(x, 1);
        st[x] = true;
    }

    int x;
    cin >> x;

    int pa = fa[x];

    if (st[x] == false) {
        cout << "It does not exist.\n";
    } else if (pa == 0) {
        cout << "It doesn't have parent.\n";
    } else {
        cout << pa << "\n";
    }

    return 0;
}