Skip to main content

Validate Binary Search Tree

Problem Statement:​

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  of a node contains only nodes with keys less than the node's key.

    subtree

  • 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.

  • Example:

✅ Solution: Validate Binary Search Tree — Recursion with Range Limits​

// ✅ Validate BST using Recursion with Min/Max Range

class Solution {
public:
    bool validate(TreeNode* currentNode, long minValue, long maxValue) {
        if (currentNode == nullptr) return true;

        // The current value must lie strictly between minValue and maxValue
        if (currentNode->val <= minValue || currentNode->val >= maxValue) return false;

        // Recursively check left and right subtrees with updated ranges
        return validate(currentNode->left, minValue, currentNode->val) &&
               validate(currentNode->right, currentNode->val, maxValue);
    }

    bool isValidBST(TreeNode* root) {
        return validate(root, LONG_MIN, LONG_MAX);
    }
};

📝 How It Works​

  • Core Idea:

    Each node must fall within a valid range:

    • Left subtree values must be less than the current node value.
    • Right subtree values must be greater than the current node value.

  • How Ranges Update:

    • For left child: maxValue gets updated to currentNode->val.
    • For right child: minValue gets updated to currentNode->val.

  • Why Use LONG_MIN and LONG_MAX:

    Handles edge cases where node values could be at integer limits.

🧩 Key Formula / Recurrence​

  • validate(node, minValue, maxValue)
    • Check node->val > minValue && node->val < maxValue
    • Recurse:
      • validate(node->left, minValue, node->val)
      • validate(node->right, node->val, maxValue)

⏱️ Time & Space Complexity​

AspectComplexity
TimeO(N)
SpaceO(H) (Recursion stack)
  • N = Number of nodes
  • H = Height of BST

⚠️ Edge Cases​

  • Single-node tree → Valid BST.
  • Skewed tree (all left or all right) → Still valid.
  • Nodes with INT_MIN or INT_MAX → Use LONG_MIN/LONG_MAX to avoid overflow issues.
  • Duplicates → Not allowed in strict BST.

💡 Other Approaches​

ApproachTimeSpaceNotes
Inorder TraversalO(N)O(N)Store elements, check sorted.
Morris TraversalO(N)O(1)Harder to implement.

🔁 Related Problems​

  • LeetCode 98 — Validate Binary Search Tree
  • LeetCode 653 — Two Sum IV — Input is a BST
  • LeetCode 530 — Minimum Absolute Difference in BST

If you'd like this turned into a formatted Notion card or a revision PDF, just let me know!

💬

Discussion & Doubts