Validate Binary Search Tree
Given the root of a binary tree, return true if it is a valid binary search tree (BST) and false otherwise.
A tree is a valid BST when, at every node:
- every value in the node's left subtree is strictly less than the node's value,
- every value in its right subtree is strictly greater than the node's value,
- and both subtrees are valid BSTs too.
An empty tree is a valid BST. Equal values anywhere in a left or right subtree break the rule.
Constraints
- The tree has between
0and10^4nodes. -2^31 <= Node.val <= 2^31 - 1
Examples
Example 1
Input: root = [8,3,10,1,6,null,14] Output: true
Every left subtree holds smaller values and every right subtree larger ones, at every node.
Example 2
Input: root = [5,4,6,null,null,3,7] Output: false
Each node is ordered correctly against its own children, but 3 sits in the right subtree of 5 and is smaller than 5.
Example 3
Input: root = [2,2,2] Output: false
Values must be strictly smaller on the left and strictly larger on the right, so equal values break the rule.
JavaScript you'll use: Recursion, the call stack and memoization Numbers, Math and integer tricks
/**
* Tree nodes are provided (you don't need to define them):
* class TreeNode { constructor(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }
*/
/**
* @param {TreeNode | null} root
* @return {boolean}
*/
function isValidBST(root) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.