Binary Search Tree : Check whether given binary tree is binary search tree or not .

Problem :

Check whether given binary tree is binary search tree or not.


Observation :

Binary Tree - tree with maximum two leaves .
Binary search tree (BST) - tree with maximum two leaves such that  (left < root < right ) leaf.

For binary tree to be as binary search tree properties  are

1. left sub-tree must be less than root .
2. right sub-tree must be greater than root.
3. Means value of root must lie between limits of left and right values .

Or

1. If we do in-order traversal of the tree it must give values sorted in ascending order

Algorithm Type : Recursion


Java code using above two properties

package com.salpe.tree;

import java.util.logging.Logger;

import org.junit.Assert;
import org.junit.Test;

/**
 * Check whether given binary tree is binary search tree or not 
 *
 */
public class BSTTest5 {

 private static final Logger s_logger = Logger.getLogger(BSTTest2.class.getName());

 /**
  * Binary tree pre-order list as 0,1,2,3,4,5,6
  */
 @Test
 public void testSuccess() {

  BST<Integer> bst = createSuccessTestData();

  boolean resultSubBSTChk = bst.isBSTUsingSubBSTChk();
  boolean resultInorderChk = bst.isBSTUsingInorderChk();

  s_logger.info("Using subSBTChk: " + Boolean.toString(resultSubBSTChk));
  s_logger.info("using InorderChk:  " + Boolean.toString(resultInorderChk));
  Assert.assertTrue(resultSubBSTChk);
  Assert.assertTrue(resultInorderChk);

 }

 /**
  * tests when binary search tree is degraded to linked list
  */
 @Test
 public void testWorstCaseSuccess() {

  BST<Integer> bst = createSuccessWorstCaseTestData();

  boolean resultSubBSTChk = bst.isBSTUsingSubBSTChk();
  boolean resultInorderChk = bst.isBSTUsingInorderChk();

  s_logger.info("Using subSBTChk: " + Boolean.toString(resultSubBSTChk));
  s_logger.info("using InorderChk:  " + Boolean.toString(resultInorderChk));
  Assert.assertTrue(resultSubBSTChk);
  Assert.assertTrue(resultInorderChk);
 }

 @Test
 public void testFailure() {

  BST<Integer> bst = createFailureTestData();
  boolean resultSubBSTChk = bst.isBSTUsingSubBSTChk();
  boolean resultInorderChk = bst.isBSTUsingInorderChk();

  s_logger.info("Using subSBTChk: " + Boolean.toString(resultSubBSTChk));
  s_logger.info("using InorderChk:  " + Boolean.toString(resultInorderChk));
  Assert.assertFalse(resultSubBSTChk);
  Assert.assertFalse(resultInorderChk);

 }



 private BST<Integer> createSuccessTestData() {
  // create test data
  BSTNode<Integer> node0 = new BSTNode<>(0, null, null);
  BSTNode<Integer> node2 = new BSTNode<>(2, null, null);

  BSTNode<Integer> node01 = new BSTNode<>(1, node0, node2);

  BSTNode<Integer> node06 = new BSTNode<>(6, null, null);
  BSTNode<Integer> node04 = new BSTNode<>(4, null, null);

  BSTNode<Integer> node05 = new BSTNode<>(5, node04, node06);

  BSTNode<Integer> node03 = new BSTNode<>(3, node01, node05);

  // create BST
  BST<Integer> bst = new BST<>(node03);
  return bst;
 }

 /**
  * worst case is linked list for binary tree
  * 
  * @return
  */
 private BST<Integer> createSuccessWorstCaseTestData() {
  // create test data

  BSTNode<Integer> node06 = new BSTNode<>(6, null, null);

  BSTNode<Integer> node05 = new BSTNode<>(5, null, node06);

  BSTNode<Integer> node04 = new BSTNode<>(4, null, node05);

  BSTNode<Integer> node03 = new BSTNode<>(3, null, node04);

  BSTNode<Integer> node02 = new BSTNode<>(2, null, node03);

  BSTNode<Integer> node01 = new BSTNode<>(1, null, node02);

  BSTNode<Integer> node0 = new BSTNode<>(0, null, node01);

  // create BST
  BST<Integer> bst = new BST<>(node0);
  return bst;
 }

 private BST<Integer> createFailureTestData() {
  // create test data
  BSTNode<Integer> node0 = new BSTNode<>(0, null, null);
  BSTNode<Integer> node2 = new BSTNode<>(2, null, null);

  BSTNode<Integer> node01 = new BSTNode<>(1, node0, node2);

  BSTNode<Integer> node06 = new BSTNode<>(-600, null, null);
  BSTNode<Integer> node04 = new BSTNode<>(4, null, null);

  BSTNode<Integer> node05 = new BSTNode<>(5, node04, node06);

  BSTNode<Integer> node03 = new BSTNode<>(3, node01, node05);

  // create BST
  BST<Integer> bst = new BST<>(node03);
  return bst;
 }

 /**
  * Binary Tree Node model
  *
  * @param <T>
  */
 static class BSTNode<T extends Comparable<T>> {

  T data;
  BSTNode<T> left;
  BSTNode<T> right;

  BSTNode(T data, BSTNode<T> left, BSTNode<T> right) {

   this.data = data;
   this.left = left;
   this.right = right;

  }

  @Override
  public String toString() {
   return "BSTNode [data=" + data + "]";
  }

 }

 /**
  * Binary Tree Representation
  *
  * @param <T>
  */
 static class BST<T extends Comparable<T>> {

  BSTNode<T> root;

  public BST(BSTNode<T> root) {
   this.root = root;
  }

  boolean isBSTUsingSubBSTChk() {

   return isBSTUsingSubBSTChk0(root);
  }

  /**
   * @param root
   * @return whether binary tree is BST
   */
  private boolean isBSTUsingSubBSTChk0(BSTNode<T> root) {

   if (root == null) {

    return true;

   }

   if ((root.left != null && (root.data.compareTo(root.left.data) < 0))
     || ((root.right != null) && (root.data.compareTo(root.right.data) > 0))) {

    return false;
   }

   // left part is BST
   boolean isLeftBST = isBSTUsingSubBSTChk0(root.left);

   // right part is BST
   boolean isRightBST = isBSTUsingSubBSTChk0(root.right);

   // left , middle , right is BST if all are BST
   return isLeftBST && isRightBST;

  }

  boolean isBSTUsingInorderChk() {

   return isBSTUsingInorderChk0(root, null);
  }

  private boolean isBSTUsingInorderChk0(BSTNode<T> node, T prev) {

   if (node == null) {

    return true;
   }

   boolean leftPartInorder = isBSTUsingInorderChk0(node.left, prev);

   boolean isleftBeforeRight = (prev != null ? prev.compareTo(node.data) < 0 : true);

   boolean rightPartInorder = isBSTUsingInorderChk0(node.right, node.data);

   return leftPartInorder && isleftBeforeRight && rightPartInorder;

  }

 }
}