Monday, December 29, 2014

Checking if a given Binary Tree is a Binary Search Tree [Top-Down and Bottom-Up (Recursive) Approaches]

Q. Implement a function to check if a binary tree is a binary search tree.

Source:

public class Code{
    
    public class Node{
        int value;
        Node left, right;
        Node(){}
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
        
        @Override
        public String toString(){
            return "Value: "+value;
        }
    }
    
    Node root; 
    
    Integer previous = null;
    boolean isBSTMethod1(Node node){
       if(node == null)return true;
       if(!isBSTMethod1(node.left))return false;
       if(previous!=null && previous > node.value)return false;
       previous = node.value;
       return isBSTMethod1(node.right);
    }
    
    //Top down check
    boolean isBSTMethod2(Node node, Integer min, Integer max){
       if(node == null) return true;
       if((max != null && node.value >= max) || 
          (min != null && node.value < min)) return false;
       if(!isBSTMethod2(node.left, min, node.value)) return false;
       return isBSTMethod2(node.right, node.value, max);
    }
    
    class Pair{
        Integer min, max; 
        Pair(Integer min, Integer max){
            this.min = min;
            this.max = max;
        }
    }
    
    //Bottom Up Check
    boolean isBSTMethod3test(){
        isBST = true;
        isBSTMethod3(root);
        return isBST;
    }
    
    boolean isBST;
    Pair isBSTMethod3(Node node){ 
        if(node.left == null && node.right == null) return new Pair(node.value, node.value);
         
        Pair left, right;
        
        if(node.left == null) left = new Pair(node.value, null);
        else left = isBSTMethod3(node.left);
        if(!isBST)return null;
        
        if(node.right == null) right = new Pair(null, node.value);
        else right = isBSTMethod3(node.right);
        if(!isBST)return null;
        
        if((left.max != null && left.max >= node.value) || (right.min != null && right.min<node.value))
            isBST = false;
        
        return new Pair(left.min, right.max); 
    }
    
    //Other functions
    void makeCustom(){
        //Tree 1 - Comment out others
        root = new Node(5);
        root.left = new Node(2);
        root.right = new Node(10);
        root.left.right = new Node(40);
        root.left.left = new Node(1); 
        root.left.right.left = new Node(3);
        root.right.left = new Node(7);
        root.right.right = new Node(10); 
        
        /*
            Failure case for Method1. This binary tree mush have values of 
            node.right >= node && node.left < node
        */
        
        /*
          root = new Node(4);
          root.left = new Node(5);
          root.right = new Node(5);
        */
        
        /*
          //Tree 2
          root = new Node(25);
          root.left = new Node(10);
          root.right = new Node(40);
          root.left.right = new Node(20);
          root.left.left = new Node(5); 
          root.left.left.left = new Node(3); 
        */
        
        //Tree 3 
        root = new Node(35);
        root.left = new Node(15);
        root.left.left = new Node(7);
        root.left.left.left = new Node(4);
        root.left.left.right = new Node(9);
        root.left.right = new Node(20);
        root.left.right.left = new Node(17);
        root.left.right.right = new Node(34);
        root.right = new Node(55);
        root.right.left = new Node(40);
        root.right.left.left = new Node(37);
        root.right.left.right = new Node(50);
        root.right.right = new Node(60);
        root.right.right.left = new Node(57);
        root.right.right.right = new Node(65);
       
    }
    
    void printTree(String string){
        System.out.println(string);
        inorder(root);
    }
    
    void inorder(Node node){
        if(node==null)return;
        inorder(node.left);
        System.out.println(node.value);
        inorder(node.right);
    }
    
    public static void main(String[] args){
        Code tree = new Code();
        tree.makeCustom();
        System.out.println("Is this tree a BST? : "+tree.isBSTMethod2(tree.root, null, null));
        System.out.println("Is this tree a BST? : "+tree.isBSTMethod3test());
    }
}

Output:

Is this tree a BST? : true
Is this tree a BST? : true

No comments:

Post a Comment