forked from TheAlgorithms/Python
- Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathis_sorted.py
More file actions
Latest commit
97 lines (86 loc) · 2.99 KB
/
Copy pathis_sorted.py
File metadata and controls
97 lines (86 loc) · 2.99 KB
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
"""
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid binary search tree is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
In effect, a binary tree is a valid BST if its nodes are sorted in ascending order.
leetcode: https://leetcode.com/problems/validate-binary-search-tree/
If n is the number of nodes in the tree then:
Runtime: O(n)
Space: O(1)
"""
from __future__ importannotations
fromcollections.abcimportIterator
fromdataclassesimportdataclass
@dataclass
classNode:
data: float
left: Node|None=None
right: Node|None=None
def__iter__(self) ->Iterator[float]:
"""
>>> root = Node(data=2.1)
>>> list(root)
[2.1]
>>> root.left=Node(data=2.0)
>>> list(root)
[2.0, 2.1]
>>> root.right=Node(data=2.2)
>>> list(root)
[2.0, 2.1, 2.2]
"""
ifself.left:
yieldfromself.left
yieldself.data
ifself.right:
yieldfromself.right
@property
defis_sorted(self) ->bool:
"""
>>> Node(data='abc').is_sorted
True
>>> Node(data=2,
... left=Node(data=1.999),
... right=Node(data=3)).is_sorted
True
>>> Node(data=0,
... left=Node(data=0),
... right=Node(data=0)).is_sorted
True
>>> Node(data=0,
... left=Node(data=-11),
... right=Node(data=3)).is_sorted
True
>>> Node(data=5,
... left=Node(data=1),
... right=Node(data=4, left=Node(data=3))).is_sorted
False
>>> Node(data='a',
... left=Node(data=1),
... right=Node(data=4, left=Node(data=3))).is_sorted
Traceback (most recent call last):
...
TypeError: '<' not supported between instances of 'str' and 'int'
>>> Node(data=2,
... left=Node([]),
... right=Node(data=4, left=Node(data=3))).is_sorted
Traceback (most recent call last):
...
TypeError: '<' not supported between instances of 'int' and 'list'
"""
ifself.leftand (self.data<self.left.dataornotself.left.is_sorted):
returnFalse
ifself.rightand (self.data>self.right.dataornotself.right.is_sorted):
returnFalse
returnTrue
if__name__=="__main__":
importdoctest
doctest.testmod()
tree=Node(data=2.1, left=Node(data=2.0), right=Node(data=2.2))
print(f"Tree {list(tree)} is sorted: {tree.is_sorted=}.")
asserttree.right
tree.right.data=2.0
print(f"Tree {list(tree)} is sorted: {tree.is_sorted=}.")
tree.right.data=2.1
print(f"Tree {list(tree)} is sorted: {tree.is_sorted=}.")