linked lists – binary trees and pre-assigned nodes

I want to design a binary tree with pre-assigned nodes, to avoid calling malloc / free every time I want to insert / delete a node. The problem is that I do not know in advance how many nodes the tree will have, so I think I need to assign a block of nodes at a time, then assign another block when the first one runs out, etc.

As far as I can tell, I need 3 data structures to achieve this, but I hope that someone can recommend a simpler and more elegant method.

The three data structures I'm thinking about are:

  1. Binary tree
  2. Stack (to store pre-assigned nodes and easily find the next one to use)
  3. Linked list (to store the different assigned node blocks so that they can be located and eventually released).

The way this would work is:


  1. Assign a block of nodes.
  2. Push each node in the block on the stack
  3. Add block to the linked list.

Tree Insert

  1. If the stack is empty, assign another block of N nodes, insert them into the stack and add them to the linked list
  2. Pop stack node and store tree node data in it
  3. Add node to the tree structure, swing, etc.

Delete tree

  1. Find the item in the tree and remove it from the tree.
  2. Push the node back onto the stack to use it later to insert


  1. Destroy tree
  2. Go through the linked list and delete all the node blocks

Using a stack to store all the pre-assigned nodes seems a good idea, since the insertion / deletion operations would be $ O (1) $. However, each time a new block of N nodes must be assigned, I must push them all on the stack $ (O (N)) $ and insert it into the Linked List $ (O (1)) $. Finally, cleaning at the end requires traversing the Linked List $ (O (NB)) $ where $ NB $ is the number of node blocks assigned.

It seems to me that I should be able to do this with less complexity (maybe 2 data structures instead of 3). Does anyone know of a more elegant method?