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?
-
$\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$Hendrik Jan– Hendrik Jan2017年04月03日 01:19:06 +00:00Commented Apr 3, 2017 at 1:19
-
$\begingroup$ Yes, you are right. # of nodes+1 is what I need!, thank you very much! :) $\endgroup$Ghasem– Ghasem2017年04月03日 03:04:39 +00:00Commented Apr 3, 2017 at 3:04
-
$\begingroup$ @HendrikJan Write an answer with the short inductive proof? $\endgroup$Yuval Filmus– Yuval Filmus2017年04月03日 07:15:19 +00:00Commented Apr 3, 2017 at 7:15
1 Answer 1
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).
Explore related questions
See similar questions with these tags.