LeetEye LeetEye
Medium Tree Traversal ~5 min

Validate Binary Search Tree

trees validate-binary-search-tree

Problem

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 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.

Examples

Example 1
Input: root = [2,1,3]
Output: true
Example 2
Input: root = [5,1,4,null,null,3,6]
Output: false
3 is in right subtree of 5 but 3 < 5.
Key Insight

Each node must be within a valid range defined by its ancestors.

Pass valid range (min, max) down. Each node must be within range. Left child: upper bound = parent. Right child: lower bound = parent.

How to Approach This Problem

Pattern Recognition: When you see keywords like validate binary search tree trees, think Tree Traversal.

Step-by-Step Reasoning

1 Checking only node.left.val < node.val fails because:
Answer: It doesn't enforce ancestor constraints
A node in the right subtree must be greater than ALL ancestors up the left path, not just its parent.
2 For a node in a BST, its value must be:
Answer: Within a range defined by ancestor path
Going left from ancestor X means value < X. Going right from Y means value > Y. All constraints apply.
3 For the root node, the valid range is:
Answer: [min_int, max_int] or (-infinity, +infinity)
No ancestors means no constraints yet. Any value is valid for root.
4 When moving to left child, the range update is:
Answer: Set new upper bound to parent's value
Left child must be < parent. So parent's value becomes the upper limit.
5 When moving to right child, the range update is:
Answer: Set new lower bound to parent's value
Right child must be > parent. So parent's value becomes the lower limit.
6 BST in-order traversal produces:
Answer: Ascending order
In-order visits left, root, right. In BST, this gives sorted order. If not strictly increasing, not a valid BST.

Solution

def isValidBST(root: TreeNode) -> bool:
    def 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(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))
    
    return validate(root, float(&#039;-inf'), float('inf'))

Complexity Analysis

Time O(n)
Space O(h)

Master This Pattern

Build intuition with interactive MCQs. Practice Tree Traversal problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye