# Rooted Binary Tree - Chain Nodes Algorithm

The question is that I have to give a recursive algorithm in pseudocode, that counts the number of chain node in a rooted binary tree. Chain node is defined as a node that has only one child and that child is not a leaf. I am stuck any help would be appreciated, so far I have done this:

Algorithm Chainnode(x) {
if (not Leaf(x)) and (left[x] XOR right[x] == Null) {
return True
}
else {
return False
}
}

Algorithm ChainnodeCount(x) {
i = 0
if (x == Null or Leaf[x]) then {
return i
}
else if ChainNode(left[x]) == True {
i = ChainNodeCount(left[x]) + 1
}
else if ChainNode(right[x]) == True {
i = ChainNodeCount(right[x]) + 1
}
else {
i = ChainNodeCount(left[x]) + ChainNodeCount(right[x])
}
}


The number of chain nodes of a rooted binary tree with two non-empty sons is the sum of the chain nodes in its sons.

Also, the number of chain nodes of a rooted binary tree with only one non-empty son is the number of chain nodes of the son plus one.

If a rooted binary tree has no non-empty sons, its number of chain nodes is zero.

And finally, the number of chain nodes of an empty rooted binary tree is zero.

So, following this properties we have

int chainNodes(tree T) {
if (T is empty)
return 0;
if (T has no nonempty sons)
return 0;
if (T has only one nonempty son)
return chainNodes(son)+1;
if (T has two nonempty sons)
return chainNoodes(leftSon)+chainNodes(rightSon);
}


which is similar to your try.

• thank you very much! – tonytouch Mar 2 '19 at 16:12