0098. Validate Binary Search Tree

leetcode

Problem:

We are given the root of a binary tree and our objective is to determine if it is a valid binary search tree (BST). A valid BST has the property that for every node with a value `N`, all nodes in its left subtree have values less than `N`, and all nodes in its right subtree have values greater than `N`.

To accomplish this, we can use an efficient approach leveraging DFS (Depth First Search) to traverse the tree while maintaining the constraints of the BST.

Solution Description:

To implement the validation of a BST, we need to use a recursive function that traverses the tree while keeping track of the acceptable value range for each node. Specifically, we can use the following approach:

Start with the root node and an initially unbounded range (`-Infinity` to `Infinity`).
For each node, check if its value lies within the current valid range.
Recursively check the left subtree with an updated upper bound (the current node's value).
Recursively check the right subtree with an updated lower bound (the current node's value).

Both subtrees must be valid for the entire tree to be considered a valid BST.

The time complexity of this solution is O(N), where `N` is the number of nodes, as we visit each node once. The space complexity is O(H), where `H` is the height of the tree, due to the recursion stack.

Example:

Consider the following binary tree:

``` 2 / \ 1 3 ```

The algorithm will:

Check the root node with value `2` (range `-Infinity` to `Infinity`).
Recursively validate the left child `1` (range `-Infinity` to `2`).
Recursively validate the right child `3` (range `2` to `Infinity`).

All nodes satisfy the BST properties, so the tree is a valid BST.

Setup:

/**
 * Function to validate if a binary tree is a valid Binary Search Tree (BST).
 *
 * @param {TreeNode} root - The root node of the binary tree
 * @returns {boolean} - Returns true if the tree is a valid BST, else false
 */
function isValidBST(root) {
    // Helper definitions as instructed
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger !== 'undefined' ? () => {} : console.table;

    if (!root) return false;

    function dfs(node, low, high) {
        if (!node) return true;

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

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

    return dfs(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);
}

// TreeNode structure for clarity
class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// Test cases
const testCases = [
    { tree: new TreeNode(2, new TreeNode(1), new TreeNode(3)), expected: true },
    { tree: new TreeNode(5, new TreeNode(1), new TreeNode(4, new TreeNode(3), new TreeNode(6))), expected: false },
    // Add more test cases as needed
];

testCases.forEach((test, index) => {
    const result = isValidBST(test.tree);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});