CODEWITHSUNDEEP
algorithmdata-structuresrecursionred-black-tree
Georges Krinker
Georges Krinker

Reputation: 2309

Red black tree red children property check

Given a RB Tree, I need to write an algorithm that checks that every node that is red, has both its children black.

i.e. returns true if every red node only has black children, false otherwise.

Here is my attempt:

ChildCheck(x){
    if (x.color==black){
        if(x.leftChild !=null or x.leftchild!=nil)
            bool a = ChildCheck(x.leftChild)
        else  a = true
        if (x.rightChild!=null or x.leftchild!=nil){
            bool b = Childcheck(x.leftChild)
        else b = true
        return (a && b)
    }
    else
        if (x.leftChild !=null or x.leftchild!=nil)
            if(x.leftChild.color==black)
                d = true
            else d = false
        else
            d = true
        if (x.rightChild !=null or x.rightchild!=nil)
            if(x.rightChild.color==black)
                e = true
            else e = false
        else
            e = true
        return (d && e)
    }
}

Will this return the right answer? If no, what's wrong with it?

Upvotes: 0

Views: 1242

Answers (1)

healthy
healthy

Reputation: 182

bool CheckRedProperty(NodePtr root)
{
    if (root == NULL) 
        return true;

    if (!CheckRedProperty(root->left))
        return false;

    if (CheckRedProperty(root->right))
        return false;

    if (root->IsRed() 
        && (root->left && root->left->IsRed() || root->right && root->right->IsRed()))
            return false;
    return true;
}

Upvotes: 2

Related Questions