Approach
- Q.preorder_traversal ,postorder_traversal orinorder_traversal ?
- Ans.
Striver series notes
- Given abinary_tree tell if it is abinary_search_tree
- What isbinary_search_tree ?
- Everything on left should be smaller than it and everything on right should be greater than node itself.
- Valid Binary Search Tree,
- binary search tree is my previous attempt at same problem.
- Every node has to be in a range,
- IM is Integer min/ max,
- To implement theapproach_should_be_mentioned_first
- call checkBST withmultiple_recursion_call
Code
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def checkBST(node, min_val=float('-inf'), max_val=float('inf')):
if node is None:
return True
elif node.value < min_val or node.value > max_val:
return False
else:
return checkBST(node.left, min_val, node.value - 1) and checkBST(node.right, node.value + 1, max_val)
root = Node(5)
twoVal = Node(2)
sixVal = Node(6)
oneVal = Node(1)
sixVal.left = oneVal
root.left = twoVal
root.right = sixVal
print(checkBST(root))
Another one:
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def helper(root, min_val=float("-inf"), max_val=float("inf")):
if root is None:
return True
return (min_val < root.val < max_val and helper(root.left, min_val, root.val) and helper(root.right, root.val, max_val))
return helper(root)Iterative solution using Queue
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
queue = deque()
queue.append((root, float("-inf"), float("inf")))
while queue:
node, min_val, max_val = queue.popleft()
if node:
if min_val >= node.val or node.val >= max_val:
return False
if node.left:
queue.append((node.left, min_val, node.val))
if node.right:
queue.append((node.right, node.val, max_val))
return TrueAttempt
'''
approach:
every element needs to be checked for falling in range,
there will be min and max vars that will need to be passed
do i need a helper function for recursion? yes
'''
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def isValidBST(self, root):
def helper(root, min_val=float("-inf"), max_val=float("inf")):
if root is None:
return True
return (min_val < root.val < max_val and helper(root.left, min_val, root.val) and helper(root.right, root.val, max_val))
return helper(root)