- Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtree.py
More file actions
Latest commit
89 lines (77 loc) · 1.96 KB
/
Copy pathtree.py
File metadata and controls
89 lines (77 loc) · 1.96 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
classNode:
def__init__(self, key):
self.left=None
self.right=None
self.val=key
definorder(temp:Node):
ifnottemp:
return
inorder(temp.left)
print(temp.val, end=" ")
inorder(temp.right)
definsert(temp: Node, key:int):
q= []
q.append(temp)
while(len(q)):
temp=q[0]
q.pop(0)
ifnottemp.left:
temp.left=Node(key)
break
else:
q.append(temp.left)
ifnottemp.right:
temp.right=Node(key)
break
else:
q.append(temp.right)
defprintLevelOrder(root: Node):
h=height(root)
foriinrange (1, h+1):
printGivenLevel(root, i)
defprintGivenLevel(root: Node, level: int):
ifrootisNone:
return
iflevel==1:
print("%d"%(root.val))
eliflevel>1:
printGivenLevel(root.left, level-1)
printGivenLevel(root.right, level-1)
defheight(node:Node):
ifnodeisNone:
return0
else:
lheight=height(node.left)
rheight=height(node.right)
if(lheight>rheight):
returnlheight+1
else:
returnrheight+1
defisValidBST(root: Node):
defhelperNode(node: Node, lower=float('-inf'), upper=float('inf')):
ifnotnode:
returnTrue
val=node.val
ifval<=lowerorval>=upper:
returnFalse
ifnothelperNode(node.left, lower, val):
returnFalse
ifnothelperNode(node.right, val, upper):
returnFalse
returnTrue
returnhelperNode(root)
root=Node(10)
root.left=Node(8)
root.left.left=Node(4)
root.left.right=Node(9)
root.right=Node(13)
root.right.left=Node(11)
root.right.right=Node(14)
inorder(root)
#insert(root, 12)
print()
inorder(root)
print()
printLevelOrder(root)
print()
print(isValidBST(root))