-
Notifications
You must be signed in to change notification settings - Fork 2
/
ValidateBinarySearchTree.py
124 lines (94 loc) · 2.13 KB
/
ValidateBinarySearchTree.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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
from typing import List
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
if not root:
return True
valueArray = []
self.inorderTraversal(root, valueArray)
if len(valueArray) > 1:
for i in range(0, len(valueArray)-1):
if valueArray[i] >= valueArray[i+1]:
return False
return True
def inorderTraversal(self, root: TreeNode, valArray: List[int]):
if not root:
return []
if root.left:
self.inorderTraversal(root.left, valArray)
valArray.append(root.val)
if root.right:
self.inorderTraversal(root.right, valArray)
return valArray
########
# Test #
########
# Empty Tree
print(Solution().isValidBST(None))
# expected: True
##################################
# 0
root = TreeNode(0)
print(Solution().isValidBST(root))
# expected: True
##################################
# 1
# /
# 1
root = TreeNode(1)
node1 = TreeNode(1)
root.left = node1
print(Solution().isValidBST(root))
# expected: False
##################################
# 2
# / \
# 1 3
root = TreeNode(2)
node1 = TreeNode(1)
node2 = TreeNode(3)
root.left = node1
root.right = node2
print(Solution().isValidBST(root))
# expected: True
##################################
# 5
# / \
# 1 4
# / \
# 3 6
root = TreeNode(5)
node1 = TreeNode(1)
node2 = TreeNode(4)
node3 = TreeNode(3)
node4 = TreeNode(6)
root.left = node1
root.right = node2
node2.left = node3
node2.right = node4
print(Solution().isValidBST(root))
# expected: False
##################################
# 5
# / \
# 4 7
# / / \
# 1 6 8
root = TreeNode(5)
node1 = TreeNode(4)
node2 = TreeNode(7)
node3 = TreeNode(1)
node4 = TreeNode(6)
node5 = TreeNode(8)
root.left = node1
root.right = node2
node1.left = node3
node2.left = node4
node2.right = node5
print(Solution().isValidBST(root))
# expected: True