Geek asks and answers

Check if bst tree or not python

I have a practical interview question that tells me to check if a tree is a balanced search tree or not, and give a verification method ... I have a class like

Class Node:
def __init__(self, k, val):
    self.key = k
    self.value = val
    self.left = None
    self.right = None

and other function definitions for the max and min values ​​of the tree as

def tree_max(node):
    maxleft  = float('-inf') if not node.left  else tree_max(node.left)
    maxright = float('-inf') if not node.right else tree_max(node.right)
    return max(node.value, maxleft, maxright)

def tree_min(node):
    minleft  = float('-inf') if not node.right else tree_min(node.left)
    minright = float('-inf') if not node.left else tree_min(node.right)
    return min(node.value, minleft, minright)

My verification method is how

def verify(node):
    if tree_max(node.left) <= node.value and node.value <= tree_min(node.right):
       if verify(node.left) and verify(node.right):
           return True
       else:
           return False
    else:
        return False

My problem arises when I try to implement a validation method. It seems that I am always mistaken, even when I try to create a BST tree. My implementation is as follows:

root= Node(10, "Hello")
root.left = Node(15, "Fifteen")
root.right= Node(30, "Thirty")

print verify(root)

root = Node(10, "Ten")
root.right = Node(20, "Twenty")
root.left = Node(5, "Five")
root.left.right = Node(15, "Fifteen")

print verify(root)

Both give me False ... Is there a problem with my validation function or my min / max function ... Any help would be appreciated.

+5
source share
2 answers

I see four errors in your code.

  • -, tree_min. , node.right node.left, .

  • -, tree.min node. ( ).

  • -, verify, tree_min tree_max , None. None, , , . min max!

  • , node.value, , node. , node.key. float (, float("-inf")) (, "ten") - Python 3 Python 2, , , , , .

, . , , , False.

, ( , ). Python , if verify tree_max(node.left) <= node.key <= tree_min(node.right). , and, if.

, ( Python 3, , Python 2):

class Node:
    def __init__(self, k, val):
        self.key = k
        self.value = val
        self.left = None
        self.right = None

def tree_max(node):
    if not node:
        return float("-inf")
    maxleft  = tree_max(node.left)
    maxright = tree_max(node.right)
    return max(node.key, maxleft, maxright)

def tree_min(node):
    if not node:
        return float("inf")
    minleft  = tree_min(node.left)
    minright = tree_min(node.right)
    return min(node.key, minleft, minright)

def verify(node):
    if not node:
        return True
    if (tree_max(node.left) <= node.key <= tree_min(node.right) and
        verify(node.left) and verify(node.right)):
        return True
    else:
        return False

root= Node(10, "Hello")
root.left = Node(5, "Five")
root.right= Node(30, "Thirty")

print(verify(root)) # prints True, since this tree is valid

root = Node(10, "Ten")
root.right = Node(20, "Twenty")
root.left = Node(5, "Five")
root.left.right = Node(15, "Fifteen")

print(verify(root)) # prints False, since 15 is to the left of 10
+7

:

INT_MAX = 999999999
INT_MIN = -999999999

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

def isBST(node):
    return (isBSTUtil(node, INT_MIN, INT_MAX))

def isBSTUtil(node, mini, maxi):
    if node is None :
        return True
    if node.data < mini or node.data > maxi :
        return False
    return (isBSTUtil(node.left, mini ,node.data-1 ) and
          isBSTUtil(node.right, node.data+1,maxi))

# Driver program to test above function
root = Node(4)
root.left = Node(2)
root.right = Node(5)
root.left.left = Node(1)
root.left.right = Node(3)

if (isBST(root)):
    print "Is BST"
else:
    print "Not a BST"
0

More articles:


All Articles