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 the left is not ok, bail out
      if (!leftOk) return(false);


      // right should be in range node.data+1..max
      boolean rightOk = isBST(node.getRight(), node.getData()+1, max);


      return(rightOk);
    }
  }

Comments

Post a Comment

Popular posts from this blog

Custom PagingNavigator for SEO friendly URL

Importing / Indexing MySQL data into Solr

The Externalizable Interface