aloalgoValidate Binary Search Tree
Easy
You are given the root of a binary tree, root.
Your task is to determine if it is a valid binary search tree (BST).
You may assume that:
- The left subtree of a
nodemust contain only nodes with values less than thenode's value. - The right subtree of a
nodemust contain only nodes with values greater than thenode's value. - Both the left and right subtrees must also be valid binary search trees.
Example 1
Input
Output
True
Explanation:
This is a valid BST. 5's left child (2) is smaller, and its right child (8) is larger. This property holds true for all nodes.
Example 2
Input
Output
False
Explanation:
This is not a valid BST. Although 6 is greater than its parent (4), it is in the left subtree of the root (5). Therefore, all nodes in that subtree must be less than 5, which 6 is not.
Example 3
Input
Output
False
Explanation:
This is not a valid BST. The node with value 1 is in the right subtree of the root (2), but 1 is not greater than 2.
Input
Output
True