Binary Search Trees Using the ordering
387. Validate Binary Search Tree
You are given root, the root node of a binary tree. Return true if it is a valid binary search tree, and
false otherwise.
A binary search tree (BST) keeps its values in order. For every node, every value in its left subtree is smaller than the node's value, and every value in its right subtree is larger. The left subtree of a node is its left child and everything below it, and the right subtree is the same on the other side. An empty tree is a valid BST.
The examples write a tree level by level, from left to right, with null where a child is missing. So
root = [5,8,null,3] is the root 5 with a left child 8 and no right child, and 8 has a left child 3. The
missing children after the last node are left out.
Example 1
Input: root = [20, 10, 30, 5, 15, 25, 40, null, null, 12]
trueExplanation: Everything under 10 (5, 15 and 12) is smaller than 20, and everything under 30 is larger. Inside, 12 is the left child of 15, so it must be smaller than 15. It must also be larger than 10, because it is in the right subtree of 10. It is both.
Example 2
Input: root = [20, 10, 30, 5, 25]
falseExplanation: 25 is the right child of 10 and larger than 10, so it is fine against its parent. But 25 is also in the left subtree of 20, where every value must be smaller than 20.
Example 3
Input: root = [-2147483648, null, 2147483647]
trueExplanation: The values are the smallest and the largest 32-bit integers. The larger one is the right child, so the tree is in order.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ number of nodes ≤ 105-231 ≤ Node.val ≤ 231 − 1- The tree has at most 1000 levels.
Clarifying questions
What you would ask an interviewer before writing any code.