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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        TreeNode *prev = nullptr;
        return traverse(root, prev);
    }

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

        if (!traverse(root->left, prev)) {
            return false;
        }

        if (prev != nullptr && root->val <= prev->val) {
            return false;
        }

        prev = root;
        return traverse(root->right, prev);
    }
};