DS BINARY TREE

Question

Consider a binary tree T that has 100 leaf nodes. Then the number of nodes in T that have exactly ONE children are ______.

Comments

Here condition about binary tree is required.

I would make

n leaves by taking n internal node out of which only 1 has 1 child.

Like,

take a case of 1 leaf = > 1 internal node

take a case of 2 leaves => root has 2 leaves and among them one leaf again has one child, hence 2 leaves 2 internal nodes but only one internal node has 1 child

Not convinced?

take a case of 3 leaves => root has 2 leaves. among that 2 children one will have again 2 children and remaining 1 will have 1 child. Hence 3 internal nodes but only one has 1 child.

Same for any tree.

SO for 100 leaves, I will take 100 internal node out of which only 1 has one child