forked from adnanaziz/EPIJudge
-
Notifications
You must be signed in to change notification settings - Fork 0
/
is_tree_a_bst.py
32 lines (24 loc) · 938 Bytes
/
is_tree_a_bst.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
from test_framework import generic_test
def is_binary_tree_bst(tree, low_range=float('-inf'), high_range=float('inf')):
if not tree:
return True
elif not low_range <= tree.data <= high_range:
return False
return (is_binary_tree_bst(tree.left, low_range, tree.data)
and is_binary_tree_bst(tree.right, tree.data, high_range))
def is_binary_tree_bst_alternative(tree):
def inorder_traversal(tree):
if not tree:
return True
elif not inorder_traversal(tree.left):
return False
elif prev[0] and prev[0].data > tree.data:
return False
prev[0] = tree
return inorder_traversal(tree.right)
prev = [None]
return inorder_traversal(tree)
if __name__ == '__main__':
exit(
generic_test.generic_test_main("is_tree_a_bst.py", 'is_tree_a_bst.tsv',
is_binary_tree_bst))