LeetCode 98. Validate Binary Search Tree

Question

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

https://leetcode.com/problems/validate-binary-search-tree/

Solution

• Solution1 – DFS, bottom up

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        if (root == null) return true;
        if (root.val >= maxVal || root.val <= minVal) return false;
        return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)