-
Notifications
You must be signed in to change notification settings - Fork 19
/
25_BST-Verification.py
43 lines (31 loc) · 903 Bytes
/
25_BST-Verification.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#!/usr/bin/python
# coding=utf-8
'''
__author__ = 'sunp'
__date__ = '2019/2/20'
Given a binary tree, write a function to test if the tree is a binary search tree.
Notes: node.left.val <= node.val < node.right.val
'''
import sys
class TreeNode(object):
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_bst(root):
return _helper(root, -sys.maxsize-1, sys.maxsize)
def _helper(node, a, b):
if not node:
return True
if node.val <= a or node.val > b:
return False
return _helper(node.left, a, node.val) and _helper(node.right, node.val, b)
if __name__ == '__main__':
test = TreeNode(2)
test.left = TreeNode(2)
test.left.left = TreeNode(1)
test.right = TreeNode(3)
assert is_bst(None)
assert is_bst(test)
test.right.val = 2
assert not is_bst(test)