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

Question

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 1

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;
}

Tested

I tested your code with a simple loop:

RedBlackBST tree = new RedBlackBST();
tree.root = tree.put(null, 0, 0);

for (int i = 1; i < 10; i++) {
    tree.root = tree.put(tree.root, i, i);
}
int redTotal = tree.countRed(tree.root);

This returns a total of 3 reds. If I inspect it in debug, it's accurate. If you feel the value isn't valid, then you should inspect your tree in debug and identify what isn't valid in your structure.