Hi everyone,
while studying binary trees, I came across this thing that a complete binary tree
has ceiling (n/2) leaves. Why is that ? and if I am to prove this through induction, what would be my base case?
acidburns
0
Newbie Poster
Narue
5,707
Bad Cop
Team Colleague
>Why is that ?
It's easiest to understand if you have a perfect binary tree (all levels are full). Notice that each branch contains twice the number of nodes. This means that in a perfect binary tree, the number of nodes on each level is exactly the number of nodes on all levels above it + 1. A perfect tree also happens to have an even number of nodes on a single level and an odd number of nodes on all levels above. If you divide the total number of nodes by 2, you get the number of internal nodes and another half (which is why ceil is needed to bump the whole result up by 1).
Now, a complete tree isn't necessarily perfect, but you can easily verify that the number of leaves will never be less than the number of internal nodes, and also never be more than 1 greater than the number of internal nodes. If the number of leaves and internal nodes are the same, the division is gives you a whole number with no fractional part, and ceil does nothing.
>if I am to prove this through induction, what would be my base case?
An empty tree with no nodes.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.