Validate Binary Search Tree - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'current', CURRENT_COLOR = 'blue';
const INVALID = 'invalid', INVALID_COLOR = 'red';
const VALID_VALUE = 'valid_value', VALID_VALUE_COLOR = 'lightgreen';
const VALID = 'valid', VALID_COLOR = 'green';
const LOWER_COLOR = 'gold', UPPER_COLOR = 'orange';

function visMainFunction(treeInput) {
    initClassProperties(); 
    explanationAndColorSchemaNotifications();

    const root = convertInputToTree(treeInput);
    const tree = new VisBinaryTree(root, { dataPropName: 'val' });

    const isValid = validate(root, -Infinity, Infinity);
    
    function validate(node, lower, upper) {
        if (!node) {
            notification(`🌿 Reached <b>null</b> — this path is <b>valid</b> since there’s nothing left to violate the rules along it. Returning <b>true</b>.`);
            return true;
        }

        const vm = tree.makeVisManagerForNode(node);
        startPartialBatch();
        setCurrentNode(vm);
        notification(`
            🔍 Checking whether the ${makeColoredSpan('current node', CURRENT_COLOR)}’s value (<b>${node.val}</b>)  lies within bounds. It must be <b>greater than</b> 
            the ${makeColoredSpan('lower', LOWER_COLOR)} (<b>${lower}</b>) and <b>less than</b> the ${makeColoredSpan('upper', 'orange')} (<b>${upper}</b>).
        `);

        if (node.val <= lower || node.val >= upper) {
            handleInvalidValue(node, vm, lower, upper);
            endBatch();
            return false;
        }

        handleValidValue(node, vm, lower, upper);
        endBatch();

        // note that handleValidLeftSubtree and handleValidNode calls are not part of the original algorithm they are included for sake of visualization
        return validate(node.left, lower, node.val) && handleValidLeftSubtree(node, vm, upper) &&
               validate(node.right, node.val, upper) && handleValidNode(vm);
    }

    if (isValid) {
        notification(`✅ The tree is a <b>valid Binary Search Tree</b>.`);
    } else {
        notification(`❌ The tree is <b>not</b> a valid Binary Search Tree.`);
    }

    return isValid;
}

// --- Visual helpers ---
let currentNodeVM = null;

function setCurrentNode(vm) {
    startBatch();
    if (currentNodeVM) currentNodeVM.removeClass(CURRENT); 
    vm.addClass(CURRENT);
    currentNodeVM = vm;
    endBatch();
}

function handleInvalidValue(node, vm, lower, upper) {
    startPartialBatch();
    vm.addClass(INVALID);
    notification(`
        ❌ <b>Violation detected!</b> The ${makeColoredSpan('current node', CURRENT_COLOR)}’s value <b>${node.val}</b> is <b>outside its valid range</b> — 
        it was expected to be <b>greater than</b> ${makeColoredSpan('lower', LOWER_COLOR)} (<b>${lower}</b>) and <b>less than</b>  ${makeColoredSpan('upper', UPPER_COLOR)} (<b>${upper}</b>).
    `);
    endBatch();
}

function handleValidValue(node, vm, lower, upper) {
    startPartialBatch();
    vm.addClass(VALID_VALUE);
    notification(`
        ✅ <b>Valid value!</b> The ${makeColoredSpan('current node', CURRENT_COLOR)}’s value <b>${node.val}</b> is <b>within its valid range</b> — 
        greater than ${makeColoredSpan('lower', LOWER_COLOR)} (<b>${lower}</b>) and less than ${makeColoredSpan('upper', UPPER_COLOR)} (<b>${upper}</b>).  
        <br>🔽 Proceeding to validate the <b>left subtree</b>, where the new upper bound becomes the current node’s value, <b>${node.val}</b>.
    `);
    endBatch();
}

function handleValidLeftSubtree(node, vm, upper) {
    startPartialBatch();
    setCurrentNode(vm);
    notification(`
        ✅ The <b>left subtree</b> of the ${makeColoredSpan('current node', CURRENT_COLOR)} is <b>valid</b>.  
        🔽 Proceeding to validate the <b>right subtree</b>, where the new <b>lower bound</b> becomes the current node’s value, <b>${node.val}</b>,  
        while the <b>upper bound</b> remains <b>${upper}</b>.
    `);
    endBatch();
    return true;
}

function handleValidNode(vm) {
    startPartialBatch();
    setCurrentNode(vm);
    notification(`
        ✅ The entire <b>subtree</b> rooted at the ${makeColoredSpan('current node', CURRENT_COLOR)} is <b>valid</b> — it satisfies both the <b>BST property</b> within itself  
        and all <b>value constraints inherited from its ancestors (if any)</b>.
    `);
    vm.removeClass(VALID_VALUE).addClass(VALID);
    endBatch();
    return true;
}

function initClassProperties() {
    setClassProperties(CURRENT, { borderColor: CURRENT_COLOR });
    setClassProperties(VALID_VALUE, { backgroundColor: VALID_VALUE_COLOR });
    setClassProperties(VALID, { backgroundColor: VALID_COLOR });
    setClassProperties(INVALID, { backgroundColor: INVALID_COLOR });
}

function convertInputToTree(arr) {
    if (!arr.length || arr[0] === null) return null;
    const nodes = arr.map(val => (val === null ? null : new TreeNode(val)));
    for (let i = 0; i < arr.length; i++) {
        if (nodes[i]) {
            nodes[i].left = nodes[2 * i + 1] || null;
            nodes[i].right = nodes[2 * i + 2] || null;
        }
    }
    return nodes[0];
} 

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

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Visual Cues (Color Schema)</b>
        <ul>
            <li>${makeColoredSpan('Current node', CURRENT_COLOR)} — <b>${CURRENT_COLOR} border</b> while being visited during validation.</li>
            <li>${makeColoredSpan('Valid value', VALID_VALUE_COLOR)} — <b>${VALID_VALUE_COLOR} background</b> when the node’s value is within its valid range.</li>
            <li>${makeColoredSpan('Fully validated node', VALID_COLOR)} — <b>${VALID_COLOR} background</b> once the subtree rooted at the node is validated.</li>
            <li>${makeColoredSpan('Invalid node', INVALID_COLOR)} — <b>${INVALID_COLOR} background</b> when a value violates its allowed bounds.</li>
        </ul>
    `);
}

Approach

We validate the binary search tree using a recursive helper validate(node, lower, upper) that enforces a range invariant for every node, where node.val must be greater than lower and less than upper. These bounds are inherited from ancestors and become tighter as we go down the tree, ensuring that each subtree also maintains the BST property internally.

🔧 Invariant & Recurrence

At each call validate(node, lower, upper):

Base case: if node == null, the path is valid since there’s nothing left to violate the rules along this path.
Bounds check: return false if node.val ≤ lower or node.val ≥ upper — the current node breaks the allowed range.
Recurse left: call validate(node.left, lower, node.val) to ensure all values in the left subtree are greater than the inherited lower bound and less than the current node’s value.
Recurse right: call validate(node.right, node.val, upper) to ensure all values in the right subtree are greater than the current node’s value and less than the inherited upper bound.
Return the result of the left recursion and the result of the right recursion. If both return true, it confirms that every node in both subtrees satisfies the inherited bounds from ancestors and maintains the BST property internally. Since the current node’s value was already validated before these calls, it means the entire subtree rooted here also satisfies the inherited bounds from ancestors and maintains the BST property internally. Otherwise, a violation was found in one of the recursive branches.

💡 Why the Bounds Are Sufficient

When we make recursive calls to the left and right subtrees, we’ve already confirmed that the current node’s value lies strictly within (lower, upper). For the left subtree, every value must be less than the current node’s value, so we tighten the upper bound to node.val. There’s no need to compare node.val with the inherited upper bound again — we already ensured that node.val < upper. Similarly, for the right subtree, every value must be greater than the current node’s value, so we tighten the lower bound to node.val. Again, there’s no need to compare node.val with the inherited lower bound — we already confirmed that node.val > lower.

⏱️ Complexity

Time: O(n) — each node is visited once.
Space: O(h) auxiliary — recursion stack height, where h is the tree height (worst case O(n) for a skewed tree; O(log n) for a balanced tree).

🧭 Result Semantics

If a call to validate(node, lower, upper) returns true, then the entire subtree rooted at node satisfies both the BST property internally and all value constraints inherited from its ancestors.

Time Complexity

O(n), where n is the number of nodes — each node is visited once.

Space Complexity

Auxiliary space usage is O(h) — the recursion stack height, where h is the tree height (worst case: O(n) for a skewed tree; average case: O(log n) for a balanced tree).

Input-1

Validate Binary Search Tree - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

🔧 Invariant & Recurrence

💡 Why the Bounds Are Sufficient

⏱️ Complexity

🧭 Result Semantics

Time Complexity

Space Complexity