Binary search large tree in C I tested creating 1 billion (1,000,000,000) nodes and lookups are fast. You can ask for a node by node_id.

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;time.h&gt;

typedef struct node {
    int node_id;
    int data;
    char *name;
    struct node *left;
    struct node *right;
} node;


node *newNode(int data, char *name, int node_id) {
    node *new_node = malloc(sizeof(node));
    new_node-&gt;data = data;
    new_node-&gt;name = name;
    new_node-&gt;node_id = node_id;
    new_node-&gt;right = new_node-&gt;left = NULL;
    return new_node;
}

node *insert_node(node *root, int data, int node_id, char *name) {
    if (root == NULL)
        return newNode(data, name, node_id);
    else {
        node *cur;
        if (node_id &lt; root-&gt;node_id) {
            cur = insert_node(root-&gt;left, data, node_id, name);
            root-&gt;left = cur;
        } else if (node_id &gt; root-&gt;node_id) {
            cur = insert_node(root-&gt;right, data, node_id, name);
            root-&gt;right = cur;
        }
    }
    return root;
}


node *find_node_data(node *root, int node_id) {
    if (root == NULL)
        return NULL;
    else if (root-&gt;node_id == node_id)
        return root;
    else if (root-&gt;node_id &gt; node_id)
        return find_node_data(root-&gt;left, node_id);
    else
        return find_node_data(root-&gt;right, node_id);
}

void print(node *np) {
    if (np) {
        print(np-&gt;left);
        printf("(%d, %d, %s)", np-&gt;node_id, np-&gt;data, np-&gt;name);
        print(np-&gt;right);
    }
}

int main() {
    int T = 1000000000; //test case 1000000000 nodes
    int data, node_id;
    //printf("Input number of nodes:");
    //scanf("%d", &amp;T);
    node *root = NULL;
    srand(time(NULL));
    while (T-- &gt; 0) {
        //printf("Input data. %d:", T);
        //scanf("%d %d", &amp;data, &amp;node_id);
        int r = rand() % 1000000000;
        int r2 = rand() % 1000000000;
        root = insert_node(root, r, r2, "Rosencrantz");
    }
    //print(root);
    printf("\n");
    printf("Find data at node:");
    scanf("%d", &amp;T);
    printf("node data %d %s", find_node_data(root, T)-&gt;data, find_node_data(root, T)-&gt;name);
    return 0;
}
node *cur is not necessary. A c idiom is

if (node_id &lt; root-&gt;node_id) {
    root-&gt;left = insert_node(root-&gt;left, data, node_id, name);

find_node_data is unnecessarily recursive. The compiler may understand that it is a tail recursion, and optimize it out, but it always better to be explicit:

    while (root) {
        if (root-&gt;node_id == node_id) {
            break;
        }
        root = root-&gt;node_id &gt; node_id? root-&gt;left: root-&gt;right;
    }
    return root;


Note the insertion may also be made iterative, although much less elegant.
The line

printf("node data %d %s", find_node_data(root, T)-&gt;data, find_node_data(root, T)-&gt;name);


looks really strange. Why do you call find_node_data twice, and why don't you call print, which you are already defined?