CODEWITHSUNDEEP
pythonpython-3.xalgorithmbinary-treebinary-search-tree
user13527143
user13527143

Reputation:

Binary Tree Search Chech Algorithm Python Not Working

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)

Upvotes: 0

Views: 128

Answers (3)

Siddhant Ranjan
Siddhant Ranjan

Reputation: 170

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.

Upvotes: 0

Yash Shah
Yash Shah

Reputation: 1654

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)

Upvotes: 0

Paul Hankin
Paul Hankin

Reputation: 58221

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.

Upvotes: 1

Related Questions