1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Apr 3, 2017 at 1:19
  • $\begingroup$ Yes, you are right. # of nodes+1 is what I need!, thank you very much! :) $\endgroup$
    – Ghasem
    Apr 3, 2017 at 3:04
  • $\begingroup$ @HendrikJan Write an answer with the short inductive proof? $\endgroup$ Apr 3, 2017 at 7:15

1 Answer 1

0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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