Number of leaves in complete binary tree

Question

I got confused a bit about definitions and from reading in the different forums, does both complete binary tree (last level is not full) and perfect binary tree, number of leaves are ⌈n/2⌉ for a tree with n nodes ? If not for what binary tree is it true? And I am asking about the exact number and not boundary. Thanks

Answer 1

A full binary tree is a binary tree where every node is either a leaf or is internal with two children.

Is such a tree has $k$ internal nodes then it has $k+1$ leaves. Thus when the total number of nodes equals $n=2k+1$ the the number of leaves equals $k+1=\lceil \frac n2\rceil$. Whatever the structure of that tree.

This can be proved using induction.

Answer 2

[…] does both complete binary tree (last level is not full) and perfect binary tree, number of leaves are ⌈n/2⌉ for a tree with n nodes ?

Yes!

Every perfect binary tree is a full binary tree, so is covered by Hendrik Jan's answer.

A complete binary tree is not necessarily a full binary tree; for example, the below is a complete binary tree whose root node has exactly one child:

  A
 /
B

Nonetheless, every complete binary tree with $n$ nodes does have $\lceil \frac n 2 \rceil$ leaf nodes. To see this, observe that there are only two cases:

1. It is a full binary tree: each of its nodes has two children or zero children.
   • In this case it's covered by Hendrik Jan's answer.
2. Exactly one of its nodes has exactly one child.
   • In this case, consider the subgraph induced by removing that one child. This subgraph is a full binary tree with $n - 1$ nodes, of which (by Hendrik Jan's answer) $\frac n 2 - 1$ are internal nodes and $\frac n 2$ are leaf nodes. So the original complete binary tree (including the child) has $\frac n 2$ internal nodes and $\frac n 2$ leaf nodes.