Wrong Answer in 'Is this a Binary Search Tree' on HackerRank

Question

For the purposes of this challenge, we define a binary tree to be a binary search tree with the following ordering requirements:

The value of every node in a node's left subtree is less than the data value of that node. The value of every node in a node's right subtree is greater than the data value of that node. Given the root node of a binary tree, can you determine if it's also a binary search tree?

Complete the function in your editor below, which has parameter: a pointer to the root of a binary tree. It must return a boolean denoting whether or not the binary tree is a binary search tree. You may have to write one or more helper functions to complete this challenge.

Input Format

You are not responsible for reading any input from stdin. Hidden code stubs will assemble a binary tree and pass its root node to your function as an argument.

Constraints: 0<=data<=10^4

Output Format

You are not responsible for printing any output to stdout. Your function must return true if the tree is a binary search tree; otherwise, it must return false. Hidden code stubs will print this result as a Yes or No answer on a new line.

My Code:

""" Node is defined as
class node:
  def __init__(self, data):
      self.data = data
      self.left = None
      self.right = None
"""
def check_binary_search_tree_(root):
    if root is None or (root.left is None and root.right is None):
        return True
    if root.left.data>=root.data or root.right.data<=root.data:
        return False
    check_binary_search_tree_(root.left)
    check_binary_search_tree_(root.right)
    return True

Why am I getting Wrong Answer?

The problem says: "The value of every node in a node's left subtree is less than the data value of that node. The value of every node in a node's right subtree is greater than the data value of that node." Your code uses <= and >=. Could be a problem. — RootTwo
– RootTwo, Commented Nov 2, 2020 at 18:48

SomeDude · Accepted Answer · 2020-11-02 19:03:46Z

3

The problem with your code is

first you didn't do :

return check_binary_search_tree_(root.left) and check_binary_search_tree_(root.right)
next even if you do that, you are forgetting to keep the root's value in mind while checking the BST property for left and right children. It could be that your left child is totally a good BST but it fails to be a BST when you consider its parent. Look at the below example:
```
              6
          4       7
       2     8
```
The subtree rooted at 4 is a good BST but fails when you consider its root's value of 6.
The solution is then to check the proper range of values at each node i.e.

left_limit < root.data < right_limit

You could write your function as :

def check_binary_search_tree_(root, min = -math.inf, max = math.inf):
    if root is None:
        return True
    if root.data > min and root.data < max:
        return check_binary_search_tree_(root.left, min, root.data) and check_binary_search_tree_(root.right, root.data, max)
    return False

answered Nov 2, 2020 at 19:03

SomeDude

14.3k5 gold badges26 silver badges49 bronze badges

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

1 Comment

WebViewer Over a year ago

According to hackerrank.com/challenges/is-binary-search-tree/problem the parent is irrelevant. Only sub-trees (children) should be considered. but it is implied in the word "every" in "...value of every node in a node's left subtree...". IOW, each root needs to verify that all of its grandchildren/offsprings do not violate the BST criteria.

roddar92 · Accepted Answer · 2020-11-02 18:56:51Z

0

check_binary_search_tree_(root.left)
check_binary_search_tree_(root.right)

You don't return a result of these recursive functions. Try to do:

return check_binary_search_tree_(root.left) and check_binary_search_tree_(root.right)

Full code example that works:

def check_binary_search_tree_(root):
    def isValid(node, lower=float('-inf'), upper=float('inf')):
        if not node:
            return True
        if node.data <= lower or node.data >= upper:
            return False
        return isValid(node.left, lower, node.data) and isValid(node.right, node.data, upper)
    return isValid(root)

edited Nov 2, 2020 at 18:56

answered Nov 2, 2020 at 18:39

roddar92

3661 silver badge4 bronze badges

1 Comment

greybeard Over a year ago

That's not the only problem.

Collectives™ on Stack Overflow

Wrong Answer in 'Is this a Binary Search Tree' on HackerRank

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related