0098_validate_binary_search_tree.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Validate Binary Search Tree - LeetCode 98</title>
    <link rel="stylesheet" href="styles.css">
    <script src="https://d3js.org/d3.v7.min.js"></script>
</head>
<body>
    <div class="container">
        <div class="problem-info">
            <h1><span class="problem-number">#0098</span> Validate Binary Search Tree</h1>
            <p><strong>Problem:</strong> Given a binary tree, determine if it is a valid BST (left subtree values < node < right subtree values).</p>
            <p><strong>Pattern:</strong> DFS with Valid Range - Track min/max bounds for each node</p>
            <div class="problem-meta">
                <span class="meta-tag">🌳 Tree</span>
                <span class="meta-tag">📚 Stack</span>
                <span class="meta-tag">🔍 Binary Search</span>
                <span class="meta-tag">⏱️ O(n)</span>
            </div>
            <div class="file-ref">
                📄 Python: <code>python/0098_validate_binary_search_tree/0098_validate_binary_search_tree.py</code>
            </div>

        </div>

        <div class="explanation-panel">
            <h4>🧠 How It Works (Layman's Terms)</h4>
            <p>Binary search is like finding a word in a dictionary - <strong>eliminate half</strong> each time:</p>
            <ul>
                <li><strong>Check middle:</strong> Look at the middle element</li>
                <li><strong>Compare:</strong> Is target less or greater?</li>
                <li><strong>Eliminate:</strong> Discard half that can't contain the answer</li>
                <li><strong>Repeat:</strong> Continue until found</li>
            </ul>
        </div>


        <div class="visualization-section">
            <h3>🎬 Step-by-Step Visualization</h3>

            <div class="visualization">
            <svg id="mainSvg"></svg>
        </div>

        <div class="controls">
            <button id="stepBtn">Step</button>
            <button id="autoBtn">Auto Run</button>
            <button id="resetBtn">Reset</button>
            <button id="toggleTreeBtn">Toggle: Valid Tree</button>
            <div class="speed-control">
                <label for="speed">Speed:</label>
                <input type="range" id="speed" min="100" max="2000" value="800">
            </div>
        </div>

        <div class="status" id="status">Click "Step" to validate the BST</div>

        <div class="variables">
            <div class="var-item">
                <span class="var-label">Current Node:</span>
                <span id="currentDisplay">-</span>
            </div>
            <div class="var-item">
                <span class="var-label">Valid Range:</span>
                <span id="rangeDisplay">(-∞, +∞)</span>
            </div>
            <div class="var-item">
                <span class="var-label">Is Valid:</span>
                <span id="validDisplay">-</span>
            </div>
        </div>

        </div>

        <div class="code-section">
            <h3>💻 Python Solution</h3>
            <div class="code-block">
                <pre>from typing import Optional

"""
LeetCode Validate Binary Search Tree

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

Description:
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.
"""

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def is_valid_bst(self, root: Optional[TreeNode]) -&gt; bool:
        """
        Determine if a binary tree is a valid binary search tree.
        
        Args:
            root: Root of the binary tree
            
        Returns:
            bool: True if the tree is a valid BST, False otherwise
        """
        # Helper function for recursive validation with min/max boundaries
        def validate(node, lower=float('-inf'), upper=float('inf')):
            # Empty trees are valid BSTs
            if not node:
                return True
                
            # Check if current node's value violates the BST property
            if node.val &lt;= lower or node.val &gt;= upper:
                return False
                
            # Recursively check left and right subtrees
            # Left subtree must have values less than the current node
            # Right subtree must have values greater than the current node
            return (validate(node.left, lower, node.val) and
                    validate(node.right, node.val, upper))
                    
        return validate(root)
    
    def is_valid_bst_inorder(self, root: Optional[TreeNode]) -&gt; bool:
        """
        Validate BST using inorder traversal.
        In a BST, inorder traversal should yield a sorted array.
        
        Args:
            root: Root of the binary tree
            
        Returns:
            bool: True if the tree is a valid BST, False otherwise
        """
        prev = float('-inf')
        
        # Helper function for inorder traversal
        def inorder(node):
            nonlocal prev
            
            if not node:
                return True
                
            # Check left subtree
            if not inorder(node.left):
                return False
                
            # Check current node's value against the previous value
            if node.val &lt;= prev:
                return False
                
            # Update previous value
            prev = node.val
            
            # Check right subtree
            return inorder(node.right)
            
        return inorder(root)
    
    def is_valid_bst_iterative(self, root: Optional[TreeNode]) -&gt; bool:
        """
        Validate BST using iterative inorder traversal.
        
        Args:
            root: Root of the binary tree
            
        Returns:
            bool: True if the tree is a valid BST, False otherwise
        """
        if not root:
            return True
            
        stack = []
        prev = float('-inf')
        current = root
        
        while stack or current:
            # Traverse to the leftmost node
            while current:
                stack.append(current)
                current = current.left
                
            # Check the current node
            current = stack.pop()
            
            # If current value is less than or equal to previous, it's not a BST
            if current.val &lt;= prev:
                return False
                
            # Update previous value
            prev = current.val
            
            # Move to the right subtree
            current = current.right
            
        return True

if __name__ == '__main__':
    # Example usage based on LeetCode sample
    solution = Solution()
    
    # Example 1
    # Tree:
    #   2
    #  / \
    # 1   3
    root1 = TreeNode(2, TreeNode(1), TreeNode(3))
    result1 = solution.is_valid_bst(root1)
    print(f"Example 1: {result1}")  # Expected output: True
    
    # Example 2
    # Tree:
    #     5
    #    / \
    #   1   4
    #      / \
    #     3   6
    root2 = TreeNode(5, TreeNode(1), TreeNode(4, TreeNode(3), TreeNode(6)))
    result2 = solution.is_valid_bst(root2)
    print(f"Example 2: {result2}")  # Expected output: False
    
    # Additional example
    # Tree:
    #     10
    #    /  \
    #   5    15
    #       /  \
    #      12   20
    root3 = TreeNode(10, TreeNode(5), TreeNode(15, TreeNode(12), TreeNode(20)))
    result3 = solution.is_valid_bst(root3)
    print(f"Example 3: {result3}")  # Expected output: True
    
    # Compare with other implementations
    print("\nUsing inorder traversal approach:")
    print(f"Example 1: {solution.is_valid_bst_inorder(root1)}")
    print(f"Example 2: {solution.is_valid_bst_inorder(root2)}")
    print(f"Example 3: {solution.is_valid_bst_inorder(root3)}")
    
    print("\nUsing iterative approach:")
    print(f"Example 1: {solution.is_valid_bst_iterative(root1)}")
    print(f"Example 2: {solution.is_valid_bst_iterative(root2)}")
    print(f"Example 3: {solution.is_valid_bst_iterative(root3)}")
</pre>
            </div>
        </div>
    </div>

    <script>
        // Valid BST
        const validTree = {
            val: 5,
            left: {
                val: 3,
                left: {val: 1, left: null, right: null},
                right: {val: 4, left: null, right: null}
            },
            right: {
                val: 7,
                left: {val: 6, left: null, right: null},
                right: {val: 9, left: null, right: null}
            }
        };

        // Invalid BST (4 should not be in right subtree of 5)
        const invalidTree = {
            val: 5,
            left: {
                val: 3,
                left: {val: 1, left: null, right: null},
                right: {val: 4, left: null, right: null}
            },
            right: {
                val: 7,
                left: {val: 4, left: null, right: null}, // Invalid! 4 < 5
                right: {val: 9, left: null, right: null}
            }
        };

        let useValidTree = true;
        let tree = validTree;
        let nodeStates = {}; // path -> 'processing' | 'valid' | 'invalid'
        let nodeRanges = {}; // path -> {low, high}
        let callStack = [];
        let isValid = null;
        let autoRunning = false;
        let autoTimer = null;

        const width = 750;
        const height = 420;
        const svg = d3.select("#mainSvg")
            .attr("width", width)
            .attr("height", height);

        function formatBound(val) {
            if (val === -Infinity) return "-∞";
            if (val === Infinity) return "+∞";
            return val;
        }

        function drawTree(node, x, y, level, path) {
            if (!node) return;

            const nodeRadius = 28;
            const dx = 120 / (level + 1);
            const dy = 70;

            // Edges
            if (node.left) {
                svg.append("line")
                    .attr("x1", x).attr("y1", y + nodeRadius)
                    .attr("x2", x - dx).attr("y2", y + dy - nodeRadius)
                    .attr("stroke", "#ddd").attr("stroke-width", 2);
                drawTree(node.left, x - dx, y + dy, level + 1, path + 'L');
            }
            if (node.right) {
                svg.append("line")
                    .attr("x1", x).attr("y1", y + nodeRadius)
                    .attr("x2", x + dx).attr("y2", y + dy - nodeRadius)
                    .attr("stroke", "#ddd").attr("stroke-width", 2);
                drawTree(node.right, x + dx, y + dy, level + 1, path + 'R');
            }

            // Node
            const state = nodeStates[path];
            const range = nodeRanges[path];

            let fill = "#e3f2fd", stroke = "#1976d2";
            if (state === 'processing') {
                fill = "#ffeb3b"; stroke = "#f57c00";
            } else if (state === 'valid') {
                fill = "#c8e6c9"; stroke = "#4caf50";
            } else if (state === 'invalid') {
                fill = "#ffcdd2"; stroke = "#e53935";
            }

            svg.append("circle")
                .attr("cx", x).attr("cy", y).attr("r", nodeRadius)
                .attr("fill", fill).attr("stroke", stroke).attr("stroke-width", 2);

            svg.append("text")
                .attr("x", x).attr("y", y + 5)
                .attr("text-anchor", "middle")
                .attr("font-size", "20px")
                .attr("font-weight", "bold")
                .text(node.val);

            // Range label
            if (range) {
                const rangeText = `(${formatBound(range.low)}, ${formatBound(range.high)})`;
                svg.append("text")
                    .attr("x", x).attr("y", y + nodeRadius + 15)
                    .attr("text-anchor", "middle")
                    .attr("font-size", "10px")
                    .attr("fill", "#666")
                    .text(rangeText);
            }
        }

        function draw() {
            svg.selectAll("*").remove();

            svg.append("text")
                .attr("x", width / 2).attr("y", 25)
                .attr("text-anchor", "middle")
                .attr("font-weight", "bold")
                .text(`Validating BST (${useValidTree ? 'Valid' : 'Invalid'} Tree)`);

            drawTree(tree, width / 2, 80, 0, 'root');

            // Legend
            const legend = [
                {color: "#e3f2fd", label: "Not visited"},
                {color: "#ffeb3b", label: "Processing"},
                {color: "#c8e6c9", label: "Valid"},
                {color: "#ffcdd2", label: "Invalid"}
            ];

            legend.forEach((item, i) => {
                svg.append("rect")
                    .attr("x", 10 + i * 100).attr("y", height - 30)
                    .attr("width", 15).attr("height", 15)
                    .attr("fill", item.color)
                    .attr("stroke", "#999");
                svg.append("text")
                    .attr("x", 30 + i * 100).attr("y", height - 18)
                    .attr("font-size", "11px")
                    .text(item.label);
            });

            // Result
            if (isValid !== null) {
                svg.append("rect")
                    .attr("x", width - 150).attr("y", height - 50)
                    .attr("width", 140).attr("height", 40)
                    .attr("rx", 8)
                    .attr("fill", isValid ? "#c8e6c9" : "#ffcdd2")
                    .attr("stroke", isValid ? "#4caf50" : "#e53935");

                svg.append("text")
                    .attr("x", width - 80).attr("y", height - 23)
                    .attr("text-anchor", "middle")
                    .attr("font-size", "16px")
                    .attr("font-weight", "bold")
                    .text(isValid ? "✓ Valid BST" : "✗ Invalid BST");
            }
        }

        function step() {
            if (isValid !== null) return false;

            if (isValid === false || (callStack.length === 0 && isValid === null && Object.keys(nodeStates).length > 0)) {
                if (isValid === null) isValid = true;
                document.getElementById("validDisplay").textContent = isValid ? "Yes ✓" : "No ✗";
                document.getElementById("status").textContent = 
                    isValid ? "Tree is a valid BST!" : "Tree is NOT a valid BST!";
                draw();
                return false;
            }

            if (callStack.length === 0) {
                callStack.push({node: tree, path: 'root', low: -Infinity, high: Infinity, phase: 'check'});
            }

            const {node, path, low, high, phase} = callStack.pop();

            if (!node) {
                return callStack.length > 0;
            }

            if (phase === 'check') {
                nodeStates[path] = 'processing';
                nodeRanges[path] = {low, high};
                
                document.getElementById("currentDisplay").textContent = `Node ${node.val}`;
                document.getElementById("rangeDisplay").textContent = 
                    `(${formatBound(low)}, ${formatBound(high)})`;

                // Check if node is within valid range
                if (node.val <= low || node.val >= high) {
                    nodeStates[path] = 'invalid';
                    isValid = false;
                    document.getElementById("status").textContent = 
                        `Node ${node.val} is NOT in range (${formatBound(low)}, ${formatBound(high)}) - INVALID!`;
                } else {
                    document.getElementById("status").textContent = 
                        `Node ${node.val} is in range (${formatBound(low)}, ${formatBound(high)}) ✓`;
                    
                    // Schedule children checks
                    callStack.push({node, path, low, high, phase: 'done'});
                    if (node.right) {
                        callStack.push({node: node.right, path: path + 'R', low: node.val, high, phase: 'check'});
                    }
                    if (node.left) {
                        callStack.push({node: node.left, path: path + 'L', low, high: node.val, phase: 'check'});
                    }
                }
            } else if (phase === 'done') {
                nodeStates[path] = 'valid';
                document.getElementById("status").textContent = 
                    `Node ${node.val} and its subtrees are valid!`;
            }

            draw();
            return callStack.length > 0 && isValid !== false;
        }

        function reset() {
            nodeStates = {};
            nodeRanges = {};
            callStack = [];
            isValid = null;
            autoRunning = false;
            if (autoTimer) clearInterval(autoTimer);
            
            document.getElementById("currentDisplay").textContent = "-";
            document.getElementById("rangeDisplay").textContent = "(-∞, +∞)";
            document.getElementById("validDisplay").textContent = "-";
            document.getElementById("status").textContent = 'Click "Step" to validate the BST';
            document.getElementById("autoBtn").textContent = "Auto Run";
            
            draw();
        }

        function toggleTree() {
            useValidTree = !useValidTree;
            tree = useValidTree ? validTree : invalidTree;
            document.getElementById("toggleTreeBtn").textContent = 
                `Toggle: ${useValidTree ? 'Valid' : 'Invalid'} Tree`;
            reset();
        }

        function autoRun() {
            if (autoRunning) {
                autoRunning = false;
                clearInterval(autoTimer);
                document.getElementById("autoBtn").textContent = "Auto Run";
            } else {
                autoRunning = true;
                document.getElementById("autoBtn").textContent = "Pause";
                const speed = 2100 - document.getElementById("speed").value;
                autoTimer = setInterval(() => {
                    if (!step()) {
                        autoRunning = false;
                        clearInterval(autoTimer);
                        document.getElementById("autoBtn").textContent = "Auto Run";
                    }
                }, speed);
            }
        }

        document.getElementById("stepBtn").addEventListener("click", step);
        document.getElementById("autoBtn").addEventListener("click", autoRun);
        document.getElementById("resetBtn").addEventListener("click", reset);
        document.getElementById("toggleTreeBtn").addEventListener("click", toggleTree);

        draw();
    </script>
</body>
</html>