Check if a Binary Tree is Binary Search Tree

Given a Binary Tree, write code to check if it is Binary Search Tree or not ? Binary search tree is a binary tree with following restrictions

• All values in the left subtree are Less than the value at root.
• All values in the Right subtree are Greater than the value at root.
• Both Left and Right sub-trees are Binary Search Trees themselves.

Don't fall for the trap:

The below logic does not work:

bool checkBST(Node* root)
{
    if(root == NULL)
        return true;
    // Data at root should satisfy BST condition
    if(root->data < root->lptr->data || root->data > root->rptr->data)
        return false;
    // Both Left & Right Sub-tree should be BST
    return (checkBST(root->lptr) && checkBST(root->rptr));
}

The above function will return true for the below tree also, But it is NOT a BST because  9 cannot come to the right of 15).

    15
   /  \
  10  20
     /  \
    9    40

The problem with above code is that it is very shallow and only check if the children of a node satisfies BST or not, but ignore the condition with the ancestors.

Below are couple of solutions for the given problem:

1. Check the in-order traversal

If the in-order traversal of the Binary Tree is sorted in ascending order,
    then the tree is Binary Search Tree,
else
    it is not Binary Search Tree.

Code:

I am using the code from this post. The function populates the inorder traversal of the tree in an array.

/**
 * Populate the array arr with the inorder traversal of the tree pointed to by r.
 * pos holds a reference to the current poisition of arr.
 */
void populateInorderArray(Node*  r, int* arr, int* pos)
{
    if(r == NULL)
        return;
    populateInorderArray(r->lptr, arr, pos);
    arr[*pos] = r->data;
    (*pos)++;
    populateInorderArray(r->rptr, arr, pos);
}

The function to check will be as below

/**
 * Check if a Tree is a Binary Search Tree or not
 */
bool checkBST(Node* r)
{
    if(NULL == r)
        return true;
    // hard-codding it to 1000 for simplicity.
    // define the array equal to number of nodes.
    int arr[1000] = {0};
    int n = 0;    // Will hold the number of Nodes
    populateInorderArray(r, arr, &n);
    // Check if the array is sorted in ascending order
    for(int i=0; i < n-1; i++)
        if(arr[i] > arr[i+1])
            return false;
    return true;
}

However we can avoid creation of this temporary array because we just need to compare the current node with the previous node in the in-order traversal. The value of previous node can be passed in the recursive function.

Initial value of previous Node will be MINUS_INFINITY

bool checkBSTRecursive(Node *p, int& prev)
{
    if(p == NULL)
        return true;
    if (checkBSTRecursive(p->left, prev))
    {
        if (p->data > prev)
        {
            prev = p->data;
            return checkBSTRecursive(p->right, prev);
        }
        else
        {
            return false;
        }
    }
    else
    {
        return false;
    }
}
bool checkBST(Node *root)
{
    int prev = INT_MIN;
    return checkBSTRecursive(root, prev);
}

Time complexity: O(n)

2. Remembering the bounds

Another method is to remember the bounds within which the Node values can exist. For example, if the tree is

    15
   /  \
  10  20
     /  \
    9    40

then the bounds for each node is as given below:

Node     Lower_Bound      Upper_Bound      Check
----     -----------      -----------      -----
15     MINUS_INFINITY    PLUS_INFINITY     true
10     MINUS_INFINITY         15           true
20        15             PLUS_INFINITY     true
9         15                  20           FALSE
40        15             PLUS_INFINITY     true

Since 9 is not within the bounds (between 15 & 20), hence the above tree is not BST.

We will keep on updating the bounds for each recursion.

Code:

/**
 * check for the node to be within the bounds,
 *        update the bouds for left sub-tree
 *        update the bouds for right sub-tree
 * call itself recursively for left & right subtrees
 */
bool checkBSTRecursive(Node* r, int low, int high)
{
    if (r == NULL)
        return true;
    if(low>r->data || high < r->data)
        return false;
    // Update low and high for subtrees
    return checkBSTRecursive(r->left, low, r->data)
             &&   checkBSTRecursive(r->right, r->data, high);
}
/** Main Function.
 * INT_MIN & INT_MAX are defined to be the lowest and highest values
 * an int can hold
 */
bool checkBST(Node *root)
{
    return checkBSTRecursive(root, INT_MIN, INT_MAX);
}