JIYIK CN >

A binary tree is a non-linear data structure. It is called a binary tree because each node has at most two children. These children are called left children and right children. For a binary tree to be a BST, it must satisfy the following properties.

• All nodes in the left subtree are smaller than the root node.
• All nodes in the right subtree are larger than the root node.
• The left and right subtrees must also be binary search trees.

Algorithm for testing whether a binary tree is a binary search tree

Algorithm 1

In this approach, we treat each node as the root of its subtree and check if the left subtree contains any element greater than the root value and if the right subtree contains any element less than the root value. To find the maximum and minimum element, we have to use two separate functions getMin()and getMax().

getMin()

• Initialize tempto root.
• When tempthere is a left, do the following.
  • Set tempto temp->left, that is, move left to find the smallest element.
• Returns temp->valthe minimum value of the subtree.

getMax()

• Initialize tempto root.
• When tempthere is a right, do the following.
  • Set tempto temp->right, that is, move right to find the largest element.
• Returns temp->valthe maximum value of the subtree.

isBST(root)

• If rootyes NULL, return true.
• Find the maximum element in the left subtree by calling getMax(root->left) maxm.
• Find the minimum element in the right subtree by calling getMin(root->right) minm.
• If the root element is less than maxmor greater than minm, returns false.
• Recursively check all nodes by calling isBST(root->left)and isBST(root->right). If both recursive calls return true, then the tree is a BST and return true, otherwise return false.

The above algorithm tells us whether a tree is a BST, but it is extremely slow. Functions getMin()and getMax()have a worst-case time complexity of n2 O(n), and they are ncalled for n2 nodes, making the total time complexity O(n2 ⁾ .

Algorithm 2

This algorithm improves on the previous one by not repeating the calculations. The previous method called getMin()and for each node getMax(). This method improves on the above method by keeping track of the minimum and maximum allowed values ​​as we traverse the nodes.

isBST(root)

• Initialize two variables minto be INT_MINand maxto be INT_MAX.
• Call isBST(root,min,max).

isBST(root, min, max)

• If rootyes NULL, return true.
• If min> root->data, then the BST property is violated and false is returned.
• If max< root->data, then the BST property is violated and false is returned.
• isBST(root->left, min, root->data-1)The left subtree is checked recursively by calling (passing minand root->data - 1as parameters changes the valid range of the BST in the left subtree), and isBST(root->right, root->data+1, max)the right subtree is checked recursively by calling (passing root->data + 1and maxas parameters changes the valid range of the BST in the right subtree).
• If both recursive calls return true, then the tree is a BST, return true.

The time complexity of this algorithm is O(n), which is a significant improvement over the previous method.

Algorithm 3

This algorithm avoids the use of INT_MINand in the above algorithm INT_MAXand uses two pointers land rinstead.

isBST(root)

• Initialize two nodes land rto be NULL.
• Call isBST(root, l, r). (Overloaded function call)

isBST(root, l, r)

• If rootyes NULL, return true.
• If lis not NULLand l->data>= root->data, then the BST property is violated and false is returned.
• If ris not NULLand r->data<= root->data, then the BST property is violated and false is returned.
• Recursively check the left subtree by calling isBST(root->left, left, root)(passing root as the third argument changes the subtree's minimum limit) and calling (passing root as the second argument changes the subtree's maximum limit).isBST(root->right, root, right)
• If both recursive calls return true, then the tree is a BST, return true.

Algorithm 4:

The inorder traversal of a binary search tree returns the elements in sorted order. We can use this property to check whether a binary tree is a BST or not. If all the elements in the inorder traversal are not in ascending order, then the given tree is not a binary search tree.

isBST(root)

• prevInitialize the variable to INT_MIN. prevUsed to check if the current node is greater than prev, thus proceeding in sorted order.
• Call isBST(root, prev). (Overload function Call).

isBST(root,prev)

• If rootyes NULL, return true.
• Recursively isBST(root->left, prev)check the left subtree by . If it does false, return false.
• If root->data<= prev, the ascending order is violated and false is returned.
• Update prev->datato root->data.
• Recursively isBST(root->right, prev)check the right subtree by . If it does false, return false.
• Otherwise, return true.

Algorithm implementation method to check whether a binary tree is a binary search tree

Algorithm 1

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int x) {
        this->data = x;
        this->left = this->right = NULL;
    }
};
int getMin(Node* root)
{
    while (root->left) {
        root = root->left;
    }

    return root->data;
}
int getMax(Node* root)
{
    while (root->right) {
        root = root->right;
    }

    return root->data;
}
bool isBST( Node* root)
{
    if (root == NULL)
        return true;

    if (root->left != NULL && getMax(root->left) > root->data)
        return false;

    if (root->right != NULL && getMin(root->right) < root->data)
        return false;

    if (!isBST(root->left) || !isBST(root->right))
        return false;

    return true;
}
int main()
{
    Node *root = new Node(6);
    root -> left = new Node(3);
    root -> right = new Node(9);
    root -> left -> left = new Node(1);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(7);
    root -> right -> right = new Node(11);
    if (isBST(root)) {
        cout << "This binary tree is a BST." << endl;
    }
    else {
        cout << "This binary tree is not a BST." << endl;
    }
    return 0;
}

Algorithm 2

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int x) {
        this->data = x;
        this->left = this->right = NULL;
    }
};
bool isBST(Node* root, int min, int max)
{
    if (root == NULL)
        return 1;
    if (root->data < min || root->data > max)
        return 0;

    return
        isBST(root->left, min, root->data - 1) &&
        isBST(root->right, root->data + 1, max);
}

bool isBST( Node* root)
{
    return isBST(root, INT_MIN, INT_MAX);
}
int main()
{
    Node *root = new Node(6);
    root -> left = new Node(3);
    root -> right = new Node(9);
    root -> left -> left = new Node(1);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(7);
    root -> right -> right = new Node(11);
    if (isBST(root)) {
        cout << "This binary tree is a BST." << endl;
    }
    else {
        cout << "This binary tree is not a BST." << endl;
    }
    return 0;
}

Algorithm 3

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int x) {
        this->data = x;
        this->left = this->right = NULL;
    }
};
bool isBST(Node* root, Node* l, Node* r)
{

    if (root == NULL)
        return true;

    if (l != NULL and root->data <= l->data)
        return false;
    if (r != NULL and root->data >= r->data)
        return false;

    return isBST(root->left, l, root) && isBST(root->right, root, r);
}
bool isBST( Node* root)
{
    Node* l = NULL;
    Node* r = NULL;
    return isBST(root, l, r);
}
int main()
{
    Node *root = new Node(6);
    root -> left = new Node(3);
    root -> right = new Node(9);
    root -> left -> left = new Node(1);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(7);
    root -> right -> right = new Node(11);
    if (isBST(root)) {
        cout << "This binary tree is a BST." << endl;
    }
    else {
        cout << "This binary tree is not a BST." << endl;
    }
    return 0;
}

Algorithm 4

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int x) {
        this->data = x;
        this->left = this->right = NULL;
    }
};
bool isBST(Node* root, int& prev)
{

    if (!root) return true;

    if (!isBST(root->left, prev))
        return false;

    if (root->data <= prev)
        return false;
    prev = root->data;

    return isBST(root->right, prev);
}


bool isBST(Node* root)
{
    int prev = INT_MIN;
    return isBST(root, prev);
}
int main()
{
    Node *root = new Node(6);
    root -> left = new Node(3);
    root -> right = new Node(9);
    root -> left -> left = new Node(1);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(7);
    root -> right -> right = new Node(11);
    if (isBST(root)) {
        cout << "This binary tree is a BST." << endl;
    }
    else {
        cout << "This binary tree is not a BST." << endl;
    }
    return 0;
}

Complexity Analysis

Time Complexity

• Average situation

To check if a given binary tree is a BST, we have to traverse all nthe nodes, since a node that does not meet the property will result in the tree not being a BST. Therefore, the time complexity is [Big Theta]: O(n).

• Best Case

The time complexity for the best case is O(n). It is the same as the time complexity for the average case.

• Worst case scenario

The worst case time complexity is O(n). It is the same as the best case time complexity.

Space complexity

Due to the additional space required for the recursive calls, the space complexity of this algorithm is O(n).