Code for checking if a tree is a Binary Search Tree in Java is failing test cases. Unsure why

Question

I began doing a BST problem on Hackerrank, where I should return true if a tree is is a BST, and false otherwise. I am failing 4 out of the 20 total cases and I am not sure why. The person who made this problem did not provide detail information on how he/she handles the inputs and makes the tree.

Here is my code:

Map<Integer, Integer> numMap = new HashMap<Integer, Integer>();


    boolean checkDuplicates(int val){
        if(numMap.containsKey(val)){
            return false;
        }
        else{
            numMap.put(val, 1);
            return true;
        }
    }


    boolean checkBST(Node root) {
        if(root.left == null && root.right == null){
            return (true && checkDuplicates(root.data));
        }
        else if(root.left.data > root.data || root.right.data < root.data){
            return false;
        }
        else{
            if(root.left == null){
                return (checkBST(root.right) && checkDuplicates(root.data));
            }
            else if(root.right == null){
                return (checkBST(root.left) && checkDuplicates(root.data));
            }
            else{
                return (checkBST(root.left) && checkBST(root.right) && checkDuplicates(root.data));
            }
        }
     }

Here is a link to the hackerrank problem: https://www.hackerrank.com/challenges/ctci-is-binary-search-tree

What am I doing wrong/overlooking here?

Henry Henry · Accepted Answer · 2017-07-28T14:53:20

Every node in the subtree must be smaller/larger than the root. You just check the root of the subtree.

For example this is not a BST:

       5
  3       7
1   6

This condition also implies that there are no duplicates, you don't have to check for that separately.

Code for checking if a tree is a Binary Search Tree in Java is failing test cases. Unsure why

1 Answers