CareerCup

Boolean test(node n,int min,int max){
if (n.data<min ||n.data>max)
return false
else
return test(n.left,min,n.data)&&test(n.right,n.data,max)
}
call as test(root,-MAX_INT,MAX_INT)

Boolean test(node n,int min,int max){
if (n.data<min ||n.data>max)
return false
else
return test(n.left,min,n.data)&&test(n.right,n.data,max)
}
call as test(root,-MAX_INT,MAX_INT)

Boolean test(node n,int min,int max){
if (n.data<min ||n.data>max)
return false
else
return test(n.left,min,n.data)&&test(n.right,n.data,max)
}
call as test(root,-MAX_INT,MAX_INT)

Make in-order traversation and check in prevValue <= curValue. Time: O(N). Space: O(1)

conside a tree ( not a bst, 10 comes in right subtree of 15)
15
/ \
12 18
/ \ /
11 14 10
here if you do inorder
11 12 14 15 10 18
according to your logic its a bst

white spaces not preserved, typing again

15
         /    \
        12    18
       / \    /
      11 14  10

oops, m@}{ is right, i take my comments back. here 15 > 10 so inorder check fails, any other senario, where it can fail??

thats not a BST..he's making fun of you..inorder always gives sorted array for a BST,,lol

thats not a BST..he's making fun of you..inorder always gives sorted array for a BST,,lol

int isBST(struct node* node) {
if (node==NULL) return(true);
// false if the max of the left is > than us

// (bug -- an earlier version had min/max backwards here)
if (node->left!=NULL && maxValue(node->left) > node->data)
return(false);

// false if the min of the right is <= than us
if (node->right!=NULL && minValue(node->right) <= node->data)
return(false);

// false if, recursively, the left or right is not a BST
if (!isBST(node->left) || !isBST(node->right))
return(false);

// passing all that, it's a BST
return(true);
}

<pre lang="" line="1" title="CodeMonkey38788" class="run-this"> public class ValidBST
{
public bool IsValidBst(BTreeNode node)
{
if ((node.LeftNode == null && node.RightNode == null) || node==null)
return true;

bool isValid = IsValidBst(node.LeftNode) && IsValidBst(node.RightNode);
if (node.RightNode != null)
isValid &= (int)node.Data < (int)node.RightNode.Data;
if (node.LeftNode != null)
isValid &= (int)node.Data >= (int)node.LeftNode.Data;
return isValid;
}
}</pre><pre title="CodeMonkey38788" input="yes">
</pre>

Check out the recursive version

//pre-condition min - INT_MIN, max - INT_MAX

int checktree(struct node *root, int min, int max) {
        int ret = 0;
        if(root != NULL) {
                if(root->data >= min && root->data < max)
                        ret = 1;
                return ret && checktree(root->left,min,root->data + 1)  
                        && checktree(root->right,root->data, max);
        }
        else
                return 1;
}

Do an inorder traversal and check if the numbers are in increasing order.Time O(n) and space O(n)

efficient solution is just do inorder traversal of the BST, and it will give the the sorted list of nodes...if not giving sorted list...its not a BST..every node value should be greater than the every visited node value...