## Monday, December 29, 2014

### Checking if a given Binary Tree is a Binary Search Tree [Top-Down and Bottom-Up (Recursive) Approaches]

Q. Implement a function to check if a binary tree is a binary search tree.

Source:

```public class Code{

public class Node{
int value;
Node left, right;
Node(){}
Node(int value){this.value = value;}
Node(int value, Node left, Node right){
this.value = value;
this.left = left;
this.right = right;
}

@Override
public String toString(){
return "Value: "+value;
}
}

Node root;

Integer previous = null;
boolean isBSTMethod1(Node node){
if(node == null)return true;
if(!isBSTMethod1(node.left))return false;
if(previous!=null && previous > node.value)return false;
previous = node.value;
return isBSTMethod1(node.right);
}

//Top down check
boolean isBSTMethod2(Node node, Integer min, Integer max){
if(node == null) return true;
if((max != null && node.value >= max) ||
(min != null && node.value < min)) return false;
if(!isBSTMethod2(node.left, min, node.value)) return false;
return isBSTMethod2(node.right, node.value, max);
}

class Pair{
Integer min, max;
Pair(Integer min, Integer max){
this.min = min;
this.max = max;
}
}

//Bottom Up Check
boolean isBSTMethod3test(){
isBST = true;
isBSTMethod3(root);
return isBST;
}

boolean isBST;
Pair isBSTMethod3(Node node){
if(node.left == null && node.right == null) return new Pair(node.value, node.value);

Pair left, right;

if(node.left == null) left = new Pair(node.value, null);
else left = isBSTMethod3(node.left);
if(!isBST)return null;

if(node.right == null) right = new Pair(null, node.value);
else right = isBSTMethod3(node.right);
if(!isBST)return null;

if((left.max != null && left.max >= node.value) || (right.min != null && right.min<node.value))
isBST = false;

return new Pair(left.min, right.max);
}

//Other functions
void makeCustom(){
//Tree 1 - Comment out others
root = new Node(5);
root.left = new Node(2);
root.right = new Node(10);
root.left.right = new Node(40);
root.left.left = new Node(1);
root.left.right.left = new Node(3);
root.right.left = new Node(7);
root.right.right = new Node(10);

/*
Failure case for Method1. This binary tree mush have values of
node.right >= node && node.left < node
*/

/*
root = new Node(4);
root.left = new Node(5);
root.right = new Node(5);
*/

/*
//Tree 2
root = new Node(25);
root.left = new Node(10);
root.right = new Node(40);
root.left.right = new Node(20);
root.left.left = new Node(5);
root.left.left.left = new Node(3);
*/

//Tree 3
root = new Node(35);
root.left = new Node(15);
root.left.left = new Node(7);
root.left.left.left = new Node(4);
root.left.left.right = new Node(9);
root.left.right = new Node(20);
root.left.right.left = new Node(17);
root.left.right.right = new Node(34);
root.right = new Node(55);
root.right.left = new Node(40);
root.right.left.left = new Node(37);
root.right.left.right = new Node(50);
root.right.right = new Node(60);
root.right.right.left = new Node(57);
root.right.right.right = new Node(65);

}

void printTree(String string){
System.out.println(string);
inorder(root);
}

void inorder(Node node){
if(node==null)return;
inorder(node.left);
System.out.println(node.value);
inorder(node.right);
}

public static void main(String[] args){
Code tree = new Code();
tree.makeCustom();
System.out.println("Is this tree a BST? : "+tree.isBSTMethod2(tree.root, null, null));
System.out.println("Is this tree a BST? : "+tree.isBSTMethod3test());
}
}```

Output:

Is this tree a BST? : true
Is this tree a BST? : true