Write a function to check if a given tree is a valid binary search tree or not.

Question

Anonymous · Accepted Answer

A functional (but possibly slow) recursive solution:

int maxInTree(Node* root)
{
    if(root->right==NULL) return(root->data);
    return maxInTree(root->right);
}

int minInTree(Node* root)
{
    if(root->left==NULL) return(root->data);
    return minInTree(root->left);
}

bool checkTree(Node* root)
{
    if(root==NULL) return true;
    if(root->data > maxInTree(root->left))
    {
        if(root->data right))
        {
            if(checkTree(root->left))
            {
                return checkTree(root->right);
            }
        }
    }
    return false;
}

Anonymous · Answer

Sorry! Since max and min do not check for NULL, must make adjustment:

bool checkTree(Node* root)
{
    if(root==NULL) return true;
    if(root->left==NULL?true:root->data>maxInTree(root->left))
    {
        if(root->right==NULL?true:root->data right))
        {
            if(root->left==NULL?true:checkTree(root->left))
            {
                return (root->right==NULL?true:checkTree(root->right));
            }
        }
    }
    return false;
}

Bloomberg

Sollicitatievraag bij Bloomberg

Antwoorden op sollicitatievragen

Gevolgde bedrijven

Vacatures