98. Validate Binary Search Tree

1. Description

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.

2. Example

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.

3. Constraints

• The number of nodes in the tree is in the range [1, $10^4$].
• $-2^{31}$ <= Node.val <= $2^{31} - 1$

4. Solutions

Depth-first Search

n is the number of nodes root
Time complexity: O(n)
Space complexity: O(logn->n)

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        int64_t prev_value = numeric_limits<int64_t>::min();
        return traverse(root, prev_value);
    }

private:
    bool traverse(TreeNode *root, int64_t &prev_value) {
        if (root == nullptr) {
            return true;
        }

        bool left_tree_valid = traverse(root->left, prev_value);
        bool root_valid = prev_value < root->val;
        prev_value = root->val;

        return left_tree_valid && root_valid && traverse(root->right, prev_value);
    }
};