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

3
votes

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?

2
binary-tree
you mean a balanced tree, because you can have a binary tree where all branches are left, or right, then you have N nodes and one leaf, if they are balanced then there should be a ratio, not that I know – geckos
No. I am just asking about binary tree in general, not a balanced one. – enamul17
You can have a binary tree with no right branch, keep adding all branches to the left, and you will have a binary tree with arbitrary deep and only one leaf. – geckos
You can have a binary search tree for example, you add N, then N-1, then N-2, ..., N-M. You will have a binary tree with no right branch, M nodes and one leaf – geckos

2 Answers

1
votes

  • 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⌉

0
votes

To complete, and maybe correct what @Kostas suggested is thinking that what you need to do to get the most leaves is a perfect (full) binary tree, which would make all the non-leaf nodes, nodes with 2 children.

  • A - no. of leaves
  • C - no. of nodes with two children (ideally, all the other ones)

No matter what, the relationship between these two is

A = C + 1

Now if the number of leaves is maximal, that means all the nodes that are not leaves would have two children, so only in this case it would mean that: A + C = N (total no. of nodes)

If we turn the equations around we would get: C = N - A => A = N - A + 1 => A = (N+1)/2

In the end, the maximum number of leaves (terminal nodes) in a binary tree with N total nodes is (N+1)/2

You can even try it out yourself with a program or peace of paper, personally the other answer in here doesn't work when I try to use it, now I may 100% be wrong.