98. Validate Binary Search Tree

https://leetcode.com/problems/validate-binary-search-tree

Python

First Solution

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self._is_valid(root, None, None)

    def _is_valid(self, node, min_val, max_val):
        if not node:
            return True

        if (min_val is not None and node.val <= min_val) \
        or (max_val is not None and node.val >= max_val):
            return False

Second Solution

from math import inf


class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        def dfs(node, left, right):
            if not node:
                return True

            if node.val <= left or node.val >= right:
                return False

            return dfs(node.left, left, node.val) and dfs(node.right, node.val, right)

        return dfs(root, -inf, inf)

Rust

DFS

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        Self::dfs(&root, i64::MIN, i64::MAX)
    }

    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, low:i64, high:i64) -> bool{
        match node{
            None => true,
            Some(n) =>{
                let v = n.borrow().val as i64;
                if v <= low || v >= high{
                    false
                } else {
                    Self::dfs(&n.borrow().left, low, v) &&
                    Self::dfs(&n.borrow().right, v, high)
                }
            }
        }
    }
}