98. Validate Binary Search Tree

Problem

https://leetcode.com/problems/validate-binary-search-tree/

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.

Example 1:

    2
   / \
  1   3

Binary tree [2,1,3], return true.

Example 2:

    1
   / \
  2   3

Binary tree [1,2,3], return false.

Solution

Solution1

If you do an in-order traversal on a BST, the result has to be sorted.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    if (!root) { return true }

    let pre = -Infinity

    function validHelper(node) {
        if (!node) { return true }

        if (!validHelper(node.left)) { return false }

        if (node.val <= pre) { return false }

        pre = node.val

        if (!validHelper(node.right)) { return false }

        return true
    }

    return validHelper(root)
};

Solution2

Check every node with a given range, which could be calculated based on the parent node.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    if (!root) { return true }

    return validHelper(root.right, root.val, +Infinity) &&
        validHelper(root.left, -Infinity, root.val)

    function validHelper(node, low, high) {
        if (!node) { return true }

        if (node.val <= low || node.val >= high) { return false }

        return validHelper(node.right, node.val, high) &&
            validHelper(node.left, low, node.val)
    }
};