In binary tree, number of nodes with two children when number of leaves is given

Question

For a binary tree what is the number of nodes with two children when the number of leaves is 20?

I know that for complete binary tree, when the number of leaves is x then the number of internal nodes is x-1.

But in the question above the given tree is just the binary tree not the complete binary tree. Also, the number of nodes asked is for those having two children which differs from internal node / non-leaf nodes.

Is there any formula to get this?

Answer 1

Let the number of leaves be $l$. Let the number of nodes with exactly two children be $d_2$ and with exactly one children be $d_1$.

Total degree

$d=l+3d_2+2d_1-1$ (as all nodes with 2 children have degree 3 except the root)

Number of nodes $n=d_2+d_1+l$

Number of edges $e=\frac{d}{2}=\frac{l+3d_2+2d_1-1}{2}$

Number of edges in a tree $e=n-1$

$\therefore \frac{l+3d_2+2d_1-1}{2}=d_2+d_1+l-1$

$\therefore d_2=l-1$

This is the result which I was trying to prove in this question.

Answer 2

The number of leaves minus one is equal to the number of nodes with two children.

Suppose there is a counter-example, then take one with the minimum number of vertices. Take the counter-example tree and remove one of the leaves. There are two things that can happen depending if the leaf is connected to a node that had two or one son. But both give a smaller counter-example as you should check. A contradiction.

Answer 3

Hint:

• For any tree: $|E| = |V|-1$.
• For any graph $2|E| = \sum_{v \in V} \deg(v)$.
• A vertex is a leaf if and only if it's degree is $1$.
• Except for root, the two-children nodes have degree $3$.
• Intuition: start with a path (each vertex has degree 2, except for two leaves at the ends); now, each time you change a vertex from degree 2 to degree 3, you have make some other vertex of degree 2 into degree 1, so that the sum of degrees is constant.

I hope this helps $\ddot\smile$

Answer 4

The task is to count how many nodes with two children, say n₂, and how many leaves n₀. So to simplify the problem, we can completely "replace" the nodes with one children with their children. This won't disturb our counting process. Why? Think about it.

                  +----z
                 |
     +----y----+
     |           +----z
x --+
     |           +----z
     +----y----+
                 |
                 +----z

The y's are useless for our problem. x is already qualified for our n₂ group (either because of y's are z's, doesn't matter) and the four z's are intact (as leaves) after our "replacement".

Now assume the number of leaves as L. The n₂ are just connectors to n₀ nodes or connectors to some other nodes in n₂. Ask how many are n₂ nodes? That's easy. Just add $$ L/2 + L/2^2 + L/2^3+....+L/2^k $$ where L=2^k. Then the The sum is $$ L(1-1/2^k) = L-1 $$