Binary trees and preallocated nodes
What you are doing is called (simple) "object pooling", a topic that has been discussed numerous times. It can be said to have nothing to do binary trees.

The simplest and yet efficient approach is to use a single stack or list, just like the C++ vector class or Java ArrayList, so that you do not have to maintain the "linked list" to keep track of the different allocated node blocks. Initially a block of $N$ nodes is allocated. Use a tail pointer to remember the first free node. Whenever it runs out of free nodes, just allocate $2N$ nodes or $cN$ nodes for a factor $c&gt;1$ of your choice. Memory copy the existing nodes to the new block and free the previous block. Do not worry about the performance of copying nodes, which is just one (system) call that should have been optimized by your language runtime and operating system.

In general, do not write these kinds of utilities from scratch by yourself unless as an exercise to broaden your skill set or enhance your understanding. For example, there is an object pool in boost library if you can use C++. Also, do not do it just for the sake of performance unless you have identified node allocation and deallocation is the performance bottleneck. The recent c/c++ runtime might be fast enough for you on object allocation and deallocation.

I would recommend that you search "object pooling" on the web or, more directly, inside github.com with your choice of language, C if you want to dive further. You will be able to find many articles and many working implementations, (for example, simple object pool.

Finally, in many cases, especially in many programming contests, all you need to do is to preallocate a huge number of nodes like a few millions of them upfront. Then just use them without deallocation. Simple, stupid and wonderful.