package com.sunny.grokkingalgorithms.gfg.it.trees;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by sundas on 2/26/2018.
 */
class Node {
  int data;
  Node left;
  Node right;
}
public class IsBTreeABST {

  /*
  Find if a tree is BST
   */


  boolean checkBSTAlternate(Node root){
    return checkBSTAlternateUtil(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
  }


  boolean checkBSTAlternateUtil(Node root,int min,int max){
    if(root == null){
      return true;
    }

    if(root.data < min || root.data > max){
      return false;
    }

    return checkBSTAlternateUtil(root.left,min,root.data - 1) && checkBSTAlternateUtil(root.right,(root.data + 1),max);

  }

  boolean checkBST(Node root) {
    if(root == null){
      return true;
    }
    boolean left = checkBST(root.left);
    if(left){
      boolean right = checkBST(root.right);
      if(right){
        int maxLeft = findMax(root.left,Integer.MIN_VALUE);
        int minRight = findMin(root.right,Integer.MAX_VALUE);
        return root.data > maxLeft && root.data < minRight;
      }
    }
    return false;
  }

  int findMax(Node root,int maxValue){
    if(root == null){
      return maxValue;
    }
    if(root.data > maxValue){
      maxValue = root.data;
    }
    int leftMax = findMax(root.left,maxValue);
    int rightMax = findMax(root.right,maxValue);
    return Math.max(leftMax,rightMax);
  }

  /**
   *
   * @param root
   * @param minValue
   * @return
   */
  int findMin(Node root,int minValue){
    if(root == null){
      return minValue;
    }
    if(root.data < minValue){
      minValue = root.data;
    }
    int leftMin = findMin(root.left,minValue);
    int rightMin = findMin(root.right,minValue);
    return Math.min(leftMin,rightMin);
  }

}

@@ -261,16 +261,540 @@
    */%0A%0A%0A
+%0A  private static Node previous;%0A  boolean checkBSTInorderOption(Node root) %7B%0A    return checkBSTInorder(root);%0A  %7D%0A%0A  boolean checkBSTInorder(Node root)%7B%0A    if(root == null)%7B%0A      return true;%0A    %7D%0A    boolean leftBST = checkBSTInorder(root.left);%0A    if(leftBST)%7B%0A      if(previous != null && previous.data %3E= root.data)%7B%0A        return false;%0A      %7D%0A      previous = root;%0A      boolean rightBST = checkBSTInorder(root.right);%0A      if(leftBST && rightBST)%7B%0A        return true;%0A      %7D%0A    %7D%0A    return false;%0A  %7D%0A%0A%0A
   boolea

Check if a tree is a BST using Inorder traversal.