Compute the binary tree nodes count

Question

Is it possible to compute how many nodes have arbitrary binary tree? The leaf count and the depth of every leaf are known (it is Huffman tree actually).

I need it in order to be able to allocate needed memory for the tree before building it actually and to avoid memory re-allocations later.

Answer 1

A Huffman tree is a full binary tree, i.e. every node in the tree has either 0 or 2 children. In this case you need exactly k - 1 inner nodes for k leafs. So the total number of nodes is 2k - 1.