Sunday, December 3, 2023
HomeSolving Leetcode 98. Validate Binary Search Tree

# 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()

```
RELATED ARTICLES