Binary trees and preallocated nodes

Question

I want to design a binary tree with preallocated nodes, in order to avoid calling malloc/free every time I want to insert/delete a node. The problem is I don't know ahead of time how many nodes the tree will have, so I am thinking I need to allocate a block of nodes at a time, then allocate another block when the first gets used up, etc.

As far as I can tell, I need 3 data structures to accomplish this, but I'm hoping someone can recommend a simpler, more elegant method.

The three data structures I am thinking of are:

1. Binary tree
2. Stack (to store the preallocated nodes and easily find the next one to use)
3. Linked list (to store the different allocated node blocks so they can be located and freed eventually).

The way these would work is:

Initialization

1. Allocate one block of N nodes
2. Push each node in the block onto the Stack
3. Append block to Linked List.

Tree Insert

1. If stack is empty, allocate another block of N nodes, push them onto the Stack and append it to Linked List
2. Pop node from stack and store tree node data in it
3. Add node to tree structure, do balancing, etc

Tree Delete

1. Find item in tree and remove from tree
2. Push node back onto Stack to be used later for insert

Cleanup

1. Destroy tree
2. Traverse Linked List and delete all node blocks

Using a Stack to store all the preallocated nodes seems like a good idea, since insert/delete operations would be $O(1)$. However, each time a new block of N nodes needs to be allocated, I need to push them all onto the Stack $(O(N))$ and insert it into the Linked List $(O(1))$. Finally, cleanup at the end requires traversing the Linked List $(O(NB))$ where $NB$ is the number of node blocks allocated.

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