How to avoid reallocating an array of pointers when we dont know the exact size from start

Question

Im trying to design a binary tree like data-struct except there is no limit on children each node can have. Now within each node I can declare node struct as such:

struct node {
  int id;
  int num_children;
  struct node ** child;
};

My question is is there a way to avoid using:

1. realloc in this scenario so to not end up with alot of fragmentation in memory when you free and reallocate? everytime I add a new child will need to go though this process
2. statically allocate finite amount of pointers in the array which means (a) at a certain point I will not be able to add to it & (b) some nodes will not have children so its a waste

Answer 1

Start by allocating a fixed number of child pointers, and add a member to store the current capacity of the list. When you go to add a child to the list, if the list is a capacity, double the size. This minimized the amount of realocations you need to do.

So a node is modified to look like this:

struct node {
  int id;
  int capacity;
  int num_children;
  struct node ** child;
};

To create a node:

struct node *newnode = malloc(sizeof *newnode);
newnode->num_children = 0;
newnode->capacity = 10;
newnode->child = malloc(sizeof *newnode->child * newnode->capacity);

To add a child when at capacity:

if (current->capacity == current->num_children) {
    current->capacity *= 2;
    current->child = realloc(current->child, 
         sizeof *current->child * newnode->capacity);
}
current->child[current->num_children++] = new_child;

Note: error checking omitted for brevity.