LietCode
Validate Binary Search Tree

Validate Binary Search Tree

Abhi's photo
Abhi
·

3 min read

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.

1) Explain the problem

We need to determine if a given binary tree is a valid binary search tree (BST). A BST is defined as a tree in which for every node, all nodes in its left subtree have values less than the node's value, and all nodes in its right subtree have values greater than the node's value.

2) Short easy to remember solution/approach

Use a recursive approach to validate the BST. Keep track of the valid range (minimum and maximum values) for each node. For each node, check if its value lies within the valid range and recursively validate its left and right subtrees.

3) Solution in Javascript with code commenting

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

function isValidBST(root) {
    function validate(node, min, max) {
        if (!node) return true;

        // Check if the current node's value is within the valid range
        if (node.val <= min || node.val >= max) return false;

        // Recursively validate the left and right subtrees
        return validate(node.left, min, node.val) && validate(node.right, node.val, max);
    }

    // Start the validation with the full range of valid values
    return validate(root, -Infinity, Infinity);
}

// Example usage:
let root = new TreeNode(2);
root.left = new TreeNode(1);
root.right = new TreeNode(3);

console.log(isValidBST(root)); // Output: true

root = new TreeNode(5);
root.left = new TreeNode(1);
root.right = new TreeNode(4);
root.right.left = new TreeNode(3);
root.right.right = new TreeNode(6);

console.log(isValidBST(root)); // Output: false

4) Explanation of the solution in an easy-to-understand way. Explain it like a 10-year-old.

Imagine you have a line of boxes, and each box has a number on it. You want to check if the numbers are arranged correctly. For each box, the numbers in the boxes on its left should be smaller, and the numbers in the boxes on its right should be larger. You keep checking each box and its neighbors to make sure the arrangement rules are followed.

5) Code explanation in pointers

  • Define a TreeNode class to represent each node in the tree.

  • Create an isValidBST function that:

    • Defines a helper function validate to:

      • Return true if the node is null (base case).

      • Check if the node's value is within the valid range (min < node.val < max).

      • Recursively validate the left subtree with an updated maximum value (current node's value).

      • Recursively validate the right subtree with an updated minimum value (current node's value).

      • Return true only if both subtrees are valid.

    • Start the validation with the full range of valid values (-Infinity to Infinity).

  • Use the isValidBST function to check if the tree is a valid BST.

6) Complexities

  • Time Complexity: (O(n)) - Each node is visited once.

  • Space Complexity: (O(h)) - Where (h) is the height of the tree. This is due to the recursion stack.

TreeTrees