Posts

Showing posts from August, 2011

Is Binary search tree - Java Program

/** 
  * Following method can be used to test if a tree meets the conditions to be a binary search tree (BST). 
  */ 
  public boolean isBST(TreeNode root) {
      if (root == null)
          return false;
      return( isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE) );
  }


/** 
   * Recursive Method - which validates very sub tree of a given binary tree.
   * Works in O(n) time -- visits each node only once. 


   * @param min   For left sub tree it should be Integer.MIN_Value
   *                        For right sub tree it should be node.data + 1
   * @param max For left sub tree it should be node.data
   *                     For right sub tree it should be Integer.MAX_VALUE


   *
   */ 
  private boolean isBST2(TreeNode node, int min, int max) {
    if (node==null) {
      return(true);
    }
    else {

     if (node.getData() < min || node.getData() > max)
return false;
     // left should be in range  min...node.data
      boolean leftOk = isBST(node.getLeft(), min, node.getData());


      // if …