Is BST
by Isai Damier, Android Engineer @ Google
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | /*************************************************************************** * Author: Isai Damier * Title: Is BST * Project: geekviewpoint * Package: algorithms * * Statement: * Indicate whether the given binary tree is a BST. isBST allows for * either flavors of BST: left < node < right or right < node < left. * * Time Complexity of Solution: * Best = Average = Worst = O(n). * * Technical Details: This is an integrity ordeal algorithm (I hope this * phrase catches on). First the input is allowed to make a claim; then * the claim is severely tested for veracity. If any contradiction is * found, the input fails. For instance, if an input claims to be a * left < node < right BST, then it is sent to lnr for its trial. * * Note: This function has not been fully tested for true negatives. * See attached unit test. * * RNL: * Assume n.left.data > n.data > n.right.data. If a counter * instance is found, return false. Otherwise return true. * * LNR: * Assume n.left.data < n.data < n.right.data. If a counter * instance is found, return false; otherwise return true. * * lnr and rnl are symmetrical to each other. **************************************************************************/ public static boolean isBST(Node root) { if ( null != root) { if ( null != root.left && root.left.data < root.data) { return lnr(root); } if ( null != root.right && root.right.data < root.data) { return rnl(root); } } return true ; } private static boolean rnl(Node n) { if ( null == n) { return true ; } if ( null != n.left && n.left.data < n.data) { return false ; } if ( null != n.right && n.right.data > n.data) { return false ; } return rnl(n.left) && rnl(n.right); } private static boolean lnr(Node n) { if ( null == n) { return true ; } if ( null != n.left && n.left.data > n.data) { return false ; } if ( null != n.right && n.right.data < n.data) { return false ; } return lnr(n.left) && lnr(n.right); } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | import org.junit.Test; import static org.junit.Assert.*; public class BSTTest { /************************************************************************* * Test of isBST method, of class BST. * A good unit tests must provide both true positives and true negatives. * To get a true negative here would require the creation of a binary tree * that is not a BST. No such test is provided here. ************************************************************************/ @Test public void testIsBST() { System.out.println( "" isBST "" ); BST bst = new BST(); assertTrue(BST.isBST(bst.getRoot())); int [] treeTape = { 200 , 100 , 300 , 50 , 150 , 250 , 350 , 25 , 75 , 125 , 175 , 225 , 275 , 325 , 375 , 35 , 212 , 312 , 400 }; for ( int i : treeTape) { bst.add(i); } assertEquals(treeTape.length, bst.size()); //has correct size //test isBST int t = treeTape.length; for ( int i = 0 ; i < treeTape.length; i++) { assertTrue(BST.isBST(bst.getRoot())); bst.delete(treeTape[--t]); } assertEquals( 0 , bst.size()); //has correct size } } |