Question

C++

Let x be a pointer to the root node of a red-black tree. Write an algorithm called TreeCountRed(x) that takes x as argument

and returns the number of red nodes in the tree.

Answer 1

TreeCountRed(x) 
    count = 0;
    if (x == null) 
        return 0;
    
    count += TreeCountRed(x->left);
    count += TreeCountRed(x->right);

    if(x->color=="RED")
        count++;
    
    return count;

This is recursive algorithm by which we can find the number of red nodes in the tree. Here we traverse the left subtree and count the no of red nodes in this and then count in the right subtree and then add together and at last check for the color of root itself and add to the count if found red. Special case (or say base case) -> when root is null or there is no node in the tree.