Close Menu
    What's Hot
    Explore the coolest frontend learning platform !
    Visit NamasteDev
    Tuesday, June 16

    Valid Binary Search Tree

    Updated: Algorithms No Comments2 Mins Readdevangini123By

    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 subtree of a node contains only nodes with keys strictly less than the node’s key.
    • The right subtree of a node contains only nodes with keys strictly greater than the node’s key.
    • Both the left and right subtrees must also be binary search trees.

    Examples:

    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.

    Constraints:

    • The number of nodes in the tree is in the range [1, 104].
    • -231 <= Node.val <= 231 - 1

    Approach

    • Base Case: If the current node is null, return true.
    • Violation Check:
      • If curr.val ≤ lo or ≥ hi, it violates BST rules, so return false.
    • Recursive Check:
      • Left subtree must be in range (lo, curr.val)
      • Right subtree must be in range (curr.val, hi)
    • Return true only if both left and right subtrees are valid.

    Time Complexity:

  • Time Complexity = O(n)

    • Space Complexity:

  • Space Complexity = O(h)(h=tree height)

    • Dry Run

    Function Call: isValidBST(root) where
    root = Node(5)
    ├── left: Node(3)
    │   ├── left: Node(2)
    │   └── right: Node(4)
    └── right: Node(7)
        ├── left: Node(6)
        └── right: Node(8)

    Step 1:
    → Call isValidBST(curr = 5, lo = null, hi = null)
    → 5 is valid (no bounds)
    → Call isValidBST(curr = 3, lo = null, hi = 5)
    → 3 is valid (less than 5)
    → Call isValidBST(curr = 2, lo = null, hi = 3)
    → 2 is valid (less than 3)
    → Call isValidBST(curr = null, lo = null, hi = 2) → returns true
    → Call isValidBST(curr = null, lo = 2, hi = 3) → returns true
    → return true for Node(2)

    → Call isValidBST(curr = 4, lo = 3, hi = 5)
    → 4 is valid (between 3 and 5)
    → Call isValidBST(curr = null, lo = 3, hi = 4) → returns true
    → Call isValidBST(curr = null, lo = 4, hi = 5) → returns true
    → return true for Node(4)

    → return true for Node(3)

    → Call isValidBST(curr = 7, lo = 5, hi = null)
    → 7 is valid (greater than 5)
    → Call isValidBST(curr = 6, lo = 5, hi = 7)
    → 6 is valid (between 5 and 7)
    → Call isValidBST(curr = null, lo = 5, hi = 6) → returns true
    → Call isValidBST(curr = null, lo = 6, hi = 7) → returns true
    → return true for Node(6)

    → Call isValidBST(curr = 8, lo = 7, hi = null)
    → 8 is valid (greater than 7)
    → Call isValidBST(curr = null, lo = 7, hi = 8) → returns true
    → Call isValidBST(curr = null, lo = 8, hi = null) → returns true
    → return true for Node(8)

    → return true for Node(7)

    → return true for root Node(5)

    Final Result: true – the binary tree is a valid BST. 
    
var isValidBST = function(curr, lo = null, hi = null) {
    if (!curr) return true;
    if ((lo !== null && curr.val <= lo) || (hi !== null && curr.val >= hi))
        return false;
    let isLeftBST = isValidBST(curr.left, lo, curr.val);
    let isRightBST = isValidBST(curr.right, curr.val, hi);
    return isLeftBST && isRightBST;
}
  
    
def isValidBST(curr, lo=float('-inf'), hi=float('inf')):
    if not curr:
        return True
    if curr.val <= lo or curr.val >= hi:
        return False
    return isValidBST(curr.left, lo, curr.val) and isValidBST(curr.right, curr.val, hi)
            
    
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}
class Solution {
    public boolean isValidBST(TreeNode curr) {
        return isValid(curr, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean isValid(TreeNode curr, long lo, long hi) {
        if (curr == null) return true;
        if (curr.val <= lo || curr.val >= hi) return false;
        return isValid(curr.left, lo, curr.val) && isValid(curr.right, curr.val, hi);
    }
}
     
    
bool isValidBST(TreeNode* curr, long long lo = LLONG_MIN, long long hi = LLONG_MAX) {
    if (!curr) return true;
    if (curr->val <= lo || curr->val >= hi) return false;
    return isValidBST(curr->left, lo, curr->val) && isValidBST(curr->right, curr->val, hi);
}
    
    
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};
bool isValidBST(struct TreeNode* curr, long long lo, long long hi) {
    if (!curr) return true;
    if (curr->val <= lo || curr->val >= hi) return false;
    return isValidBST(curr->left, lo, curr->val) && isValidBST(curr->right, curr->val, hi);
}
            
    
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
}
public class Solution {
    public bool IsValidBST(TreeNode curr, long lo = long.MinValue, long hi = long.MaxValue) {
        if (curr == null) return true;
        if (curr.val <= lo || curr.val >= hi) return false;
        return IsValidBST(curr.left, lo, curr.val) && IsValidBST(curr.right, curr.val, hi);
    }
}

    Keep Reading

    Add A Comment
    Leave A Reply

    Demo

    Courses

    Community

    Contact Us