Published: Jan 16, 2023
Problem 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 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.
Constraints: The number of nodes in the tree is in the range
[1, 10**4]
.
-2**31 <= Node.val <= 2**31 - 1
Examples
Example 1
Input: root = [2,1,3]
Output: true
Explanation:
2
/ \
1 3
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.
5
/ \
1 4
/ \
3 6
How to Solve
Check each node value is less than upper bound and greater than lower bound. Start from a minimum value as a lower bound and a maximum value as a upper bound. The solution here took depth-first search (recursive). When it goes to a left subtree, lower bound is from previous one and upper bound is a parent node value. When it goes to a right subtree, lower bound is a parent node value and upper bound is from previous one. If all node values are valid, the tree is a valid BST.
Solution
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class ValidateBinarySearchTree {
private:
bool helper(TreeNode* root, long long low, long long high)
{
if (!root)
return true;
if (root->val <= low || root->val >= high)
return false;
return helper(root->left, low, root->val) && helper(root->right, root->val, high);
}
public:
bool isValidBST(TreeNode* root) {
return helper(root, LLONG_MIN, LLONG_MAX);
}
};
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class ValidateBinarySearchTree:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def helper(root: Optional[TreeNode], low, high)-> bool:
if not root:
return True
if root.val <= low or root.val >= high:
return False
return helper(root.left, low, root.val) and\
helper(root.right, root.val, high)
return helper(root, float('-inf'), float('inf'))
# Definition for a binary tree node.
# class TreeNode
# attr_accessor :val, :left, :right
# def initialize(val = 0, left = nil, right = nil)
# @val = val
# @left = left
# @right = right
# end
# end
def helper(root, low, high)
if !root
return true
end
if root.val <= low || high <= root.val
return false
end
return helper(root.left, low, root.val) && helper(root.right, root.val, high)
end
# @param {TreeNode} root
# @return {Boolean}
def is_valid_bst(root)
return helper(root, -2**31-1, 2**31)
end
Complexities
- Time:
O(n)
- Space:
O(h)
– h: height of the tree