Is Valid BST ?

Given a tree, how t o find out if it is Binary Search Tree or not?

two methods

1. Run inorder traversal on the tree and check if the resulting array is sorted or not.

2. For every node check if the Max of left subtree < the value at node and if min of right subtree> value at root.

Simple Solution:

boolean isBST(Node *root)
{
return (root == null || (
(root->left == null || (root->left->data < root->data
&& isBST(root->left))) && (root->right == null ||
(root->right->data > root->data &&
isBST(root->right)))));
}

Powered by ScribeFire.