why is static keyword required for finding if a given binary tree is BST or not?

Question

Here is the code for finding if the given binary tree was a binary search tree(BST) or not:

bool isBST(struct node* root)
{
     // traverse the tree in inorder fashion and keep track of prev node
    if (root)
    {
        struct node *prev = NULL;
        if (!isBST(root->left))
          return false;
        // Allows only distinct valued nodes 
        if (prev != NULL && root->data <= prev->data)
          return false;
        prev = root;
        return isBST(root->right);
    }

    return true;
}

However this does not give the correct output. when I changed my code to the below version it worked fine:

bool isbst(node * root)
{
    static struct node * prev = NULL;
    if( root)
    {
        if(!isbst(root->left))
            return false;
        if(prev != NULL && root->data < prev->data)
            return false;
        prev = root;
        return isbst(root-> right);
    }
   return true;
}

My question is why does it work when the line static struct node * prev = NULL; was added to the code?

In my previous code even though the variable 'prev' was declared again and again it was update to the root each time..my code should have worked fine. But it didn't. what is wrong with it?

N.Vegeta · Accepted Answer · 2017-07-15T13:32:19.270

static struct node * prev = NULL;

In the above line, the use of the static keyword gives rise to two things: 1) prev is only initialised to null exactly once, i.e. the first time it is reached
2) More importantly, because prev is static, any update to its value is retained in subsequent calls to the function isBST.

In your initial/bad/non-working case without the static keyword

struct node *prev = NULL;

1) You are not retaining the value of the previous node (this is precisely why your algo didn't work) 2) Not only that you are setting it to null

In short, with the use of static, you are retaining the previous node's value (your intention). In the other case, you aren't retaining the previous node's value

static initialisation of a variable within a function scope in C++ is a neat way to retain values between recursive calls.

why is static keyword required for finding if a given binary tree is BST or not?

1 Answers1