Binary Search Tree Check

Question: Given a binary tree, check whether it is a binary search tree or not.

Solution 1:

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

public boolean isBST(TreeNode T) {         if(T == null){             return true;         }         if(T.left != null && T.element < getMaxVal(T.left)) {             return false;         }         if(T.right != null && T.element > getMinVal(T.right)) {             return false;         }         return isBST(T.left) && isBST(T.right);     }           private int getMaxVal(TreeNode T){              while(T.right != null) {             T = T.right;         }         return T.element;     }     private int getMinVal(TreeNode T){              while(T.left != null) {             T = T.left;         }         return T.element;     }

Solution 2: Efficient one

1 2 3 4 5 6 7 8 9 10 11

public boolean isBST2(TreeNode T, int min, int max) {         if(T == null) {             return true;         }         if(min < T.element && T.element < max) {             return isBST2(T.left, min, T.element) && isBST2(T.right, T.element, max);         }         else {             return false;         }           }