Advertisement
stefbrad15

isitsearchtree

Mar 26th, 2017
392
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. """ Node is defined as
  2. class node:
  3.    def __init__(self, data):
  4.        self.data = data
  5.        self.left = None
  6.        self.right = None
  7. """
  8.  
  9. def check_binary_search_tree_(root, values = None, leftParent = None, rightParent = None, parent = None):
  10.     #print root.data
  11.     #print root.left
  12.     #print root.right
  13.     toReturn = True
  14.    
  15.     if values == None:
  16.         values = dict()
  17.         leftParent = root
  18.         rightParent = root
  19.         parent = root
  20.     '''
  21.    print root.data
  22.    if root.right:
  23.        print root.right.data
  24.    if root.left:    
  25.        print root.left.data
  26.    print "left par = " + str(leftParent.data)
  27.    print "right par = " + str(rightParent.data)
  28.    print "-------------"
  29.    '''
  30.    
  31.     if not root.data in values:
  32.         values[root.data] = True
  33.     else:
  34.         return False
  35.  
  36.     #print values
  37.     if (root.left):
  38.         if (root.left.data > root.data):
  39.             return False
  40.         elif(root == leftParent):
  41.             toReturn = check_binary_search_tree_(root.left, values, leftParent = root.left, rightParent = root, parent = root)
  42.         elif(root.left.data > leftParent.data):          
  43.             toReturn = check_binary_search_tree_(root.left, values, leftParent = leftParent, rightParent = root, parent = root)
  44.         else:
  45.             return False
  46.  
  47.     if (root.right and toReturn):
  48.         if (root.right.data < root.data):
  49.             return False
  50.         elif (root == rightParent):            
  51.             toReturn = check_binary_search_tree_(root.right, values, leftParent = root, rightParent = root.right, parent = root)
  52.         elif (root.right.data < rightParent.data):
  53.             toReturn = check_binary_search_tree_(root.right, values, leftParent = root, rightParent = rightParent, parent = root)
  54.         else:
  55.             return False
  56.  
  57.     return toReturn
Advertisement
RAW Paste Data Copied
Advertisement