Assume you are given a binary search tree. Check that the binary search tree is “legal”. A binary search tree is legal if it obeys all the properties of the binary search tree. They are the following: All the nodes on the left is smaller than the root. All the nodes on the right is larger than the root. Both the right and the left subtrees are also legal binary search trees. Input Format Input: root = [6,4,9] The list represents how the tree looks like. This will mean: 6 / \ 4 9 This will be true Input: root = [6,4,9,1,None,7,10] The list represents how the tree looks like. This will mean: 6 / \ 4 9 / \ / \ 1 N 7 10 This will be true Input: root = [6,4,9,1,None,7,2] The list represents how the tree looks like. This will mean: 6 / \ 4 9 / \ / \ 1 N 7 2 This will be false Constraints Use the following starter code: from sys import stdin class Node: def __init__(self, data): self.left = None self.right = None self.data = data def set_child(temp_list,index): if index >= len(temp_list) or temp_list[index] == None: return None temp = Node(temp_list[index]) temp.left = set_child(temp_list, index*2+1) temp.right = set_child(temp_list, index*2+2) return (temp) def isValidBST(root): #todo if __name__ == '__main__': flag = True for line in stdin: nums = list(line[1:-1].strip().split(",")) nums = [int(item) if item.isnumeric() else None for item in nums] root = set_child(nums, 0) print(isValidBST(root)) Output Format Output: true True if it is a BST. Else if it is not. Sample Input 0 [6,4,9,1,None,7,2] Sample Output 0 False Sample Input 1 [6,4,9,1,None,7,10] Sample Output 1 True
Assume you are given a binary search tree. Check that the binary search tree is “legal”. A binary search tree is legal if it obeys all the properties of the binary search tree. They are the following: All the nodes on the left is smaller than the root. All the nodes on the right is larger than the root. Both the right and the left subtrees are also legal binary search trees.
Input Format
Input: root = [6,4,9] The list represents how the tree looks like. This will mean:
6
/ \
4 9
This will be true
Input: root = [6,4,9,1,None,7,10] The list represents how the tree looks like. This will mean:
6
/ \
4 9
/ \ / \
1 N 7 10
This will be true
Input: root = [6,4,9,1,None,7,2] The list represents how the tree looks like. This will mean:
6
/ \
4 9
/ \ / \
1 N 7 2
This will be false
Constraints
Use the following starter code:
from sys import stdin
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
def set_child(temp_list,index):
if index >= len(temp_list) or temp_list[index] == None:
return None temp = Node(temp_list[index])
temp.left = set_child(temp_list, index*2+1)
temp.right = set_child(temp_list, index*2+2)
return (temp)
def isValidBST(root):
#todo
if __name__ == '__main__': flag = True for line in stdin:
nums = list(line[1:-1].strip().split(","))
nums = [int(item) if item.isnumeric() else None for item in nums]
root = set_child(nums, 0)
print(isValidBST(root))
Output Format
Output: true
True if it is a BST. Else if it is not.
Sample Input 0
[6,4,9,1,None,7,2]
Sample Output 0
False
Sample Input 1
[6,4,9,1,None,7,10]
Sample Output 1
True
Step by step
Solved in 2 steps
