Skip to content

Instantly share code, notes, and snippets.

@danong
Created October 5, 2018 21:48
Show Gist options
  • Save danong/f58aff34bbcbfa086499bdfd3373b26e to your computer and use it in GitHub Desktop.
Save danong/f58aff34bbcbfa086499bdfd3373b26e to your computer and use it in GitHub Desktop.
Given the head node of a binary tree, check if the tree is a binary search tree.
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_bst_rec(node: Node, min_v: object = None, max_v: object = None) -> bool: # todo should use float('inf') and float('-inf')
if (min_v and node.val < min_v) or (max_v and node.val > max_v):
return False
if node.left:
if node.left.val > node.val or not is_bst_rec(node.left, min_v, node.val):
return False
if node.right:
if node.right.val < node.val or not is_bst_rec(node.right, node.val, max_v):
return False
return True
def is_bst_iter(node: Node):
if node is None:
return True
stack = []
last = float('-inf')
while stack or node:
if node:
stack.append(node)
node = node.left
else:
node = stack.pop()
if node.val <= last:
return False
last = node.val
node = node.right
return True
if __name__ == '__main__':
a = Node(1)
b = Node(2)
c = Node(3)
d = Node(4)
c.left = b
b.left = a
print(is_bst_iter(c))
c.right = d
print(is_bst_iter(c))
c.right = None
b.right = d
print(is_bst_iter(c))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment