Validate BST

Check whether a given binary tree satisfies the BST property.

bst recursion validation trees

Write a function `is_valid_bst(root)` that takes the root of a binary tree and returns `True` if the tree is a valid Binary Search Tree (BST), otherwise `False`. A BST is defined as:
- The left subtree of a node contains only nodes with keys **less than** the node's key.
- The right subtree of a node contains only nodes with keys **greater than** the node's key.
- Both the left and right subtrees must also be binary search trees.

The tree is represented by a `TreeNode` class with attributes `value`, `left`, and `right` (where `left` and `right` are either `TreeNode` or `None`). The test harness will construct TreeNode objects from dictionaries when calling your function, so your solution must access attributes via `node.value`, `node.left`, `node.right`. All node values are unique integers.

Constraints

The number of nodes in the tree is in [0, 10^4]. Node values are integers in the range [-10^9, 10^9]. The tree height can be up to O(n). The solution should use O(n) time and O(h) auxiliary space (where h is the tree height), but any correct solution is acceptable.

Example

>>> # Example 1: Valid BST
>>> root = TreeNode(2)
>>> root.left = TreeNode(1)
>>> root.right = TreeNode(3)
>>> is_valid_bst(root)
True
>>> # Example 2: Invalid BST (right child equals root)
>>> root = TreeNode(5)
>>> root.left = TreeNode(1)
>>> root.right = TreeNode(4)
>>> root.right.left = TreeNode(3)
>>> root.right.right = TreeNode(6)
>>> is_valid_bst(root)
False
>>> # Example 3: Empty tree
>>> is_valid_bst(None)
True

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use an inorder traversal: a valid BST yields values in strictly increasing order.

Track the previously visited value during traversal and ensure each new value is greater than it.

Alternatively, write a recursive helper that passes allowed lower and upper bounds for each subtree.

For an empty tree, return True.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.