#56 Medium Time O(n) Space O(n) Animated

Validate Binary Search Tree

Validate if a binary tree is a valid BST.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Tree traversal with recursive contracts

Ask each subtree for exactly the information its parent needs, then combine the two answers.

Approach: DFS (Recursive bounds)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Ask each subtree for exactly the information its parent needs, then combine the two answers.

Common Pitfall

Define the base case before combining left and right subtree results.

Description

Validate if a binary tree is a valid BST.

Constraints

Time Complexity: O(n)
Space Complexity: O(n)

Solution — DFS (Recursive bounds)

TimeO(n) SpaceO(n)

Implementation Plan

Translate the invariant into these small, testable moves.

Define what one recursive call returns.
Handle an empty node.
Recurse into children.
Combine the child results at the current node.

def isValidBST(root):
    def valid(node, left, right):
        if not node:
            return True
        if not (node.val < right and node.val > left):
            return False
            
        return (valid(node.left, left, node.val) and 
                valid(node.right, node.val, right))
                
    return valid(root, float("-inf"), float("inf"))

Count Good Nodes in Binary Tree

Kth Smallest Element in a BST

Validate Binary Search Tree

Steps

Description

Constraints

Tags

Solution — DFS (Recursive bounds)