Insert into binary tree and keep it balanced
You can keep all leaves in a queue, and on insertion set the new node as a child for the q.front(), add the new node to the queue and check if the numbers of children of the node in front of the queue = 2 then pop the node out of the queue.
To remove a node you can swap the node you are removing and the last added node delete the last one (you should remove it from the back of the queue as well). 

However, I would implement it as an array where a[0] is the root of the tree and a[i*2 + 1], a[i*2 + 2] are the children of a[i]. Inserting would be in this case to add an element to the back of the array and to remove an element you can swap it with the back of the array and pop the back of the arrray