Skip to main content

Validate Binary Search Tree

Problem​

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.

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
   public:
    bool traversal(TreeNode* root, long long min, long long max) {
        if (!root) return true;
        if (root->val < min || root->val > max) return false;
        return (traversal(root->left, min, (long long)root->val - 1ll) &
                traversal(root->right, (long long)root->val + 1ll, max));
    }

    bool isValidBST(TreeNode* root) {
        return traversal(root, INT_MIN, INT_MAX);
    }
};