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 · Accepted Answer · 2017-07-28 14:55:21Z

3

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.

edited Jul 28, 2017 at 14:55

answered Jul 28, 2017 at 14:53

Henry

43.9k7 gold badges75 silver badges89 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Team. Coco Over a year ago

In the question, I believe some of the trees that they create contain duplicate values. I ended up passing a few extra test cases when I checked for duplicate values. Can you clarify about the first part of your response? I thought I was checking every node recursively

Team. Coco Over a year ago

I'm confused now as to how to approach this. Should I make an ArrayList and append values to it as I am traversing down and check against the current value?

Henry Over a year ago

You can just pass down the limits (allowed range) into the recursive calls. For example when checking the right subtree of '3' in the example, all nodes must be between 3 and 5.

Collectives™ on Stack Overflow

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

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related