Validate Binary Search Tree
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
Examples
root = [2,1,3]
true
1 < 2 < 3, valid BST.
root = [5,1,4,null,null,3,6]
false
Node 3 is in the right subtree of 5 but 3 < 5.
Constraints
- •
The number of nodes in the tree is in the range [1, 10^4] - •
-2^31 <= Node.val <= 2^31 - 1
Approaches
For each node, verify all nodes in left subtree are smaller and all in right subtree are larger.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_valid_bst(root):
def is_smaller(node, val):
if not node:
return True
if node.val >= val:
return False
return is_smaller(node.left, val) and is_smaller(node.right, val)
def is_larger(node, val):
if not node:
return True
if node.val <= val:
return False
return is_larger(node.left, val) and is_larger(node.right, val)
if not root:
return True
if not is_smaller(root.left, root.val) or not is_larger(root.right, root.val):
return False
return is_valid_bst(root.left) and is_valid_bst(root.right)Pass down valid min/max range for each node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_valid_bst(root):
def validate(node, low=float('-inf'), high=float('inf')):
if not node:
return True
if node.val <= low or node.val >= high:
return False
return validate(node.left, low, node.val) and validate(node.right, node.val, high)
return validate(root)Perform inorder traversal and verify the sequence is strictly increasing.
Diagram
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_valid_bst(root):
prev = [None]
def inorder(node):
if not node:
return True
if not inorder(node.left):
return False
if prev[0] is not None and node.val <= prev[0]:
return False
prev[0] = node.val
return inorder(node.right)
return inorder(root)Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Check Each Node Against All Descendants | O(n^2) | O(h) | For each node, verify all nodes in left subtree are smaller and all in right subtree are larger. |
| DFS with Range | O(n) | O(h) | Pass down valid min/max range for each node. |
| Inorder Traversal | O(n) | O(h) | Perform inorder traversal and verify the sequence is strictly increasing. |
For each node, verify all nodes in left subtree are smaller and all in right subtree are larger.
Pass down valid min/max range for each node.
Perform inorder traversal and verify the sequence is strictly increasing.
Common Mistakes
Only checking immediate children instead of all descendants
Not using a range (min/max) to validate BST property
Confusing the BST property (left < root < right, not just left < right)