Algorithm-Day44-Validate-Binary-Search-Tree-lc-98

Posted on In , Views:

🧩 Problem Description

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as:

  • The left subtree of a node contains only nodes with values less than the node’s value.
  • The right subtree of a node contains only nodes with values greater than the node’s value.
  • Both the left and right subtrees must also be valid BSTs.

💬 Example

1
2
Input: root = [2,1,3]
Output: true
1
2
3
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The value 3 is in the right subtree of 5 but is less than 5.

💡 Approach 1: DFS with Value Ranges

We recursively check each node’s value against an allowed range:

  1. Initially, the root has range (-∞, +∞).
  2. For left child: upper bound is parent’s value.
  3. For right child: lower bound is parent’s value.
  4. If any node violates the range rule, it’s not a BST.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean validate(TreeNode node, long min, long max) {
        if (node == null) return true;
        if (node.val <= min || node.val >= max) return false;

        return validate(node.left, min, node.val) &&
               validate(node.right, node.val, max);
    }
}

💡 Approach 2: Inorder Traversal Check

  • Perform inorder traversal of the tree.
  • If the resulting sequence is strictly increasing, it’s a valid BST.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    private long prev = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if (!isValidBST(root.left)) return false;
        if (root.val <= prev) return false;
        prev = root.val;
        return isValidBST(root.right);
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n) — every node visited once.
  • Space Complexity: O(h) — recursion depth (h is tree height).

✍️ Summary

  • Range-check DFS is the most intuitive and avoids extra storage.
  • Inorder traversal works because BST’s inorder is sorted.
  • Common BST pitfalls:
    • Duplicate values — BST usually disallows duplicates.
    • Only checking immediate children is not enough — must check whole range.

Related problems: lc-230 (Kth Smallest in BST), lc-701 (Insert into BST), lc-450 (Delete Node in BST)