For the purpose of memory performance optimizations while building a Huffman tree I would like to pre-allocate the necessary memory for its nodes.
Is there a way to calculate the maximum number of nodes (internal nodes plus leafs)?
Input for the calculation should be the table of symbols and their probabilities/frequencies. I would like to avoid a simulated tree building run. Instead it should be a plain calculation that must not give the actual/optimal number of nodes but a reliable maximum.
If there are n symbols, then there are n-1 internal nodes, or 2n-1 internal nodes and leaves, or what you're calling nodes. It's always exactly that — not a "maximum".