Validate Binary Search Tree

📋

Problem

Imagine you are building a database index that relies on a binary search tree structure. You need to verify if the tree is correctly structured to ensure fast lookups.

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. Input: root node of a binary tree. Output: true if the tree is a valid BST, false otherwise.

The number of nodes in the tree is in the range [1, 10^5].Node values are integers and can be negative or positive.You must solve the problem with O(n) time complexity.

Edge cases: Single node tree → trueTree with duplicate values → false (BST requires strictly less/greater)Left skewed tree (all nodes have only left child) → true if values strictly decreasing

</>

IDE

def is_valid_bst(root: Optional[TreeNode]) -> bool:public boolean isValidBST(TreeNode root)bool isValidBST(TreeNode* root)function isValidBST(root)

def is_valid_bst(root):
    # Write your solution here
    pass

class Solution {
    public boolean isValidBST(TreeNode root) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool isValidBST(TreeNode* root) {
    // Write your solution here
    return false;
}

function isValidBST(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: trueCode only compares immediate children to parent, missing violations deeper in subtrees.✅ Use recursive min/max bounds to validate all descendants, not just direct children.

Wrong: trueCode allows duplicate values by using <= or >= instead of strict < and > comparisons.✅ Change comparisons to strict inequalities: left < node < right.

Wrong: falseCode fails on single node trees due to missing base case or null pointer errors.✅ Return true immediately for null or leaf nodes.

Wrong: TLECode uses O(n^2) brute force approach checking subtree min/max repeatedly.✅ Implement O(n) solution using min/max range validation or inorder traversal.

✓

Test Cases

Try testing your solution on minimal trees and trees with duplicates to catch base case bugs.

Think about how to detect violations not just at immediate children but anywhere in the subtree.

Optimize your solution to run in linear time by avoiding repeated subtree traversals.

t1_01basic

Input{"root":[2,1,3]}

Expectedtrue

⏱ Performance - must finish in 2000ms

The tree: 2 / \ 1 3 All left nodes are less than 2 and all right nodes are greater than 2.

💡 Recall the BST property: left < node < right for all nodes.

💡 Use a recursive helper with min and max bounds to validate each node.

💡 Check that each node's value is strictly between allowed min and max ranges.

Why it failed: Failed basic test: likely did not enforce strict inequality or min/max bounds correctly. Fix by passing updated min/max limits in recursion.

✓ Correctly validates BST property using min/max bounds.

t1_02basic

Input{"root":[5,1,7,null,null,6,8]}

Expectedtrue

⏱ Performance - must finish in 2000ms

The tree: 5 / \ 1 7 / \ 6 8 All left nodes less than 5, right nodes greater than 5, and subtrees valid BSTs.

💡 Check each subtree recursively with updated min/max constraints.

💡 Remember to update bounds when moving left or right in the tree.

💡 Ensure no node violates the BST property by being outside its allowed range.

Why it failed: Failed to update min/max bounds properly when recursing into subtrees. Fix by passing correct bounds for left and right children.

✓ Properly maintains and checks min/max bounds for all nodes.

t2_01edge

Input{"root":[1]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Single node tree is always a valid BST.

💡 A single node with no children trivially satisfies BST conditions.

💡 Check that your code handles leaf nodes correctly without errors.

💡 Return true immediately if node has no children.

Why it failed: Code fails on single node trees, possibly due to null pointer or missing base case. Fix by returning true when node is leaf or null.

✓ Handles single node trees correctly.

t2_02edge

Input{"root":[2,2,2]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Tree with duplicate values violates strict BST property (left < node < right).

💡 BST requires strict inequality, not <= or >=.

💡 Check that your comparisons use < and >, not <= or >=.

💡 Fix comparisons to enforce strict less than for left and greater than for right.

Why it failed: Code incorrectly allows duplicates by using <= or >= instead of < and >. Fix by changing comparisons to strict inequalities.

✓ Correctly rejects trees with duplicate values.

t2_03edge

Input{"root":[3,2,null,1]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Left skewed tree with strictly decreasing values: 3 -> 2 -> 1 is a valid BST.

💡 Check that left children are strictly less than their parent nodes.

💡 Ensure recursion correctly handles skewed trees with null right children.

💡 Verify min/max bounds propagate correctly down the left chain.

Why it failed: Code fails on skewed trees due to incorrect null handling or bounds propagation. Fix by properly handling null children and updating bounds.

✓ Correctly validates left skewed BSTs.

t3_01corner

Input{"root":[10,5,15,null,null,6,20]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Right subtree has a node (6) less than root (10), violating BST property.

💡 BST property must hold for all descendants, not just immediate children.

💡 Use min/max bounds to check entire subtree ranges, not just direct children.

💡 Fix by passing down min/max limits and validating all nodes against them.

Why it failed: Code only compares immediate children to parent, missing deeper violations. Fix by enforcing min/max bounds recursively for all descendants.

✓ Correctly detects violations deep in subtrees.

t3_02corner

Input{"root":[1,null,1]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Right child equals root value, violating strict greater-than rule.

💡 BST requires right child values strictly greater than parent.

💡 Check that your code uses > for right child comparisons, not >=.

💡 Fix comparisons to enforce strict inequality for right subtree.

Why it failed: Code allows equal values on right subtree by using >= instead of >. Fix by changing to strict > comparison.

✓ Correctly rejects equal values on right subtree.

t3_03corner

Input{"root":[5,4,6,null,null,3,7]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Node with value 3 in right subtree of 5 is less than 5, violating BST property.

💡 BST property applies to all descendants, not just immediate children.

💡 Use min/max bounds to validate all nodes in subtrees.

💡 Fix by passing updated bounds and checking all nodes against them.

Why it failed: Code only checks immediate children, missing violations deeper in subtree. Fix by enforcing min/max bounds recursively.

✓ Detects violations in deeper subtree nodes.

t4_01performance

Input{"root":[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10,null,11,null,12,null,13,null,14,null,15,null,16,null,17,null,18,null,19,null,20,null,21,null,22,null,23,null,24,null,25,null,26,null,27,null,28,null,29,null,30,null,31,null,32,null,33,null,34,null,35,null,36,null,37,null,38,null,39,null,40,null,41,null,42,null,43,null,44,null,45,null,46,null,47,null,48,null,49,null,50,null,51,null,52,null,53,null,54,null,55,null,56,null,57,null,58,null,59,null,60,null,61,null,62,null,63,null,64,null,65,null,66,null,67,null,68,null,69,null,70,null,71,null,72,null,73,null,74,null,75,null,76,null,77,null,78,null,79,null,80,null,81,null,82,null,83,null,84,null,85,null,86,null,87,null,88,null,89,null,90,null,91,null,92,null,93,null,94,null,95,null,96,null,97,null,98,null,99,null,100]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Right skewed tree with n=100 nodes, strictly increasing values. O(n) time complexity required to pass within 2 seconds.

💡 Use O(n) time complexity algorithms like inorder traversal or min/max range validation.

💡 Avoid O(n^2) brute force approaches that check subtree min/max repeatedly.

💡 Implement recursive validation passing down min/max bounds or use inorder traversal.

Why it failed: TLE due to O(n^2) brute force approach checking subtree min/max repeatedly. Fix by using O(n) min/max range or inorder traversal validation.

✓ Efficient O(n) solution confirmed by passing performance test.