Validate BST

Medium

Python

def is_valid_bst(root,mn=float('-inf'),mx=float('inf')):
    if not root: return True
    if root.val<=mn or root.val>=mx: return False
    return is_valid_bst(root.left,mn,root.val) and is_valid_bst(root.right,root.val,mx)

Java

public boolean isValidBST(TreeNode root){
    return validate(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
boolean validate(TreeNode n,long mn,long mx){
    if(n==null) return true;
    if(n.val<=mn||n.val>=mx) return false;
    return validate(n.left,mn,n.val)&&validate(n.right,n.val,mx);
}

Key Insight

Python default params elegant. Java needs separate helper. float('-inf') vs Long.MIN_VALUE.

Python → Java Differences

float('-inf') vs Long.MIN_VALUE
Default params vs separate helper
Range validation identical

Python

def is_valid_bst(root,mn=float('-inf'),mx=float('inf')):
    if not root: return True
    if root.val<=mn or root.val>=mx: return False
    return is_valid_bst(root.left,mn,root.val) and is_valid_bst(root.right,root.val,mx)

Java

public boolean isValidBST(TreeNode root){
    return validate(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
boolean validate(TreeNode n,long mn,long mx){
    if(n==null) return true;
    if(n.val<=mn||n.val>=mx) return false;
    return validate(n.left,mn,n.val)&&validate(n.right,n.val,mx);
}

Algorithm Steps

1. Maintain valid range
2. Each node must be in range

← Previous All Trees Next →