98. Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows:

• The left of a node contains only nodes with keys strictly less than the node’s key.
• The right subtree of a node contains only nodes with keys strictly greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Constraints:

• The number of nodes in the tree is in the range $[1, 104]$.
• $-2^{31}$ <= node.val <= $2^{31} - 1$

To satisfy the BST property, we have to consider the values of the subtrees in relation to the root value root.

• For the left subtree, all values must be less than root, so all nodes lie in the range (-inf, root).
• For the right subtree, all values must be greater than root, so all nodes lie in the range (root, inf). However, this applies at all levels of the tree! In other words, we must keep track of a range (min_val, max_val) for each node, and update this accordingly as we recurse down each of its subtrees.
• For the left subtree, it must be strictly less than node.val, so we pass in node.val for the new maximum.
• For the right subtree, it must be strictly greater than the root, so we pass in node.val for the new minimum. Notice that if the node itself is valid, then min_val <= node.val <= max_val, so we are guaranteed that passing in node.val shrinks the range. Thus, we simply check if the node is valid before we recurse down to its children.

def isValid(node: Optional[TreeNode], 
			min_val: Optional[int], 
			max_val: Optional[int]) -> bool:
	 
	if not node: return True
	
	# check if root is valid
	if ((min_val is not None and node.val <= min_val) 
	 or (max_val is not None and node.val >= max_val)):
	   return False
	
	# root is valid - check if subtrees are valid
	return (isValid(node.left, min_val, node.val) 
		and isValid(node.right, node.val, max_val))

We only have to call this function from the root to check the full BST. We can pass the range as (None, None) since the root can be of any value.

def isValidBST(root: Optional[TreeNode]) -> bool:
	def isValid(node: Optional[TreeNode], 
				min_val: Optional[int], 
				max_val: Optional[int]) -> bool:
		
		if not node: return True
		
		# check if root is valid
		if ((min_val is not None and node.val <= min_val) 
		 or (max_val is not None and node.val >= max_val)):
		   return False
		
		# root is valid - check if subtrees are valid
		return (isValid(node.left, min_val, node.val) 
			and isValid(node.right, node.val, max_val))
	
	return isValid(root, None, None)

Time Complexity

The algorithm recurses down, checking every node. Notice at each node, there are constant time operations. Thus for a tree with $n$ nodes, the algorithm has $\mathcal{O}(n)$ time complexity.

Space Complexity

No memory is used to store variables. However, notice that there is recursive overhead, since the algorithm recurses through the entirety of the tree before terminating at the root. Since there are $n$ nodes, there will be $n$ calls—thus the space complexity is $\mathcal{O}(n)$.