Verify if a tree is a binary search tree(BST)

原创转载请注明出处：http://agilestyle.iteye.com/blog/2360893

 

Binary Search Tree

• any node in left sub-tree < its parent
• any node in rigth sub-tree > its parent

核心思想：递归

recursively to check values within range

• recursion, update range for both left and right sub-trees and continue verifying
• initial range for the root node (Integer.minimal, Integer.maximum)

package org.fool.java.test;

public class VerifyBSTTest {
    public static void main(String[] args) {
        //       4
        //    2     6
        //  1   3  5  7
        Tree myTree = new Tree(4);
        myTree.left = new Tree(2);
        myTree.right = new Tree(6);
        myTree.left.left = new Tree(1);
        myTree.left.right = new Tree(3);
        myTree.right.left = new Tree(5);
        myTree.right.right = new Tree(7);

        System.out.println("My tree is BST? " + ifBST(myTree, Integer.MIN_VALUE, Integer.MAX_VALUE));
    }

    // the key of this algorithm is to keep track of the reasonable range for current focus node and its sub-trees
    // so we need small and large as two range index values
    private static boolean ifBST(Tree a, int small, int large) {
        // firstly check if Tree is a valid tree node or null
        if (a == null) {
            return true;    // if no elements, return true
        }

        // now check if the current tree node is within (small, large)
        if (a.value > small && a.value < large) {
            // call the recursive part to check its' left and right sub-trees
//            boolean leftBST = ifBST(a.left, small, a.value);
//
//            boolean rightBST = false;
//
//            if(leftBST) {   // if leftBST == false, do not need to check the right half
//                rightBST = ifBST(a.right, a.value, large);
//            }
//
//            return rightBST;

            return ifBST(a.left, small, a.value) && ifBST(a.right, a.value, large);
        } else {
            return false;   // which means the current node finds inappropriate node, return false immediately
        }
    }
}

class Tree {
    public int value;
    public Tree left;
    public Tree right;

    public Tree(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

Console Output

 

Reference

https://www.youtube.com/watch?v=aNtDir94pcA&list=PLlhDxqlV_-vkak9feCSrnjlrnzzzcopSG&index=44 

https://en.wikipedia.org/wiki/Binary_search_tree