user3408536 user3408536 - 1 month ago 6
Java Question

Java program to calculate how many red nodes are in a Red-Black Tree

I'm building a program to determine how many red nodes are in a red black tree. I have already implemented a RED BLACK BST which builds the tree after reading a text input. I'm stuck on how to count the number of red nodes? I know the red nodes can only be left leaning and a red parent node can't have a red child. What would be the appropriate method on attacking this problem?

Answer

A recursive solution would look like this:

public static int countRed(Node node) {
    int nbRed = 0;
    if (node == null) {
        return 0;
    }
    nbRed += countRed(node.left);
    nbRed += countRed(node.right);

    if(node.isRed()){
        nbRed++;
    }
    return nbRed;
}