# Python implementation # Here we define a node class Node: def __init__(self, val): self.val = val self.left = None self.right = None def visitInorder(self, output): if self.left != None: self.left.visitInorder(output) # Visit ourself output.append(self.val) if self.right != None: self.right.visitInorder(output) def testIfBinarySearchTree(root): # total = O(n) + O(n) = O(n) # Generate the inorder traversal O(n) output = [] root.visitInorder(output) # See if it's sorted O(n) for x in range(1, len(output)): prev = output[x-1] cur = output[x] if prev > cur: return False return True # A test example root = Node(5) root.left = Node(3) root.left.right = Node(4) root.left.left = Node(2) testIfBinarySearchTree(root)