PROBLEM DESCRIPTION
Given a tree, check whether it’s a BST.
SOLUTION
APPROACH 1
MaxOf(Left Sub Tree) < Node.value <= MinOf(Right Sub Tree)
Using this relation, for each Node, we can find the max on LST and min on RST and check if the current Node belongs to that range. Recursively do this for each Node.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.*;
class Program {
public static boolean validateBst(BST tree) {
if(tree == null) return true;
boolean check = (tree.value > findMax(tree.left) && tree.value <= findMin(tree.right));
return check && validateBst(tree.left) && validateBst(tree.right);
}
public static int findMax(BST tree){
if(tree == null) return Integer.MIN_VALUE;
int left = findMax(tree.left);
int right = findMax(tree.right);
if(tree.value > left && tree.value > right){
return tree.value;
}else if(left > right){
return left;
}else{
return right;
}
}
public static int findMin(BST tree){
if(tree == null) return Integer.MAX_VALUE;
int left = findMin(tree.left);
int right = findMin(tree.right);
if(tree.value < left && tree.value < right){
return tree.value;
}else if(left < right){
return left;
}else{
return right;
}
}
static class BST {
public int value;
public BST left;
public BST right;
public BST(int value) {
this.value = value;
}
}
}
APPROACH 2
A more optimal way is to maintain the min and max possible values while making the recursive call. For the root node, it’s going to be between INTEGER.MIN_VALUE & INTEGER.MAX_VALUE. When we call root.left, the possible value should be between (INTEGER.MIN_VALUE, root.value-1). For root.right: (root.value, INTEGER.MAX_VALUE). Assuming that the duplicate values are on the right sub-tree. This way we can keep doing the recursive call and updating the range of possible values. If the node.value does not fall in this range, return false.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;
class Program {
public static boolean validateBst(BST tree, int min, int max) {
if(tree == null) return true;
if(tree.value < min || tree.value > max) return false;
boolean left = validateBst(tree.left, min, tree.value-1);
boolean right = validateBst(tree.right, tree.value, max);
return left && right;
}
public static boolean validateBst(BST tree) {
return validateBst(tree, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
static class BST {
public int value;
public BST left;
public BST right;
public BST(int value) {
this.value = value;
}
}
}