package com.sunny.grokkingalgorithms.fasttrack.treesandgraphs;

import com.sunny.grokkingalgorithms.ctci.c4.util.BinaryTreeNode;
import com.sunny.grokkingalgorithms.ctci.c4.util.TreeUtils;

import java.util.HashMap;
import java.util.Map;

class BSTPlaceHolder{
  int max = Integer.MIN_VALUE;
  int min = Integer.MAX_VALUE;
}
/**
 * Created by sundas on 6/9/2018.
 */
public class CheckIfATreeIsABSTOrNot {

  /*
  Check if a given binary tree is a BST or not.
   */

  public static Map<BinaryTreeNode,BSTPlaceHolder> minMaxHolder = new HashMap<>();

  /**
   *
   * @param root
   * @return
   */
  public static boolean isBST(BinaryTreeNode root){
    if(root == null){
      return true;
    }
    int maxOfLeftSubTree = findMaxAlt(root.left);
    int minOfRightSubTree = findMinAlt(root.right);
    if(root.data >= maxOfLeftSubTree
        && root.data < minOfRightSubTree){
      /*
      Check if subtrees are bst or not, bST condition for this node has been validated.The BST condition should hold true
       for every node in the tree.
       */
      return (isBST(root.left) && isBST(root.right));
    }
    /*
    Failed BST condistion so false,no need to check further.
     */
    return false;
  }


  /**
   *
   * @param root
   * @return
   */
  public static int findMaxAlt(BinaryTreeNode root){
    if(root == null){
      return Integer.MIN_VALUE;
    }
    if(minMaxHolder.containsKey(root) && minMaxHolder.get(root).max > Integer.MIN_VALUE){
      return minMaxHolder.get(root).max;
    }
    int left = findMaxAlt(root.left);
    int right = findMaxAlt(root.right);
    int max = Math.max(left,right);
    max = Math.max(root.data,max);
    BSTPlaceHolder bstPlaceHolder = null;
    if(minMaxHolder.get(root) != null){
      bstPlaceHolder = minMaxHolder.get(root);
    }
    else{
      bstPlaceHolder = new BSTPlaceHolder();
      minMaxHolder.put(root,bstPlaceHolder);
    }
    bstPlaceHolder.max = max;
    return max;
  }

  /**
   *
   * @param root
   * @return
   */
  public static int findMinAlt(BinaryTreeNode root){
    if(root == null){
      return Integer.MAX_VALUE;
    }
    if(minMaxHolder.containsKey(root) && minMaxHolder.get(root).min < Integer.MAX_VALUE){
      return minMaxHolder.get(root).min;
    }
    int left = findMinAlt(root.left);
    int right = findMinAlt(root.right);
    int min = Math.min(left, right);
    min = Math.min(root.data,min);
    BSTPlaceHolder bstPlaceHolder = null;
    if(minMaxHolder.get(root) != null){
      bstPlaceHolder = minMaxHolder.get(root);
    }
    else{
      bstPlaceHolder = new BSTPlaceHolder();
      minMaxHolder.put(root,bstPlaceHolder);
    }
    bstPlaceHolder.min = min;
    return min;
  }






  /**
   *
   * @param root
   * @return
   */
  public static boolean isBSTBruteForce(BinaryTreeNode root){
    /*
    Empty tree is a BST
     */
    if(root == null){
      return true;
    }
    int maxOfLeftSubTree = findMax(root.left);
    int minOfRightSubTree = findMin(root.right);
    if(root.data >= maxOfLeftSubTree
        && root.data < minOfRightSubTree){
      /*
      Check if subtrees are bst or not, bST condition for this node has been validated.The BST condition should hold true
       for every node in the tree.
       */
      return (isBSTBruteForce(root.left) && isBSTBruteForce(root.right));
    }
    /*
    Failed BST condistion so false,no need to check further.
     */
    return false;
  }

  /**
   *
   * @param root
   * @return
   */
  public static int findMax(BinaryTreeNode root){
    if(root == null){
      return Integer.MIN_VALUE;
    }
    int left = findMax(root.left);
    int right = findMax(root.right);
    int max = Math.max(left,right);
    max = Math.max(root.data,max);
    return max;
  }

  /**
   *
   * @param root
   * @return
   */
  public static int findMin(BinaryTreeNode root){
    if(root == null){
      return Integer.MAX_VALUE;
    }
    int left = findMin(root.left);
    int right = findMin(root.right);
    int min = Math.min(left,right);
    min = Math.min(root.data,min);
    return min;
  }


  /**
   *
   * @param args
   */
  public static void main(String[] args) {
    BinaryTreeNode root = TreeUtils.createBST();
    TreeUtils.performBfsLevelMarker(root);
    System.out.println(isBSTBruteForce(root));
    System.out.println(isBST(root));
    System.out.println("########");
    root = TreeUtils.createUnBalancedBinaryTree();
    TreeUtils.performBfsLevelMarker(root);
    System.out.println(isBSTBruteForce(root));
    System.out.println(isBST(root));
  }

}

@@ -544,16 +544,711 @@
 p%3C%3E();%0A%0A
+%0A  static BinaryTreeNode previous;%0A%0A  /**%0A   *%0A   * @param root%0A   * @return%0A   */%0A  public static boolean isBSTUsingInorderTraversal(BinaryTreeNode root)%7B%0A    /*%0A    An empty tree is BST%0A     */%0A    if(root == null)%7B%0A      return true;%0A    %7D%0A    //Go left%0A    boolean left = isBSTUsingInorderTraversal(root.left);%0A    if(left) %7B%0A      //Now previous has been populated%0A      if (previous == null%0A          %7C%7C root.data %3E previous.data) %7B%0A        previous = root;%0A        //Go right now current root will be the predecessor to the next node%0A        boolean right = isBSTUsingInorderTraversal(root.right);%0A        if(right)%7B%0A          return true;%0A        %7D%0A      %7D%0A    %7D%0A    return false;%0A  %7D%0A%0A%0A
   /**%0A  
@@ -4999,32 +4999,90 @@
 n(isBST(root));%0A
+    System.out.println(isBSTUsingInorderTraversal(root));%0A
     System.out.p
@@ -5279,15 +5279,73 @@
 root));%0A
+    System.out.println(isBSTUsingInorderTraversal(root));%0A
   %7D%0A%0A%7D%0A

Check if a Binary Tree is a BST or not , using inorder traversal.