How to verify if a given tree is a Binary Search Tree or not

Question

I wanted to know if a given binary tree is a binary search tree or not.

I don't know How to do that?

The only thing I know is that the inorder traversal of BST will gives you ascending order output.

So, is this the only condition we need to verify or is there anything else we are suppose to check.

In case if there are some other necessary conditions to be checked, What are they? and why those conditions are necessary to be checked? Because, I think, INORDER traversal itself can tell you easily if the given tree is BST or not.

Start with [the definition of a Binary Search Tree](http://en.wikipedia.org/wiki/Binary_search_tree). Does the tree given match this definition? (Note that the in-order traversal rule can be derived by applying the rules recursively. Also note that different trees, e.g. RB, may qualify as a BST *and* another tree type.) — , Apr 16 '12 at 08:44
Can you please go through the below link....the question i asked is almost similar to that. But in that link, people have suggested some other ways...apart from INORDER traversal. I dont know why those extra conditions needs to be checked. http://stackoverflow.com/questions/499995/what-is-validating-a-binary-search-tree — Jatin, Apr 16 '12 at 09:02
All the answers in the link you have provided pretty much does the same "an inorder walk (in different languages) and check if the left sub-tree is smaller than the root and the right sub-tree is greater than the root". This is exactly what @Andreas Brinck has said in his answer below. — yasouser, Apr 16 '12 at 13:11

score 13 · Accepted Answer · answered Apr 16 '12 at 08:42

13

Yes, if inorder traversal of the tree gives you a strictly monotonic list of values that is sufficient to determine that the tree is a BST.

answered Apr 16 '12 at 08:42

Andreas Brinck

51,293
14
84
114

can you give an example of 'monotonic list of values'; :( – Papai from BEKOAIL Feb 15 '19 at 12:47

score 5 · Answer 2 · edited Dec 19 '14 at 05:55

By definition of Binary search tree, if every node of the binary tree satisfy the following conditions then it is a Binary Search Tree:

The left subtree of a node should contain only nodes with keys less than the node’s key
The right subtree of a node should contain only nodes with keys greater than the node’s key
Both the left and right subtrees must also be binary search trees.

All the above conditions are verified if the inorder traversal is in ascending order.

score 0 · Answer 3 · answered Aug 27 '13 at 13:57

Actually - it is not enough to just do an in order traversal - you also need to verify that each node's value follows the rules of the tree. In the case of a BST, the left child value is less than the node value and the right child value is greater than the node value. Here is a recursive example in Java.

private static boolean isBST(Node current, Comparable more, Comparable less) {
    if (current == null) 
        return true;

    if (less != null && current.value.compareTo(less) > 0)
        return false;

    if (more != null && current.value.compareTo(more) < 0) 
        return false;

    return isBST(current.left, more, current.value) && 
            isBST(current.right, current.value, less);
}

public static boolean isBST(BinarySearchTree tree) {
    return isBST(tree.getRoot(), null, null);
}

score 0 · Answer 4 · answered May 09 '14 at 07:12

While doing In-Order traversal, we can keep track of previously visited node

Code:

bool isBST(struct node* root)
{
    static struct node *prev = NULL;

    // traverse the tree in inorder fashion and keep track of prev node
    if (root)
    {
        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;
}

score 0 · Answer 5 · answered May 09 '14 at 21:30

A simple but elegant recursive solution in Java:

public static boolean isBST(TreeNode node, int leftData, int rightData)
{
    if (node == null) return true;

    if (node.getData() > leftData || node.getData() <= rightData) return false;

    return (isBST(node.left, node.getData(), rightData)
           && isBST(node.right, leftData,  node.getData()));

}

The initial call to this function can be something like this:

if (isBST(root, Integer.MAX_VALUE, Integer.MIN_VALUE))
    System.out.println("This is a BST.");
else
    System.out.println("This is NOT a BST!");

Essentially we keep creating a valid range (starting from [ MIN_VALUE, MAX_VALUE]) and keep shrinking it down foe each node as we go down recursively.

Source: http://exceptional-code.blogspot.com/2011/08/binary-search-trees-primer.html

How to verify if a given tree is a Binary Search Tree or not

5 Answers5