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])
}
}