// Name   :
// Matric#:
// Group# :
// CS1102 Lab 8A
//
// A copy of this program can also be found at:
// http://www.comp.nus.edu.sg/~cs1102/B/a.html
//
// TITLE: Checking if a Binary Tree is a Binary Search Tree.
//
// In this lab, you are to write a method that checks if a binary tree
// satisfy the binary search tree property.  Efficiency is not a concern 
// in this lab, so we are using a very inefficient method that runs in 
// O(N^2).
//
// You are to complete three methods for BinaryTreeNode.
// (a) getMin()  -- returns the minimum element among the nodes in the
//     tree rooted at the current node.
// (b) getMax() -- returns the maximum element among the nodes in the 
//     tree rooted at the current node.  The code for this is very
//     similar to getMin().
// (c) isBST() -- returns true if the tree rooted at the current node 
//     satisfies BST property.  Returns false otherwise.  You may want
//     to make use of the getMin() and getMax() methods you have 
//     written.
//
// Important Remarks:
// - getMin() and getMax() should work on binary tree, not just 
//   binary search tree.
// - you should not use the function isBST2() shown in the lecture notes for
//   CS1102, Group A.
// - make sure you think, plan, and verify your solution before you begin 
//   coding.
// - you may find these two methods provided by Java useful:
//   - Math.min(int a, int b): returns the minimum of a and b.
//   - Math.max(int a, int b): returns the maximum of a and b.
// - you may also find these two constants provided by Java useful:
//   - Integer.MIN_VALUE: minimum possible value for int. 
//   - Integer.MAX_VALUE: maximum possible value for int. 


/**
 * A Node in a Binary Tree.  Each node has a integer element, and two 
 * references to the left and right node.  Note that left, right and 
 * element are not private.  Therefore, you can access their values
 * directly just like in the textbook (e.g., t.left).
 */
class BinaryNode {
  int element; 
  BinaryNode left;
  BinaryNode right;
  
  public BinaryNode(int x) 
  {
    element = x;
    left = right = null;
  }


  /**
   * getMin returns the minimum element in the tree rooted in this node.
   */
  int getMin()
  {
     // WRITE YOUR CODE HERE.
     return 0; //just to compile, you may want to remove it.
  }


  /**
   * getMax returns the maximum element in the tree rooted in this node.
   */
  int getMax()
  {
     // WRITE YOUR CODE HERE.
     return 0; //just to compile, you may want to remove it.
  }


  /**
   * isBST returns true if the tree rooted at this node is a BST. Return
   * false otherwise.
   */
  boolean isBST()
  {
     // WRITE YOUR CODE HERE.
     return false; //just to compile, you may want to remove it.
  }


  /**
   * prints out the tree for debugging.  Just a wrapper around 
   * the print(int level).
   */
  void print()
  {
     print(0);
     System.out.println();
  }

  /**
   * prints out the tree for debugging.
   */
  void print(int depth)
  {
     System.out.println(element);

     if (left != null) 
     {
         for (int i = 0; i <= depth; i++)
             System.out.print(" ");
         left.print(depth + 1);
     }

     if (right != null) 
     {
         for (int i = 0; i <= depth; i++)
             System.out.print(" ");
         right.print(depth + 1);
     }
  }
}


public class Lab8A {

  public static void main(String[] args) 
  {
    // Manually construct three trees.
    BinaryNode roots[];
    roots = new BinaryNode[3];

    roots[0] = new BinaryNode(1);
    roots[0].left = new BinaryNode(2);
    roots[0].right = new BinaryNode(3);
    roots[0].left.left = new BinaryNode(4);
    roots[0].left.right = new BinaryNode(5);
    roots[0].right.left = new BinaryNode(6);
    roots[0].right.right = new BinaryNode(7);

    roots[1] = new BinaryNode(5);
    roots[1].left = new BinaryNode(3);
    roots[1].right = new BinaryNode(7);
    roots[1].left.left = new BinaryNode(2);
    roots[1].left.right = new BinaryNode(4);
    roots[1].right.left = new BinaryNode(6);
    roots[1].right.right = new BinaryNode(8);

    roots[2] = new BinaryNode(2);
    roots[2].right = new BinaryNode(3);
    roots[2].right.left = new BinaryNode(1);
    roots[2].right.right = new BinaryNode(4);

    for (int i = 0; i < roots.length; i++) {
        roots[i].print();
        System.out.println("Min key is "+roots[i].getMin());
        System.out.println("Max key is "+roots[i].getMax());
        if (roots[i].isBST()) 
            System.out.println("This tree is a BST");
        else
            System.out.println("This tree is not a BST");
    }
  }
}