# Find a formula for leaves in tree

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.

• What is your definition of full binary tree? The tree you describe is what I call a full binary tree. Mar 8 at 1:52

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.