98. Validate Binary Search Tree

📝 Problem Details

• Title: 98. Validate Binary Search Tree
• Link: https://leetcode.com/problems/validate-binary-search-tree/
• Difficulty: Medium
• Tags/Categories: BST Recursion

💭What Were My Initial Thoughts?

BST validity:
- left subtree contains nodes that are less than the parent
- right subtree contains nodes that are greater than the parent
- both left and right subtrees are also BSTs

- only checking the immediate parent-child relationships could incorrectly classify an invalid BST as valid
- we need to track the allowed value range as we move down the tree

💡 Explanation of Solution

- use a helper function to perform pre-order DFS
	- the helper function takes in a lower and upper node which will form the range where `lower < current val < upper`
	- these constraints are updated and passed down to its children

Why not just pass in the values instead of the entire node?
- we **could** just pass in the values, but would risk running into edge cases where the lower or upper bound are nullptr

⌛ Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n) worst case 

💻 Implementation of Solution

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return validate(root, nullptr, nullptr);
    }
 
    bool validate(TreeNode* node, TreeNode* lower, TreeNode* upper) {
        if(node == nullptr) return true;
 
        // check if lower is not null
        // check if current node's val is <= to the lower val
        if( (lower && node->val <= lower->val)
        || ( upper && node->val >= upper->val)) {
            return false;
        }
 
        return validate(node->left, lower, node) && validate(node->right, node, upper);
    }
};