Validate BST 25 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

Determine if a binary tree is a valid BST. A common mistake: just checking left < root < right is NOT enough!

#       5
#      / \
#     1   4        ← Invalid! 4 < 5 but...
#        / \
#       3   6      ← 3 is in RIGHT subtree of 5, but 3 < 5!

#       5
#      / \
#     1   7        ← Valid!
#        / \
#       6   8

The correct approach: each node must be within a valid range:

Root: range is (-∞, +∞)
Left child of node X: range is (-∞, X)
Right child of node X: range is (X, +∞)
Pass min_val and max_val bounds down recursively

Alternative: do an inorder traversal and check if the output is strictly increasing. If it is, it's a valid BST!

📋 Instructions

Implement `is_valid_bst(root)` using the range-checking approach. Test with both valid and invalid trees.

Helper function validate(node, min_val, max_val). If not node: return True. If node.val <= min_val or node.val >= max_val: return False. Return validate(left, min_val, node.val) and validate(right, node.val, max_val).

🧪 Test Cases

Input

is_valid_bst(t1)

Expected

True

Boolean check

Input

is_valid_bst(t2)

Expected

False

Boolean check

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›