Fragen im Vorstellungsgespräch bei Bloomberg L.P.: Write a function to check if ... | Glassdoor.de

Frage im Vorstellungsgespräch

Financial Software Developer Intern-Vorstellungsgespräch New York, NY (Vereinigte Staaten von Amerika)

Write a function to check if a given tree is a valid binary

  search tree or not.
Antwort

Antwort im Vorstellungsgespräch

2 Antworten

0

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 am 11.04.2012
0

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

Anonymous am 11.04.2012

Antwort oder Kommentar posten

Um dies zu kommentieren, bitte anmelden oder Konto anlegen.