c implementation of triplets problem on interview street [ first attempt , not at all optimized ]

triplets.c

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct node {
    int data;
    int frequency;
    struct node* left;
    struct node* right;
};

struct node* getnode(int data, int frequency) {
    struct node* newnode = (struct node*) malloc(sizeof(struct node));
    newnode->left = NULL;
    newnode->right = NULL;
    newnode->data = data;
    if(frequency < 0) 
      newnode->frequency = 0;
    else 
    	newnode->frequency = frequency;    
    return newnode;
}

void insert(struct node* root, int new_data, int frequency) {
    if(new_data > root->data) {
        if(root->right)
        	insert(root->right, new_data, frequency);
        else
            root->right = getnode(new_data, frequency);
    }
    else if(new_data < root->data) {
        if(root->left)
        	insert(root->left, new_data, frequency);
        else
            root->left = getnode(new_data, frequency);
            
    }
    else if(new_data == root->data) {
        if(frequency < 0)
        root->frequency = 0;
    }
}

int getSum(struct node* root) {
    if(!root)
        return 0;
    else {
        return root->frequency + getSum(root->left) + getSum(root->right);
    }
}

int main() {

    int size, t;
    int d[100000];
    int middle;
    int frequency = 1;
    int i, j, k, lower=0, higher=0, triplets=0;
    int total_lower, total_higher;
    scanf("%d", &size);
    for(i = 0; i < size; i++) {
        scanf("%d", &d[i]);
    }
    for(j = 1; j < size-1; j++) {
        middle = abs(d[j]);
        lower = 0;
        higher = 0;
        
        struct node* root_l = getnode(middle, 1);
        frequency = 1;
        for(i = 0 ; i < j; i++) {
			insert(root_l, abs(d[i]), frequency);
    	}
        
        struct node* root_h = getnode(middle, 1);
        frequency = 1;
        for(i = j+1 ; i < size; i++) {
            if(d[i] == middle) {
            	frequency = -1;
                continue;
            }
			insert(root_h, abs(d[i]), frequency);
    	}
        
        lower = getSum(root_l->left);
        higher = getSum(root_h->right);
        triplets += lower * higher ;
    }
    printf("%d", triplets);
    return 0;
}