content: package trees;
  
  public class IsBST {
  
      /*
       * Given a Binary Tree figure out whether it's a Binary Search Tree.
       * A binary search tree holds the property that each node's key value is smaller than the key value of all
       * nodes in the right subtree and greater than the key values of all nodes in the left subtree i.e. L < N < R.
       *
       *  BST: 100, 50, 200, 25, 75, 125, 350
       *
       *  Runtime Complexity:
       *  Linear, O(n)
       *
       *  Memory Complexity:
       *  O(h)
       *  
       * */
  
      private static class Node {
          private int data;
          private Node left, right;
  
          Node(int item) {
              data = item;
              left = right = null;
          }
  
          public int getData() {
              return data;
          }
  
          public Node getLeft() {
              return left;
          }
  
          public Node getRight() {
              return right;
          }
      }
  
  
      private Node root1;
  
      private static boolean isBstRec(Node root,
                                      int minValue,
                                      int maxValue) {
  
          if (root == null) {
              return true;
          }
  
          if (root.data < minValue ||
                  root.data > maxValue) {
              return false;
          }
  
          return
                  isBstRec(root.left, minValue, root.data) &&
                          isBstRec(root.right, root.data, maxValue);
      }
  
      public static boolean isBst(Node root) {
          return isBstRec(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
      }
      
      
  
      public static void main(String[] argv) {
  
          IsBST isBST = new IsBST();
          isBST.root1 = new Node(100);
          isBST.root1.left = new Node(50);
          isBST.root1.right = new Node(200);
          isBST.root1.left.left = new Node(25);
          isBST.root1.left.right = new Node(75);
          isBST.root1.right.left = new Node(125);
          isBST.root1.right.right = new Node(350);
  
          System.out.println();
          System.out.println("Is it BST: " + Boolean.toString(isBst(isBST.root1)));
      }
  }
  