Binary search large tree in C

Question

I tested creating 1 billion (1,000,000,000) nodes and lookups are fast. You can ask for a node by node_id.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
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->data = data;
 new_node->name = name;
 new_node->node_id = node_id;
 new_node->right = new_node->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 < root->node_id) {
 cur = insert_node(root->left, data, node_id, name);
 root->left = cur;
 } else if (node_id > root->node_id) {
 cur = insert_node(root->right, data, node_id, name);
 root->right = cur;
 }
 }
 return root;
}
node *find_node_data(node *root, int node_id) {
 if (root == NULL)
 return NULL;
 else if (root->node_id == node_id)
 return root;
 else if (root->node_id > node_id)
 return find_node_data(root->left, node_id);
 else
 return find_node_data(root->right, node_id);
}
void print(node *np) {
 if (np) {
 print(np->left);
 printf("(%d, %d, %s)", np->node_id, np->data, np->name);
 print(np->right);
 }
}
int main() {
 int T = 1000000000; //test case 1000000000 nodes
 int data, node_id;
 //printf("Input number of nodes:");
 //scanf("%d", &T);
 node *root = NULL;
 srand(time(NULL));
 while (T-- > 0) {
 //printf("Input data. %d:", T);
 //scanf("%d %d", &data, &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", &T);
 printf("node data %d %s", find_node_data(root, T)->data, find_node_data(root, T)->name);
 return 0;
}

• Olivier Jacot-Descombes: What is your question?
• vnp: @OlivierJacot-Descombes At this exchange, there is always an implicit question: "Please review".

Answer 1

• node *cur is not necessary. A c idiom is

  if (node_id < root->node_id) {
   root->left = insert_node(root->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->node_id == node_id) {
   break;
   }
   root = root->node_id > node_id? root->left: root->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)->data, find_node_data(root, T)->name);
  

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