6c:T6c1,def is_valid_bst(root): """ Validate BST using range-based recursion. Time Complexity: O(n) - visit each node exactly once Space Complexity: O(h) - recursion stack, where h is tree height O(log n) for balanced, O(n) for skewed """ def validate(node, min_val, max_val): # Base case: empty tree is valid if node is None: return True # Check if current node violates the range constraint if node.val <= min_val or node.val >= max_val: return False # Recursively validate subtrees with updated ranges # Left subtree: all values must be less than current node # Right subtree: all values must be greater than current node return (validate(node.left, min_val, node.val) and validate(node.right, node.val, max_val)) # Start with infinite range return validate(root, float('-inf'), float('inf')) # For trees with integer values, we can use sentinel values def is_valid_bst_with_sentinels(root): """ Alternative using None as sentinel for unbounded ranges. Useful when dealing with extreme integer values. """ def validate(node, min_val, max_val): if node is None: return True # Check lower bound (if it exists) if min_val is not None and node.val <= min_val: return False # Check upper bound (if it exists) if max_val is not None and node.val >= max_val: return False return (validate(node.left, min_val, node.val) and validate(node.right, node.val, max_val)) return validate(root, None, None)6d:T799,function isValidBST(root: TreeNode | null): boolean { /** * Validate BST using range-based recursion. * * Time Complexity: O(n) - visit each node exactly once * Space Complexity: O(h) - recursion stack, where h is tree height * O(log n) for balanced, O(n) for skewed */ function validate( node: TreeNode | null, minVal: number, maxVal: number ): boolean { // Base case: empty tree is valid if (node === null) { return true; } // Check if current node violates the range constraint if (node.val <= minVal || node.val >= maxVal) { return false; } // Recursively validate subtrees with updated ranges // Left subtree: all values must be less than current node // Right subtree: all values must be greater than current node return ( validate(node.left, minVal, node.val) && validate(node.right, node.val, maxVal) ); } // Start with infinite range return validate(root, -Infinity, Infinity); } // Alternative using null sentinels for unbounded ranges function isValidBSTWithSentinels(root: TreeNode | null): boolean { function validate( node: TreeNode | null, minVal: number | null, maxVal: number | null ): boolean { if (node === null) { return true; } // Check lower bound (if it exists) if (minVal !== null && node.val <= minVal) { return false; } // Check upper bound (if it exists) if (maxVal !== null && node.val >= maxVal) { return false; } return ( validate(node.left, minVal, node.val) && validate(node.right, node.val, maxVal) ); } return validate(root, null, null); }6e:T61e,public boolean isValidBST(TreeNode root) { /** * Validate BST using range-based recursion. * * Time Complexity: O(n) - visit each node exactly once * Space Complexity: O(h) - recursion stack, where h is tree height * O(log n) for balanced, O(n) for skewed */ return validate(root, null, null); } private boolean validate(TreeNode node, Integer minVal, Integer maxVal) { // Base case: empty tree is valid if (node == null) { return true; } // Check if current node violates the range constraint if (minVal != null && node.val <= minVal) { return false; } if (maxVal != null && node.val >= maxVal) { return false; } // Recursively validate subtrees with updated ranges // Left subtree: all values must be less than current node // Right subtree: all values must be greater than current node return validate(node.left, minVal, node.val) && validate(node.right, node.val, maxVal); } // Alternative with explicit Long bounds to handle Integer edge cases public boolean isValidBSTWithLongBounds(TreeNode root) { return validateWithLong(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean validateWithLong(TreeNode node, long minVal, long maxVal) { if (node == null) { return true; } if (node.val <= minVal || node.val >= maxVal) { return false; } return validateWithLong(node.left, minVal, node.val) && validateWithLong(node.right, node.val, maxVal); }6f:T663,def is_valid_bst_inorder(root): """ Validate BST using inorder traversal property. Key insight: Inorder traversal of a valid BST produces a strictly increasing sequence. Time Complexity: O(n) - visit each node exactly once Space Complexity: O(h) - recursion stack """ prev = [float('-inf')] # Use list for Python closure semantics def inorder(node): if node is None: return True # Visit left subtree if not inorder(node.left): return False # Check current node against previous value if node.val <= prev[0]: return False # Update previous value prev[0] = node.val # Visit right subtree return inorder(node.right) return inorder(root) # Alternative: Iterative inorder with explicit stack def is_valid_bst_iterative(root): """ Iterative inorder traversal validation. Avoids recursion stack overflow for very deep trees. Uses explicit stack simulation of inorder traversal. """ stack = [] prev = float('-inf') current = root while stack or current: # Go as far left as possible while current: stack.append(current) current = current.left # Process current node current = stack.pop() # Validate against previous value if current.val <= prev: return False prev = current.val # Move to right subtree current = current.right return True70:T74b,function isValidBSTInorder(root: TreeNode | null): boolean { /** * Validate BST using inorder traversal property. * * Key insight: Inorder traversal of a valid BST produces * a strictly increasing sequence. * * Time Complexity: O(n) - visit each node exactly once * Space Complexity: O(h) - recursion stack */ let prev = -Infinity; function inorder(node: TreeNode | null): boolean { if (node === null) { return true; } // Visit left subtree if (!inorder(node.left)) { return false; } // Check current node against previous value if (node.val <= prev) { return false; } // Update previous value prev = node.val; // Visit right subtree return inorder(node.right); } return inorder(root); } // Alternative: Iterative inorder with explicit stack function isValidBSTIterative(root: TreeNode | null): boolean { /** * Iterative inorder traversal validation. * * Avoids recursion stack overflow for very deep trees. * Uses explicit stack simulation of inorder traversal. */ const stack: TreeNode[] = []; let prev = -Infinity; let current = root; while (stack.length > 0 || current !== null) { // Go as far left as possible while (current !== null) { stack.push(current); current = current.left; } // Process current node current = stack.pop()!; // Validate against previous value if (current.val <= prev) { return false; } prev = current.val; // Move to right subtree current = current.right; } return true; }71:T676,public boolean isValidBSTInorder(TreeNode root) { /** * Validate BST using inorder traversal property. * * Key insight: Inorder traversal of a valid BST produces * a strictly increasing sequence. * * Time Complexity: O(n) - visit each node exactly once * Space Complexity: O(h) - recursion stack */ long[] prev = {Long.MIN_VALUE}; // Use array for closure semantics return inorder(root, prev); } private boolean inorder(TreeNode node, long[] prev) { if (node == null) { return true; } // Visit left subtree if (!inorder(node.left, prev)) { return false; } // Check current node against previous value if (node.val <= prev[0]) { return false; } // Update previous value prev[0] = node.val; // Visit right subtree return inorder(node.right, prev); } // Alternative: Iterative inorder with explicit stack public boolean isValidBSTIterative(TreeNode root) { Deque stack = new ArrayDeque<>(); long prev = Long.MIN_VALUE; TreeNode current = root; while (!stack.isEmpty() || current != null) { // Go as far left as possible while (current != null) { stack.push(current); current = current.left; } // Process current node current = stack.pop(); // Validate against previous value if (current.val <= prev) { return false; } prev = current.val; // Move to right subtree current = current.right; } return true; }72:T841,def is_valid_bst_production(root): """ Production-ready BST validation with comprehensive edge case handling. Features: - Handles None/empty trees correctly - Uses None bounds to avoid integer overflow issues - Supports customizable duplicate handling - Includes iterative option for deep trees """ def validate(node, min_val, max_val): if node is None: return True # Check bounds using None for unbounded (no overflow risk) if min_val is not None and node.val <= min_val: return False if max_val is not None and node.val >= max_val: return False return (validate(node.left, min_val, node.val) and validate(node.right, node.val, max_val)) return validate(root, None, None) def is_valid_bst_with_duplicates(root, duplicates_allowed_left=True): """ BST validation that handles duplicate values. Args: root: Root of the tree duplicates_allowed_left: If True, duplicates go to left subtree If False, duplicates go to right subtree """ def validate(node, min_val, max_val): if node is None: return True if min_val is not None: # Duplicates on left: left <= root, so right > root if duplicates_allowed_left and node.val <= min_val: return False # Duplicates on right: left < root, so right >= root if not duplicates_allowed_left and node.val < min_val: return False if max_val is not None: # Duplicates on left: left <= root if duplicates_allowed_left and node.val > max_val: return False # Duplicates on right: left < root (strict) if not duplicates_allowed_left and node.val >= max_val: return False return (validate(node.left, min_val, node.val) and validate(node.right, node.val, max_val)) return validate(root, None, None)65:{"json":{"id":"seed_e6edf138af6947922b5b192fc723aa78","slug":"common-bst-patterns","category":"Data Structures & Algorithms","topic":"Common BST Patterns & Problem Types","title":"Common BST Patterns & Problem Types","description":"Master the essential problem patterns that appear repeatedly when working with Binary Search Trees. Learn to validate BSTs, find floor and ceiling values, execute range queries, convert sorted arrays to balanced BSTs, and rebalance existing trees.","difficulty":"INTERMEDIATE","estimatedMinutes":90,"pages":[{"id":"seed_54b2058790999608fdd4213bdfe048b1","title":"Validating a BST","order":0,"content":[{"id":"opening-hook","title":"The Fundamental Verification Problem","content":[{"data":{"content":"Given a binary tree, how do you determine whether it is a valid Binary Search Tree? This seemingly simple question reveals one of the most instructive patterns in tree algorithms—and exposes a subtle trap that catches even experienced engineers.\n\nBST validation is not merely an academic exercise. It appears in production code when:\n- Deserializing tree data from external sources\n- Verifying data integrity after tree mutations\n- Debugging BST implementations\n- Writing comprehensive unit tests for tree-based data structures\n\nThis problem forces us to reason precisely about what the BST property actually means, and why our first intuition is often subtly wrong."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand the precise definition of a valid BST, recognize why naive approaches fail, master multiple validation strategies (recursive range-tracking and inorder traversal), and develop the analytical skills to choose the right approach for different contexts.","variant":"info"},"type":"callout"}]},{"id":"bst-property-recall","title":"Recalling the BST Property","content":[{"data":{"content":"Before we can validate a BST, we must state precisely what we're validating. The **Binary Search Tree property** is deceptively simple:\n\n> For every node N in the tree:\n> - All values in N's **left subtree** are **less than** N's value\n> - All values in N's **right subtree** are **greater than** N's value\n\nPay careful attention to the words **all values** and **subtree**. This is not saying 'the left child is less than the root'—it's saying *every descendant* on the left must be less than the root. This distinction is the crux of BST validation."},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Critical Distinction","content":"The BST property is a **global constraint** on subtrees, not just a local constraint between adjacent nodes. Checking only parent-child relationships is insufficient and leads to incorrect validation.","variant":"warning"},"type":"callout"},{"data":{"content":"**Handling Equal Values:**\n\nDifferent implementations handle equal values differently:\n- **Strict BST**: No duplicates allowed\n- **Left-leaning duplicates**: Equal values go to the left subtree (left ≤ root < right)\n- **Right-leaning duplicates**: Equal values go to the right subtree (left < root ≤ right)\n\nFor this discussion, we'll use strict inequality (no duplicates), but the patterns generalize. When solving interview problems, always clarify how duplicates should be handled."},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"naive-approach-fails","title":"The Naive Approach and Why It Fails","content":[{"data":{"content":"The first approach most developers consider is straightforward: for each node, check if the left child is less than the node and the right child is greater. If this holds for every node, the tree is a BST.\n\nThis approach is **incorrect**."},"type":"text"},{"data":{"fileName":"naive_validation.py","languages":[{"code":"# INCORRECT APPROACH - DO NOT USE\ndef is_valid_bst_naive(node):\n \"\"\"\n This approach checks only immediate children.\n It will incorrectly return True for trees that violate\n the BST property through deeper descendants.\n \"\"\"\n if node is None:\n return True\n \n # Check immediate left child\n if node.left and node.left.val >= node.val:\n return False\n \n # Check immediate right child\n if node.right and node.right.val <= node.val:\n return False\n \n # Recursively check subtrees\n return is_valid_bst_naive(node.left) and is_valid_bst_naive(node.right)","label":"Python","value":"python"},{"code":"// INCORRECT APPROACH - DO NOT USE\nfunction isValidBSTNaive(node: TreeNode | null): boolean {\n /**\n * This approach checks only immediate children.\n * It will incorrectly return True for trees that violate\n * the BST property through deeper descendants.\n */\n if (node === null) {\n return true;\n }\n \n // Check immediate left child\n if (node.left && node.left.val >= node.val) {\n return false;\n }\n \n // Check immediate right child\n if (node.right && node.right.val <= node.val) {\n return false;\n }\n \n // Recursively check subtrees\n return isValidBSTNaive(node.left) && isValidBSTNaive(node.right);\n}","label":"TypeScript","value":"typescript"},{"code":"// INCORRECT APPROACH - DO NOT USE\npublic boolean isValidBSTNaive(TreeNode node) {\n /**\n * This approach checks only immediate children.\n * It will incorrectly return True for trees that violate\n * the BST property through deeper descendants.\n */\n if (node == null) {\n return true;\n }\n \n // Check immediate left child\n if (node.left != null && node.left.val >= node.val) {\n return false;\n }\n \n // Check immediate right child\n if (node.right != null && node.right.val <= node.val) {\n return false;\n }\n \n // Recursively check subtrees\n return isValidBSTNaive(node.left) && isValidBSTNaive(node.right);\n}","label":"Java","value":"java"}]},"type":"code"},{"data":{"content":"**Why does this fail?**\n\nConsider this counterexample:"},"type":"text"},{"data":{"height":"300px","mermaidSyntax":"graph TD\n A((10)) --> B((5))\n A --> C((15))\n C --> D((6))\n C --> E((20))\n \n style D fill:#ff6b6b,color:#fff"},"type":"mermaid-excalidraw"},{"data":{"content":"In this tree:\n- 10 is the root\n- 5 is the left child (5 < 10) ✓\n- 15 is the right child (15 > 10) ✓\n- 6 is the left child of 15 (6 < 15) ✓\n- 20 is the right child of 15 (20 > 15) ✓\n\nThe naive algorithm returns `true` because every local parent-child relationship satisfies the BST constraint.\n\n**But this tree is NOT a valid BST!**\n\nThe node with value **6** is in the **right subtree** of the root 10, but 6 < 10. The BST property requires that *all* values in the right subtree be greater than the root. The value 6 violates this—it's less than the root 10, yet it appears in the right subtree."},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Lesson","content":"Local correctness does not imply global correctness. A node must satisfy constraints imposed not just by its parent, but by all its ancestors. The node 6 must be greater than both its parent 15 AND the root 10—but the naive approach only checks the parent.","variant":"error"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"range-based-approach","title":"The Range-Based Recursive Approach","content":[{"data":{"content":"The correct approach tracks the **valid range** for each node as we recurse. Every node must fall within a range determined by its ancestors:\n\n- When we go **left**, the current node becomes the new **upper bound**\n- When we go **right**, the current node becomes the new **lower bound**\n\nThis elegantly enforces the global BST property by propagating constraints downward through the tree."},"type":"text"},{"data":{"content":"**The Algorithm:**\n\n1. Start at the root with range (-∞, +∞)\n2. For each node, verify its value falls within the valid range\n3. Recurse left with updated range (min, node.val)\n4. Recurse right with updated range (node.val, max)\n5. A null node is trivially valid (base case)"},"type":"text"},{"data":{"fileName":"range_validation.py","languages":[{"code":"$6c","label":"Python","value":"python"},{"code":"$6d","label":"TypeScript","value":"typescript"},{"code":"$6e","label":"Java","value":"java"}]},"type":"code"},{"data":{"content":"**Tracing Through the Counterexample:**\n\nLet's trace the range-based algorithm on our earlier counterexample:"},"type":"text"},{"data":{"rows":[["10 (root)","(-∞, +∞)","10 in (-∞, +∞)?","✓ Valid, recurse"],["5 (left of 10)","(-∞, 10)","5 in (-∞, 10)?","✓ Valid, recurse"],["15 (right of 10)","(10, +∞)","15 in (10, +∞)?","✓ Valid, recurse"],["6 (left of 15)","(10, 15)","6 in (10, 15)?","✗ INVALID - 6 ≤ 10"]],"caption":"Range Tracking During Validation","headers":["Node","Valid Range","Check","Result"]},"type":"table"},{"data":{"content":"The key insight: when we descend into the left subtree of 15, we inherit the constraint that all values must still be greater than 10 (from the ancestor root). The range becomes (10, 15), and 6 fails this check.\n\nThis is how range propagation captures the **global** BST constraint, not just local relationships."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Understanding the Range Logic","content":"Think of each node as inheriting a \"passport\" that must satisfy all border controls from root to leaf. Going left adds an upper bound; going right adds a lower bound. A valid BST node must clear ALL checkpoints.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"inorder-approach","title":"The Inorder Traversal Approach","content":[{"data":{"content":"A fundamentally different approach exploits a beautiful property of BSTs:\n\n> **An inorder traversal of a valid BST produces a strictly increasing sequence.**\n\nThis means we can validate a BST by performing an inorder traversal and verifying that each value is greater than the previous. If any value is less than or equal to its predecessor in the inorder sequence, the tree is not a valid BST."},"type":"text"},{"data":{"content":"**Why does inorder traversal yield sorted output?**\n\nInorder traversal visits nodes in the order: left subtree → root → right subtree. Due to the BST property:\n- Everything in the left subtree is less than the root\n- Everything in the right subtree is greater than the root\n\nBy the time we visit the root, we've already visited all smaller values (left subtree). After the root, we visit all larger values (right subtree). This recursive property guarantees sorted output."},"type":"text"},{"data":{"fileName":"inorder_validation.py","languages":[{"code":"$6f","label":"Python","value":"python"},{"code":"$70","label":"TypeScript","value":"typescript"},{"code":"$71","label":"Java","value":"java"}]},"type":"code"},{"data":{"icon":"Info","title":"Closure Semantics in Python","content":"In the recursive Python solution, we use `prev = [float('-inf')]` instead of a simple variable. This is because Python's closure semantics require mutable objects (like lists) to modify outer variables from nested functions. Using `prev[0]` allows us to update the value across recursive calls.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"comparing-approaches","title":"Comparing the Two Approaches","content":[{"data":{"content":"Both the range-based and inorder approaches solve BST validation correctly with identical asymptotic complexity. However, they differ in important ways:"},"type":"text"},{"data":{"rows":[["Time Complexity","O(n)","O(n)"],["Space Complexity","O(h) recursion stack","O(h) recursion stack"],["Early Termination","Can terminate immediately on invalid node","Must complete traversal path to detect violations"],["Conceptual Basis","Directly encodes BST constraint","Exploits sorted output property"],["State Tracking","Two values (min, max) per call","One value (prev) shared across calls"],["Edge Cases","Requires careful handling of int overflow","Same overflow concerns"],["Generalization","Easily adapts to variants (≤ vs <)","Requires adjustment for duplicates"]],"caption":"Range-Based vs. Inorder Validation","headers":["Aspect","Range-Based","Inorder Traversal"]},"type":"table"},{"data":{"content":"**When to Choose Each Approach:**\n\n**Range-based** is often preferred when:\n- You want the code to directly express the BST invariant\n- You're teaching or explaining BST concepts\n- You need to handle BST variants with different inequality rules\n\n**Inorder-based** is often preferred when:\n- You already have an inorder traversal utility\n- You want to verify sorting property explicitly\n- You're combining validation with other inorder-based operations"},"type":"text"},{"data":{"left":[{"data":{"items":["Directly encodes the BST definition","Clear propagation of constraints","Intuitive for understanding BST structure","Easy to modify for variants"],"title":{"icon":"Target","text":"Range-Based Strengths","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Simpler state—just one previous value","Leverages a fundamental BST property","Often reuses existing traversal code","Natural for sorted validation"],"title":{"icon":"Target","text":"Inorder-Based Strengths","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"}],"titleType":"number","titleNumber":5},{"id":"edge-cases","title":"Edge Cases and Production Considerations","content":[{"data":{"content":"Robust BST validation must handle several edge cases that appear in production code and interviews:"},"type":"text"},{"data":{"items":["**Empty tree**: An empty tree (null root) is a valid BST by definition. Both approaches handle this: range-based returns true for null node; inorder never processes any nodes.","**Single node**: A tree with one node and no children is always a valid BST. No constraints can be violated.","**All left or all right (skewed tree)**: These should be valid if values are properly ordered. Tests the recursive structure thoroughly.","**Integer boundaries**: Nodes with values at `INT_MIN` or `INT_MAX` can break naive implementations using infinity. Use nullable bounds or wider types (long in Java).","**Duplicate values**: Clarify the duplicate policy. If not allowed, fail on equal values. If allowed on one side, adjust inequality checks accordingly.","**Very deep trees**: For extremely deep trees, recursive implementations may cause stack overflow. Consider iterative solutions for production use."],"title":{"icon":"AlertCircle","text":"Critical Edge Cases","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"fileName":"edge_case_handling.py","languages":[{"code":"$72","label":"Python","value":"python"}]},"type":"code"},{"data":{"icon":"AlertCircle","title":"Integer Overflow Trap","content":"In languages like Java or C++, using `Integer.MIN_VALUE` and `Integer.MAX_VALUE` as initial bounds can fail if the tree contains nodes with those exact values. The safer approach is using nullable bounds (Integer wrapper in Java) or wider types (long) to avoid this edge case.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"common-mistakes","title":"Common Mistakes and Debugging","content":[{"data":{"content":"BST validation is a common interview question precisely because it exposes several subtle errors. Being aware of these helps you avoid them:"},"type":"text"},{"data":{"items":["**Checking only parent-child relationships**: The most common mistake. Always remember BST is a global constraint, not local.","**Off-by-one in inequality**: Using `<` instead of `<=` (or vice versa) changes whether duplicates are allowed. Be consistent and intentional.","**Forgetting to update bounds correctly**: When recursing left, the current node becomes the new upper bound. When recursing right, it becomes the new lower bound. Getting this backwards invalidates the algorithm.","**Not handling null nodes**: Both children being null is the expected termination condition. Failing to handle null returns causes crashes.","**Mixing up min/max semantics**: Remember: `min_val` is the exclusive lower bound (value must be > min_val), and `max_val` is the exclusive upper bound (value must be < max_val).","**Incorrect initial bounds**: Starting with bounds that are too tight (like 0 and 100) excludes valid trees. Use infinity or null for unbounded."],"title":{"icon":"XCircle","text":"Frequent Errors","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**Debugging Strategy:**\n\nWhen your BST validation produces wrong results:\n\n1. **Trace manually**: Draw the tree and walk through each node with its valid range\n2. **Check the base case**: Ensure null returns true\n3. **Verify bound updates**: Print the bounds at each recursive call\n4. **Test edge cases individually**: Empty tree, single node, skewed trees, min/max values\n5. **Validate inequality direction**: Confirm < vs <= matches your duplicate policy"},"type":"text"},{"data":{"icon":"Lightbulb","title":"Interview Tip","content":"If you're unsure during an interview, explicitly state 'I'll assume no duplicates are allowed, so I'll use strict inequality.' This shows awareness of the ambiguity and prevents silent errors in your solution.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"complexity-analysis","title":"Complexity Analysis Deep Dive","content":[{"data":{"content":"Understanding the complexity of BST validation reinforces fundamental reasoning about tree algorithms:"},"type":"text"},{"data":{"content":"**Time Complexity: O(n)**\n\nBoth approaches visit each node exactly once:\n- Range-based: Each node is processed once during the DFS\n- Inorder: Each node is visited once during the traversal\n\nAt each node, we perform O(1) work (comparisons, bound updates). With n nodes, total work is O(n).\n\nNo approach can do better than O(n) because we must examine every node to guarantee correctness. A single invalid node anywhere in the tree invalidates the BST—we can't skip any nodes."},"type":"text"},{"data":{"content":"**Space Complexity: O(h)**\n\nThe space complexity is dominated by the recursion stack (or explicit stack for iterative versions):\n\n- **Balanced tree** (height h = log n): O(log n) space\n- **Skewed tree** (height h = n): O(n) space\n\nFor interview purposes, stating O(h) is precise. Stating O(n) worst case is also acceptable."},"type":"text"},{"data":{"rows":[["Perfect binary tree","log₂(n)","O(log n)","1 million nodes → ~20 stack frames"],["Complete binary tree","log₂(n)","O(log n)","Same as perfect, slight variation"],["Left-skewed tree","n","O(n)","1 million nodes → 1 million stack frames"],["Right-skewed tree","n","O(n)","Same as left-skewed"],["Random BST (expected)","~2 ln(n)","O(log n)","Expected balanced on average"]],"caption":"Space Complexity by Tree Shape","headers":["Tree Type","Height (h)","Space Complexity","Example"]},"type":"table"},{"data":{"icon":"Info","title":"Why O(h) Matters","content":"The O(h) space complexity is characteristic of DFS-based tree algorithms. It's also why binary search trees with guaranteed O(log n) height (like AVL and Red-Black trees) are preferred in production—they guarantee logarithmic stack depth for all recursive operations.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":8},{"id":"real-world-applications","title":"Real-World Applications","content":[{"data":{"content":"While BST validation might seem like purely algorithmic practice, it has genuine real-world applications:"},"type":"text"},{"data":{"items":["**Data Integrity Verification**: Database indices often use tree structures. Validating the tree invariants can detect corruption from hardware failures, software bugs, or incomplete transactions.","**Deserialization Safety**: When loading tree data from files, network responses, or user input, validation ensures the data forms a valid BST before use—preventing undefined behavior in BST operations.","**Testing and QA**: Unit tests for BST implementations should verify that after any operation (insert, delete, etc.), the tree remains a valid BST. This is essential for correctness verification.","**Debugging Complex Trees**: When BST operations produce unexpected results, validation can quickly identify whether the tree structure itself is corrupted, narrowing the bug search.","**Merge/Migration Validation**: When combining data from multiple sources into a BST, validation confirms the merge preserved ordering properties."],"title":{"icon":"Zap","text":"Production Use Cases","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"content":"**Example: Database Index Corruption Detection**\n\nConsider a database using a B-tree index (a generalization of BST). After a power failure:\n\n```\n1. System restarts\n2. Database runs integrity checks\n3. Index validation discovers a subtree violates ordering\n4. Database triggers index rebuild from source data\n5. Operations resume with corrected index\n```\n\nWithout validation, the corrupted index would cause wrong query results or crashes. The validation algorithm—though running in O(n)—is essential for system reliability."},"type":"text"}],"titleType":"number","titleNumber":9},{"id":"summary","title":"Summary and Key Takeaways","content":[{"data":{"content":"BST validation is a foundational problem that teaches critical lessons about tree algorithms and the BST property. Let's consolidate what we've learned:"},"type":"text"},{"data":{"type":"ordered","items":["**The BST property is global, not local**: Every node must satisfy constraints from all ancestors, not just its parent. Checking only parent-child relationships is incorrect.","**Two correct approaches exist**: Range-based recursion (track valid [min, max] range) and inorder traversal (verify strictly increasing sequence). Both achieve O(n) time and O(h) space.","**Range propagation encodes ancestor constraints**: Going left adds an upper bound; going right adds a lower bound. This carries the global constraint downward.","**Inorder property is fundamental**: A valid BST's inorder traversal is sorted. This property underlies many BST algorithms and is worth internalizing.","**Edge cases require care**: Handle empty trees, single nodes, integer boundaries, and duplicate policies. Production code must be robust to all cases.","**Know both approaches**: Different contexts favor different solutions. Being fluent in both demonstrates mastery."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**Looking Ahead:**\n\nBST validation is the first in a series of common BST patterns. Having mastered the fundamental property check, we're now equipped to explore more complex patterns:\n\n- **Floor and Ceiling**: Finding the largest value ≤ target or smallest value ≥ target\n- **Range Queries**: Extracting all values within a given range\n- **Construction**: Building a balanced BST from sorted data\n- **Rebalancing**: Transforming an unbalanced BST into a balanced one\n\nEach of these patterns builds on the deep understanding of BST structure that validation requires."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand how to correctly validate a Binary Search Tree using both range-based and inorder approaches. You know why naive approaches fail, how to handle edge cases, and where this pattern appears in production systems. Next, we'll explore finding floor and ceiling values in a BST.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":10}],"isLocked":false},{"id":"seed_9474058ad52855b6ead36f40fcd2e10b","title":"Finding Floor and Ceiling","order":1,"content":null,"isLocked":true},{"id":"seed_36b1bce4787484e46222ec5c7852d841","title":"Range Queries in BST","order":2,"content":null,"isLocked":true},{"id":"seed_3086bef33cdaa962aea33881750f189b","title":"Converting Sorted Array to BST","order":3,"content":null,"isLocked":true},{"id":"seed_926265ffd5676102c7a304eab4b8069a","title":"Balancing an Existing BST","order":4,"content":null,"isLocked":true}]}}