Validate Binary Search Tree
- 1 min read
- LC-Medium
- Binary-search-tree
3 years ago
Solution
- Same problem as Validate BST
- Just do a traversal of the tree, updating lower bounds and upper bounds as we go down.
- If at any point there is an invalid node, return False
| Time | Space | Explanation |
|---|---|---|
O(n) | O(log n) or O(h) |
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def isValid(root, lb, ub):
if not root:
return True
isNodeValid = root.val > lb and root.val < ub
isLeftValid = isValid(root.left, lb, root.val)
isRightValid = isValid(root.right, root.val, ub)
return isNodeValid and isLeftValid and isRightValid
return isValid(root, -math.inf, math.inf)