Solving Leetcode 98. Validate Binary Search Tree

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.

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a 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. A single node tree is a BST

Code in JavaScript

var isValidBST = function(root) {
    const isValid = (root, low, high) => {
        if (!root) {return true}
        if (root.val <= low || root.val >= high) { return false }
        if (root.left && root.val <= root.left.val ) { return false }
        if (root.right && root.val >= root.right.val ) { return false }
        
        return isValid(root.left, Math.min(root.val, low), Math.min(root.val, high)) && isValid(root.right, Math.max(root.val, low), Math.max(root.val, high))
    }
    return isValid(root, -Infinity, Infinity)
};

Code in Python

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

class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        res = []
        self.inOrder(root, res)
        return res == sorted(res) and len(res) == len(set(res))
        
    def inOrder(self, root, res):
        if not root: return []
        l = self.inOrder(root.left, res)
        if l:
            res.extend(l)
        res.append(root.val)
        r = self.inOrder(root.right, res)
        if r:
            res.extend()