What is the maximum and minimum number of leaf nodes of a binary tree with n nodes?

Question

As far as I understood, the minimum number of leaf nodes of a n-node binary tree is 1 and the maximum number of leaf nodes is ⌈n/2⌉. Are my assumptions correct?

Answer 1

• Leaf node count of a binary tree >= 1 is trivially correct.

• Leaf node count <= ⌈n/2⌉:

Proof:

• For n=1, leaf node count = 1
• For every <1 left branch & 1 right branch under the same leaf> you stop a leaf from being so, and create 2 new leafs (+1 leaf per 2 nodes)
• For every <left branch> or <right branch> you create under a leaf, you stop a leaf from being so and create 1 new leaf (+0 leaf per 1 node)

Therefore, at maximum Leaf node count <= 1 + ((n-1)//2) = ⌈n/2⌉