# 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