Is there an insertion method for binary tree search faster than trivial?

Question

I’m trying to solve this problem in an online Judge.

The problem provides N integers that must be inserted, in the given order, into an insertion algorithm of a binary search tree. After Q queries are performed. For each query the code must tell who is the parent of the element that is provided in the input.

The entry will be as follows:

N (amount of values)
N₁ N₂ ... N_N (These are the values to be entered in the tree)
Q (the amount of consultations)
Q₁ Q₂ ... Q_Q (the integer representing the position of the given value in the input)

For the following example of input following the above specification:

5
3 1 4 2 5
2
2 5

The algorithm must form the following tree:

And with this tree must answer who is the parent of the second input element (the parent of 1) and the 5 input element (the parent of 5) separated by a space (no spaces after the last output value)

Example of expected output for example input:

3 4

To solve this problem I used the trivial binary tree insertion algorithm (What takes a worst-case complexity of O(n²)). During insertion, already save the parent of each node on a map.

But the code was judged to be time limit exceeded. Is there any insertion algorithm faster than the trivial (which keeps the order given in the input ... AVL trees will change the parents of each in the...)?

#include <cstdio>
#include <cstdlib>
#include <unordered_map>

struct node {
    int data;
    struct node *leftChild;
    struct node *rightChild;
};

void insertAndBuildFather(node **tree, int data, std::unordered_map<int, int> &father){
    struct node *tempNode = (struct node*) malloc(sizeof(struct node));

    tempNode->data = data;
    tempNode->leftChild = NULL;
    tempNode->rightChild = NULL;

    struct node *root = *tree;
    if(root == NULL){
        root = tempNode;
        father[root->data] = -1; //raiz nao tem pai
        *tree = root;
        return;
    }

    struct node *current = root;
    struct node *parent = NULL;

    while(1){
        parent = current;
        if(data < parent->data){
            current = current->leftChild;
            if(current == NULL){
                father[tempNode->data] = parent->data;
                parent->leftChild = tempNode;
                return;
            }
        }
        else{
            current = current->rightChild;
            if(current == NULL){
                father[tempNode->data] = parent->data;
                parent->rightChild = tempNode;
                return;
            }
        }

    }
}

int main ( void ) {
    int n;
    scanf("%d", &n);

    struct node* tree = NULL;
    std::unordered_map<int, int> father; //guarda os pais de cada valor
    int in[n + 1];
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &in[i]);
        insertAndBuildFather(&tree, in[i], father);
    }

    int q, qi;
    scanf("%d", &q);
    for (int i = 1; i < q; ++i) {
        scanf("%d", &qi);
        printf("%d ", father[in[qi]]);
    }
    scanf("%d", &qi);
    printf("%d\n", father[in[qi]]);
}

I appreciate any help =)

Answer 1

In general, the insertion in BST is O(N) in the worst case (which is a tree completely hanging to one side), which would actually give an algorithm O(N²). However, this can be easily circumvented by keeping where the largest node of the tree is and the smallest node of the tree. If the value to be inserted is greater than the largest node in the tree, then just put it to the right of the largest, and set it as the new largest, and do the same for if the value to be inserted is smaller than the smallest. This way, by entering an extreme value, you reduce the complexity from O(N) to O(1), receiving Accepted.

Below is AC example code:

// Gabriel Taets - Universidade Federal de Itajubá - gabrieltaets at gmail.com
#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
int tree[200100];
int n, hi = -1, lo = 0x3f3f3f3f;
int matricula[100010];
int pai[100010];

void insere(int node){
  if(tree[0] == -1){
    hi = lo = node;
    tree[0] = tree[1] = node;
    return;
  }
  int atual = 0;
  if(matricula[node] > matricula[hi]){
    int dir = hi*2+1;
    tree[dir] = node;
    pai[node] = hi;
    hi = node;
    return;
  }
  if(matricula[node] < matricula[lo]){
    int esq = lo*2;
    tree[esq] = node;
    pai[node] = lo;
    lo = node;
    return;
  }
  while(1){
    int dir = atual*2+1, esq = atual*2;
    if(matricula[node] > matricula[atual]){
      if(tree[dir] == -1){
        tree[dir] = node;
        pai[node] = atual;
        return;
      }
      atual = tree[dir];
      continue;
    }
    else {
      if(tree[esq] == -1){
        tree[esq] = node;
        pai[node] = atual;
        return;
      }
      atual = tree[esq];
      continue;
    }
  }
}

int main(){
  scanf("%d",&n);
  memset(tree,-1,sizeof tree);
  for(int i = 1; i <= n; i++){
    scanf("%d",&matricula[i]);
    insere(i);
  }
  int q;
  cin >> q;
  for(int i = 0; i < q; i++){
    int x;
    scanf("%d",&x);
    if(i) putchar(' ');
    printf("%d",matricula[pai[x]]);
  }
  putchar('\n');
  return 0;
}

A good tip too, it’s usually a bad idea to use dynamic allocation on these Online Judges issues (unless you’re training specifically on dynamic allocation). Dynamic Allocation is very error sensitive and can cause crashes where you don’t even know you might be wrong in your code. So if your goal with Online Judge is to train for programming competitions, I recommend you learn to represent trees as vectors, as in the code above.

I hope I’ve helped!