I'm currently struggling with solving the following problem: given a tree T made up of n internal nodes, where n-k nodes have 2 children and k nodes have 3 children, demonstrate that T has n+k+1 leaves.
Can anyone help me or point me to the right direction? Thank you in advance!
On
Ok, after a while I managed to solve this.
Being m the number of leaves, and n the number of internal nodes, we know that the size of the tree equals the total number of nodes, which is then m+n.
Now we know that the sum of the degrees of all nodes tot_deg = size-1, so tot_deg = m+n-1. We can write tot_deg as 2(n-k) + 3k (number of children per each node multiplied by number of nodes).
We then solve the equation 2(n-k) + 3k = m+n-1 obtaining m, demonstrating that it's equal to n+k+1.
Try thinking of the tree as a family tree, and what a node with 2 children does to the number of nodes in the next generation... What does a node with 3 children do? Hope this helps