0
$\begingroup$

Given a tree $T$ with $n$ nodes, every node that isn't a leaf has 2 children, can i drive a formula for number of leaves in a such tree $T$?

My idea: i read this post:Full binary tree proof validity: Number of leaves $L$ and number of nodes $N$ , but it is about full binary tree, our problem maybe not full binary tree.

$\endgroup$
1
  • $\begingroup$ What is your definition of full binary tree? The tree you describe is what I call a full binary tree. $\endgroup$
    – saulspatz
    Mar 8 at 1:52
0
$\begingroup$

Suppose that $T$ has $n$ nodes, $\ell$ of which are leaves; then the sum of the degrees of the nodes is

$$2+3(n-\ell-1)+\ell=3n-2\ell-1\,,$$

since the root has degree $2$, each of the other $n-\ell-1$ non-leaves has degree $3$, and each leaf has degree $1$. This is twice the number of edges, so $T$ has $\frac{3n-1}2-\ell$ edges.

On the other hand, $T$ is a tree, so it has $n-1$ edges, and we have the equation

$$\frac{3n-1}2-\ell=n-1\,,$$

so that

$$\ell=\frac{n+1}2\,.$$

The reason that $n$ has to be odd, as this formula clearly implies, is that the non-root nodes of $T$ come in sibling pairs, so there is an even number of them, and the root makes an odd total number of nodes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.