How will you check if a Binary tree is BST or not?

1.	How will you check if a Binary tree is BST or not?
Answer» Before understanding this with a program let’s KNOW some PROPERTIES of BST. Nodes in the LEFT subtree of a node have keys less than the node’s key. Nodes in the right subtree of a node in BST have keys greater than the node’s key. Both left and right subtrees are also BST. To check a binary TREE is BST or not, we have different approaches like Brute Force APPROACH, Optimized Brute Force, and Using In order Traversal. Today we will show this using the Inorder Traversal approach. Example bool isBST(node* root) { static 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; }

Answer»

Before understanding this with a program let’s KNOW some PROPERTIES of BST.

Nodes in the LEFT subtree of a node have keys less than the node’s key.
Nodes in the right subtree of a node in BST have keys greater than the node’s key.
Both left and right subtrees are also BST.
To check a binary TREE is BST or not, we have different approaches like Brute Force APPROACH, Optimized Brute Force, and Using In order Traversal.
Today we will show this using the Inorder Traversal approach.

Example

bool isBST(node* root)
{
     static 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;
}

Discussion

No Comment Found

Related InterviewSolutions

If Microsoft wanted to introduce a data analytics product to small businesses, how will you use your marketing skills to drive interest and highlight its virtues?
Explain recursion in a way that a non-technical person may comprehend.
Is data deleted from the Recycle Bin permanently lost?
How do you establish and maintain healthy connections with coworkers who work in different locations?
List out some main differences between standard modules and class modules?
How will you check if a Binary tree is BST or not?
How would you explain the cloud to someone but you have only 90 seconds?
Do you use Microsoft products or services? If yes, which one is your favorite, and why?

How will you check if a Binary tree is BST or not?

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment