Validate Binary Search Tree Problem


Description

LeetCode Problem 98.

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:

1
2
Input: root = [2,1,3]
Output: true

Example 2:

1
2
3
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, 10^4].
  • -2^31 <= Node.val <= 2^31 - 1


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = NULL;
        return validate(root, prev);
    }
    bool validate(TreeNode* node, TreeNode* &prev) {
        if (node == NULL) return true;
        if (!validate(node->left, prev)) return false;
        if (prev != NULL && prev->val >= node->val) return false;
        prev = node;
        return validate(node->right, prev);
    }
};




Related Posts

Convert Sorted Array to Binary Search Tree Problem

LeetCode 108. Given an integer array nums where the elements...

Validate Binary Search Tree Problem

LeetCode 98. Given the root of a binary tree, determine...

Same Tree Problem

LeetCode 100. Given the roots of two binary trees p...

Recover Binary Search Tree Problem

LeetCode 99. You are given the root of a binary...

Unique Binary Search Trees Problem

LeetCode 96. Given an integer n, return the number of...

Unique Binary Search Trees II Problem

LeetCode 95. Given an integer n, return all the structurally...