Check whether a tree satisfies the black-height property of Red Black Tree

Question

How to recursively check if a given red black tree respects the rule of "Every path from a node to a null link must contain the same number of black nodes". I'm using this structure:

enum color = {RED, BLACK};

typedef struct node {
    int value;
    struct node* left;
    struct node* right;
    color c;
} node;

I've tried to implement an algorithm using this prototype:

bool isRBT(struct node* tree, int numberBlackNodesLeft, int numberBlackNodesRight)

But, I wasn't able to count these numbers recursively. Because, the rule imposes that every path from one node must repects the rule. Which was some hard to me to implement.

Any brilliant idea, please ?

Thanks in advance!

Answer 1

Here is a simple way to do it:

// Returns the number of black nodes in a subtree of the given node
// or -1 if it is not a red black tree.
int computeBlackHeight(node* currNode) {
    // For an empty subtree the answer is obvious
    if (currNode == NULL)
        return 0; 
    // Computes the height for the left and right child recursively
    int leftHeight = computeBlackHeight(currNode->left);
    int rightHeight = computeBlackHeight(currNode->right);
    int add = currNode->color == BLACK ? 1 : 0;
    // The current subtree is not a red black tree if and only if
    // one or more of current node's children is a root of an invalid tree
    // or they contain different number of black nodes on a path to a null node.
    if (leftHeight == -1 || rightHeight == -1 || leftHeight != rightHeight)
        return -1; 
    else
        return leftHeight + add;
}

---

To test whether a tree satisfies the black-height property of the Red-Black Tree, you can wrap the above function as:

bool isRBTreeBlackHeightValid(node* root)
{
    return computeBlackHeight(root) != -1;
}