Swapnil
BAN USERConsidering that only one value is missing.
Method 1: Find the sum(S) of AP using:
S = (N/2)(First Term + Last Term);
First Term = a;
Last Term = a+(N-1)*(Delta);
where N = Number of terms in AP,
and, Delta is the difference between any two consecutive terms.
Hopefully this should work. Let me know if I missed anything.
@Nik: But how about the case of comparision between root->left->right and root. You can't say whether one entity will be greater or less than the other.
Below is the example:
12
/ \
8 15
/ \
7 10
\
9
In this case assume root = 8, and then (root->left->right) > root in this example which can be can not be true always.
You need to maintain global min and global max so that you can compare that any value in left subtree is always less than global minimum and similarly any value in right subtree should be greater than global maximum. Using that concept:
public boolean isBST(Node root) {
return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public boolean isBST(Node root, int min, int max) {
if(root == null)
return true;
if(root.data <= min || root.data > max)
return false;
if(!isBST(root.left, min, root.data) || !isBST(root.right, root.data, max))
return false;
return true;
}
- Swapnil April 16, 2015