-
Notifications
You must be signed in to change notification settings - Fork 0
/
Check_BST.py
58 lines (48 loc) · 1.74 KB
/
Check_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
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
"""
Check for BST (Binary Search Tree)
Given the root of a binary tree. Check whether it is a BST or not.
Note: We are considering that BSTs can not contain duplicate Nodes.
A BST 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.
The Task:
The task is to complete the function isBST() which takes the root of the tree as a parameter
and returns true if the given binary tree is BST, else returns false.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the BST).
"""
# first way
class Solution:
def checkBST(self, root, MIN, MAX):
if root == None:
return 1
if root.data < MIN or root.data > MAX:
return 0
return self.checkBST(root.left, MIN, root.data - 1) and self.checkBST(root.right, root.data + 1, MAX)
def isBST(self, root):
INT_MAX = 4294967296
INT_MIN = -4294967296
return self.checkBST(root, INT_MIN, INT_MAX)
# second way: if InOrder traversal of BST is sorted, it is BST
class Solution:
def isBST(self, root):
stack = []
arr = []
if root==None:
return
current = root
while (True):
if current:
stack.append(current)
current = current.left
elif stack:
current = stack.pop()
arr.append(current.data)
current = current.right
else:
break
for i in range(1,len(arr)):
if arr[i]<=arr[i-1]:
return False
return True