Hackerrank: Is This a Binary Tree?

Question

Problem Statement: https://www.hackerrank.com/challenges/is-binary-search-tree

My Solution:

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

Getting "Wrong Answer" for few of the test cases. I know there are a lot of ways to solve this problem, but I am trying to figure out the error in the above solution.

Note: I am not able to debug for those specific test cases because the code doesn't show how the BST is built with those testcases.

Edit: working solution:

  boolean bstUtil(Node root, int min, int max) {
            return root == null 
                || (root.data > min && root.data < max) 
                && bstUtil(root.left, min, root.data) 
                && bstUtil(root.right, root.data, max);
   }

   boolean checkBST(Node root) {
        return bstUtil(root, -1, 10001);
   }

your solution is only good for distinct values

wojtuch
– wojtuch

2017-04-05 12:18:18 +00:00
Commented Apr 5, 2017 at 12:18 — wojtuch
– wojtuch, Commented Apr 5, 2017 at 12:18
@wojtuch that seems in line with the assignment.

Jiri Tousek
– Jiri Tousek

2017-04-05 12:20:17 +00:00
Commented Apr 5, 2017 at 12:20 — Jiri Tousek
– Jiri Tousek, Commented Apr 5, 2017 at 12:20
ah right, I answered without looking at the source

wojtuch
– wojtuch

2017-04-05 12:23:07 +00:00
Commented Apr 5, 2017 at 12:23 — wojtuch
– wojtuch, Commented Apr 5, 2017 at 12:23

Eran · Accepted Answer · 2017-04-05 12:21:34Z

8

Consider the following tree :

Your test would return true, even though this is not a binary search tree (since the left sub-tree of the root contains a node (6) larger than the root (3)).

It's not enough to check that the left sub-tree is a binary search tree and the left child is smaller than the root. You must also check that every node of the left child is smaller than the root.

answered Apr 5, 2017 at 12:21

Eran

395k57 gold badges726 silver badges793 bronze badges

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

2 Comments

Abhishek Over a year ago

I had another approach where I did inorder traversal and checked if the result is sorted, but i have failing cases there as well. Code: ideone.com/fXcxup. Any help would be appreciated!

Eran Over a year ago

@Abhishek If you post that code as a question, I might be able to help (or someone else will).

Collectives™ on Stack Overflow

Hackerrank: Is This a Binary Tree?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related