I am trying to solve a binary search tree problem, but I can't pass all of the test cases. I need to return true if the tree is a binary search tree, otherwise, I need to return false. I also need to check for duplicates and ensure that every value in the right tree is greater than the root, and that every value in left tree is smaller than the root.
This is the hackerrank challenge that I am trying to solve, the link is here: https://www.hackerrank.com/challenges/ctci-is-binary-search-tree
As it was suggested in my fist question, here, Is tree a binary search tree?
this is the solution which doesn't check for duplicates or whether every value in the right tree is greater than the root, and similarly for the left tree.
For duplicates, I have an idea how to solve it, but not sure how to check whether values are smaller than root on the left tree and bigger on the right tree.
'''
class node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
'''
def checkBST(root):
if root == None or (root.left == None and root.right == None):
return True
elif root.right == None:
return root.left.data < root.data and checkBST(root.left)
elif root.left == None:
return root.right.data >= root.data and checkBST(root.right)
return checkBST(root.left) and checkBST(root.right)
Copyright Notice:Content Author:「user2645029」,Reproduced under the CC 4.0 BY-SA copyright license with a link to the original source and this disclaimer.
Link to original article:https://stackoverflow.com/questions/44887838/is-this-tree-a-binary-search-tree