Validate Binary Search Tree medium

Problem Statement

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.

Steps

1. Recursive Approach: We'll use a recursive helper function to traverse the tree.
2. In-order Traversal Logic: A BST, when traversed in-order (left, root, right), will produce a sorted sequence. We'll leverage this property. We'll maintain a variable to track the previous node's value during in-order traversal.
3. Base Case: If the current node is null, we're done with that branch.
4. Recursive Steps:
   • Recursively check the left subtree.
   • If the left subtree is invalid, return false.
   • Check if the current node's value is greater than the previous node's value (maintaining sorted order). If not, return false.
   • Update the previous node's value.
   • Recursively check the right subtree.
   • If the right subtree is invalid, return false.
5. Return true: If all checks pass, the tree is a valid BST.

Explanation

The key insight is that an in-order traversal of a BST yields a sorted sequence. Our recursive helper function simulates this traversal, keeping track of the previously visited node. If at any point the current node's value is not greater than the previous node's value, the sorted property is violated, and the tree is not a BST.

Code

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}

function isValidBST(root: TreeNode | null): boolean {
    let prev: number | null = null;

    function isValidBSTHelper(node: TreeNode | null): boolean {
        if (node === null) {
            return true;
        }

        if (!isValidBSTHelper(node.left)) {
            return false;
        }

        if (prev !== null && node.val <= prev) {
            return false;
        }

        prev = node.val;

        if (!isValidBSTHelper(node.right)) {
            return false;
        }

        return true;
    }

    return isValidBSTHelper(root);
}


// Example usage:
const root1 = new TreeNode(2, new TreeNode(1), new TreeNode(3));
console.log(isValidBST(root1)); // true

const root2 = new TreeNode(5, new TreeNode(1), new TreeNode(4, new TreeNode(3), new TreeNode(6)));
console.log(isValidBST(root2)); // false

const root3 = new TreeNode(1, null, new TreeNode(2, null, new TreeNode(3)));
console.log(isValidBST(root3)); //false

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once during the in-order traversal.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H could be N, but in a balanced tree, H would be log₂N.