Check for Binary Search Tree in c++

 

A Binary Search Tree (BST) is a special type of tree data structure in which the value of each node is greater than or equal to the values of all the nodes in its left subtree and less than or equal to the values of all the nodes in its right subtree. In other words, it is a tree that follows the property of a binary search algorithm, where the left subtree of a node contains only nodes with keys lesser than the node's key, and the right subtree contains only nodes with keys greater than the node's key.

One of the most important applications of BSTs is in searching and sorting algorithms, as they allow for efficient searching and sorting of data. In this article, we will discuss how to check for a Binary Search Tree in C++.

Before we begin, it is important to note that there are several different ways to check for a BST in C++. One of the most common methods is to use an in-order traversal of the tree, and check if the values of the nodes are in increasing order. Another method is to check the value of each node against the minimum and maximum values of its left and right subtrees.

Method 1: In-Order Traversal

The first method we will discuss is using an in-order traversal of the tree. In-order traversal is a method of traversing a tree in which the left subtree is visited first, then the root, and finally the right subtree. By traversing the tree in this order, the nodes will be visited in ascending order, which is the property of a BST.

Here is a C++ implementation of this method:

bool checkBST(Node* root) { 
 if (root == NULL)
        return true;
 // check left subtree 
 if (!checkBST(root->left)) 
 return false;
 // check current node
 
    if (prev != NULL && root->data <= prev->data)
 return false;
 prev = root;
 // check right subtree
     
if (!checkBST(root->right))
 return false;
 return true;
 }

In this code, we use a recursive approach to traverse the tree in-order. We first check if the current node is null, and if so, return true. We then check the left subtree, and if it is not a BST, we return false. Next, we check the current node against the previous node (stored in the variable prev) and if the current node's value is less than or equal to the previous node's value, we return false. Finally, we check the right subtree, and if it is not a BST, we return false. If all of these checks pass, we return true, indicating that the tree is a BST.

Method 2: Min and Max Values

The second method we will discuss is checking the value of each node against the minimum and maximum values of its left and right subtrees. In a BST, the value of each node must be greater than or equal to the values of all the nodes in its left subtree and less than or equal to the values of all the nodes in its right subtree.

Here is a C++ implementation of this method:

bool checkBST(Node* root, int minValue, int maxValue) {
 if (root == NULL)
        return true;
 // check current node
 
    if (root->data < minValue || root->data > maxValue)
 return

false;

// check left subtree 
if (!checkBST(root->left, minValue, root->data))
 return false;

 
// check right subtree
 
if (!checkBST(root->right, root->data, maxValue))
 return false;
 return true;

}

In this code, we use a recursive approach to check the value of each node against the minimum and maximum values of its left and right subtrees. We first check if the current node is null, and if so, return true. We then check the current node's value against the minimum and maximum values passed in as parameters (`minValue` and `maxValue`). If the current node's value is less than the minimum value or greater than the maximum value, we return false. Next, we check the left subtree, and if it is not a BST, we return false. Finally, we check the right subtree, and if it is not a BST, we return false. If all of these checks pass, we return true, indicating that the tree is a BST.

Conclusion

In this article, we have discussed two methods for checking for a Binary Search Tree in C++: using an in-order traversal and checking the value of each node against the minimum and maximum values of its left and right subtrees. Both methods are efficient and can be used to check for a BST in C++. However, it is important to note that both of these methods have time complexity of O(n) where n is the number of nodes in the tree, which could be a problem for very large trees. It is up to you to decide which method works best for your specific use case.