## Description

Title

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

Assume a 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.

Example 1:

``````   2
/ \
1   3
``````

Input: [2,1,3]

Output: true

Example 2:

``````    5
/ \
1   4
/ \
3   6
``````

Input: [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.

## Solution

 `````` 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 26 27 28 29 `````` ``````class Solution { public: bool isValidBST(TreeNode* root) { if (!root) { return true; } long first = LONG_MIN; return visit(root, first); } private: bool visit(TreeNode* root, long &last) { if (root->left && !visit(root->left, last)) { return false; } if (root->val <= last) { return false; } last = root->val; if (root->right && !visit(root->right, last)) { return false; } return true; } };``````