98. Valid bst

98_solution1.c

#include "tree_node.h"
#include <limits.h>
#include <stdbool.h>

static bool dfs(struct TreeNode *root, long lowerbound, long upperbound) {
  if (!root)
    return true;

  if (root->val <= lowerbound || root->val >= upperbound)
    return false;

  return dfs(root->right, root->val, upperbound) &&
         dfs(root->left, lowerbound, root->val);
}

bool isValidBST(struct TreeNode *root) { return dfs(root, LONG_MIN, LONG_MAX); }

tree_node.h

#pragma once

#include <stddef.h>

// Definition for a binary tree node.
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

98_solution1.cpp

#include "tree_node.h"
#include <climits>

class Solution {
public:
  bool isValidBST(TreeNode *root) { return dfs(root, LONG_MIN, LONG_MAX); }

  bool dfs(TreeNode *root, long lowerbound, long upperbound) {
    if (!root)
      return true;

    if (root->val <= lowerbound || root->val >= upperbound)
      return false;

    return dfs(root->right, root->val, upperbound) &&
           dfs(root->left, lowerbound, root->val);
  }
};

tree_node.h

#pragma once

// Definition for a binary tree node.
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

98_solution1.go

package trees

import "math"

func isValidBST(root *TreeNode) bool {
    var dfs func(node *TreeNode, lowerbound, upperbound int) bool
    dfs = func(node *TreeNode, lowerbound, upperbound int) bool {
        if node == nil {
            return true
        }
        if node.Val <= lowerbound || node.Val >= upperbound {
            return false
        }
        return dfs(node.Right, node.Val, upperbound) &&
            dfs(node.Left, lowerbound, node.Val)
    }

    return dfs(root, math.MinInt, math.MaxInt)
}

tree_node.go

package trees

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

98_solution1.java

class Solution {
    public boolean isValidBST(TreeNode root) {
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean dfs(TreeNode node, long lowerbound, long upperbound) {
        if (node == null)
            return true;

        if (node.val <= lowerbound || node.val >= upperbound)
            return false;

        return dfs(node.right, node.val, upperbound) &&
               dfs(node.left, lowerbound, node.val);
    }
}

TreeNode.java

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

98_solution1.js

const TreeNode = require("./tree_node");

var isValidBST = function (root) {
  const dfs = (node, lowerbound, upperbound) => {
    if (!node) return true;
    if (node.val <= lowerbound || node.val >= upperbound) return false;
    return (
      dfs(node.right, node.val, upperbound) &&
      dfs(node.left, lowerbound, node.val)
    );
  };

  return dfs(root, -Infinity, Infinity);
};

tree_node.js

// Definition for a binary tree node.
function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

module.exports = TreeNode;

98_solution1.py

from typing import Optional

from tree_node import TreeNode


class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(node: Optional[TreeNode], lowerbound: float, upperbound: float) -> bool:
            if not node:
                return True
            if node.val <= lowerbound or node.val >= upperbound:
                return False
            return dfs(node.right, node.val, upperbound) and dfs(
                node.left, lowerbound, node.val
            )

        return dfs(root, float("-inf"), float("inf"))

tree_node.py

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

98_solution1.rs

use std::cell::RefCell;
use std::rc::Rc;

use crate::tree_node::TreeNode;

type Link = Option<Rc<RefCell<TreeNode>>>;

impl Solution {
    pub fn is_valid_bst(root: Link) -> bool {
        Self::dfs(&root, i64::MIN, i64::MAX)
    }

    fn dfs(node: &Link, lowerbound: i64, upperbound: i64) -> bool {
        match node {
            None => true,
            Some(n) => {
                let n = n.borrow();
                let val = n.val as i64;
                if val <= lowerbound || val >= upperbound {
                    return false;
                }
                Self::dfs(&n.right, val, upperbound) && Self::dfs(&n.left, lowerbound, val)
            }
        }
    }
}

tree_node.rs

use std::cell::RefCell;
use std::rc::Rc;

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}