Binary Tree Search Chech Algorithm Python Not Working

Question

I wrote this algorithm for a coding challenge on HackerRank to determine if a give binary tree is a BST. Yet in some cases when the tree is not a BST my algorithm returns True anyway. I couldn't find what was wrong, everything seems ok, right? Or is there something I don't know about BSTs?

Node is defined as:

class node:
 def __init__(self, data):
 self.data = data
 self.left = None
 self.right = None

My algorithm is

def checkBST(root):
 if not root:
 return True
 else:
 if root.left and root.left.data >= root.data:
 return False
 if root.right and root.right.data <= root.data:
 return False
 return checkBST(root.left) and checkBST(root.right)

Answer 1

A binary search tree has all the nodes on the left branch less than the parent node, and all the nodes on the right branch greater than the parent node.

So your code fails on a case like this:

 5
 / \
 4 7
 / \
 2 6

It's not a valid BST because if you searched for 6, you'd follow the right branch from the root, and subsequently fail to find it.

Answer 2

Take a look at a picture below for which your code is giving an incorrect answer: enter image description here

Where are you going wrong:

1. if an element exists on the left subtree if there exists a node with a value greater than root.

2. if an element exists on the right subtree if there exists a node with a value smaller than root.

You should try this approach :

if not root:
 return True
else:
 if root.left and maximumOfSubtree(root.left) >= root.data:
 return False
 if root.right and minimumOfSubtree(root.right) <= root.data:
 return False
return checkBST(root.left) and checkBST(root.right)

• Paul Hankin: The approach you suggest is quadratic in the height of the tree.
• Yash Shah: @PaulHankin Yes, but can be optimized if the author understands where he/she is going wrong...

Answer 3

so the problem is to determine whether the given tree is a BST or not.
the best way to find out is through an inorder traversal.

• Do In-Order Traversal of the given tree and store the result in a temp array.
• Check if the temp array is sorted in ascending order, if it is, then the tree is BST.

this can be the approach

def check_binary_search_tree_(root):
 visited = []
 def traverse(node): 
 if node.left: traverse(node.left)
 visited.append(node.data)
 if node.right: traverse(node.right)
 traverse(root)
 fc = {}
 for i in visited:
 if i in fc:
 return False
 else:
 fc[i]=1
 m = sorted(visited)
 if visited==m:
 return True
 return False

refer to this for other methods https://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
method 1 and method 2 are similar to your approach so it will help you to understand that too.