# A closed form expression for # of inputs of a binary tree and its number of nodes

Is there any closed from expression that can express the number of input pins of a binary tree based on height of the tree and its number of nodes?

In case that the binary tree is a full tree, it is easy to find the number of input pins. In this case we will have $2^{H-1}$ nodes at the last level of the tree ($H$ is the height of the tree). Thus, the # of input pins will be $2^H$ because each node has 2 input pins.

How can we generalize this for a binary tree which is not a full trees?

• For any binary tree the number of leaves equals the number of internal nodes plus one. Isn't that an expression linking input pins and nodes? – Hendrik Jan Apr 3 '17 at 1:19
• Yes, you are right. # of nodes+1 is what I need!, thank you very much! :) – Ghasem Apr 3 '17 at 3:04
• @HendrikJan Write an answer with the short inductive proof? – Yuval Filmus Apr 3 '17 at 7:15

## 1 Answer

There is a known expression linking the number of input pins and the number of nodes in a binary tree. It does not use the height of the tree.

For any binary tree the number of leaves equals the number of internal nodes plus one.

We can prove this by induction. Basis. A tree with one node has two leaves. Induction step. Whenever I replace a leaf by a new node, both the number of nodes and the number of leaves increase by one (we lose a leaf, and get two new leaves in return).