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.
Example 1:
Input: root = [2,1,3]
Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
Pseudocode
- use properties of BST to validate that left and right child are following rules
Solution
var isValidBST = function (root) {
function walk(root, minVal, maxVal) {
// base condition
if (!root) {
return true;
}
// pre
if (root.val <= minVal || root.val >= maxVal) {
return false;
}
// recurse
// left node can't be larger than parent node
// right node must be larger than parent node
return (
walk(root.left, minVal, root.val) && walk(root.right, root.val, maxVal)
);
// post
}
return walk(root, -Infinity, Infinity);
};
