Internal path length of red black tree

Question

I am working on a homework problem which asks us to find the Internal path length of a red black tree. This is the code I have implemented so far.

int Tree::internalpathlength(BinTree* root_node, int curr_level){
int ipl;
if(root_node == NULL){
    return 0;
}
else if(root_node->colour == BLACK){
    ipl = (curr_level+internalpathlength(root_node->left,curr_level+1)+internalpathlength(root_node->right,curr_level+1));

}
return ipl;
}

I think I am missing the base case of the recursion. Can someone help me understand it better? Thanks.

Answer 1

I think the correct answer is that we do not have to check for root node's colour to be black. The internal path length should be calculated for both black and red nodes. If we do not consider the red link, it means that we are considering elements connected by a red link as a two node, which is not the case.

int Tree::internalpathlength(BinTree* root_node, int curr_level){
    if(root_node == NULL){
    return 0;
    }
     else
      return (curr_level+internalpathlength(root_node->left,curr_level+1)+internalpathlength(root_node->right,curr_level+1));
  }