98. Validate Binary Search Tree

98. Validate Binary Search Tree (Medium)

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.

 

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.

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -231 <= Node.val <= 231 - 1

Companies:
Amazon, Facebook, Bloomberg, Microsoft, Zillow, Apple, Google, Uber, ByteDance

Related Topics:
Tree, Depth-First Search, Binary Search Tree, Binary Tree

Similar Questions:

• Binary Tree Inorder Traversal (Easy)
• Find Mode in Binary Search Tree (Easy)

Solution 1. Pre-order Traversal

// OJ: https://leetcode.com/problems/validate-binary-search-tree
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
public:
    bool isValidBST(TreeNode* root, TreeNode *left = NULL, TreeNode *right = NULL) {
        if (!root) return true;
        if ((left && root->val <= left->val) || (right && root->val >= right->val)) return false;
        return isValidBST(root->left, left, root) && isValidBST(root->right, root, right);
    }
};

Or

// OJ: https://leetcode.com/problems/validate-binary-search-tree/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
public:
    bool isValidBST(TreeNode* root, long left = LONG_MIN, long right = LONG_MAX) {
        if (!root) return true;
        if (root->val <= left || root->val >= right) return false;
        return isValidBST(root->left, left, root->val) && isValidBST(root->right, root->val, right);
    }
};

Solution 2. In-order traversal

// OJ: https://leetcode.com/problems/validate-binary-search-tree
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(logN)
class Solution {
    TreeNode *prev = NULL;
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        if (!isValidBST(root->left) || (prev && prev->val >= root->val)) return false; 
        prev = root;
        return isValidBST(root->right);
    }
};