Check whether a binary tree is a valid binary search tree
Coding problemMediumAsked in: Adobe, Amazon, Flipkart, Goldman Sachs, Microsoft, Walmart
Given the root of a binary tree, return true if it is a valid binary search tree, and false otherwise. In a valid binary search tree, for every node:
- every value in its left subtree is strictly smaller than the node's value;
- every value in its right subtree is strictly larger than the node's value.
So equal values are not allowed. An empty tree is valid. Trees are written in level order, with null for a missing child.
Examples
Example 1
Input: root = [2,1,3]
Output: true
Example 2
Input: root = [5,1,4,null,null,3,6]
Output: false
The right child 4 is smaller than the root 5.
Example 3
Input: root = [5,4,6,null,null,3,7]
Output: false
3 is in the right subtree of 5 but smaller than 5, even though it is a correct left child of 6.
Constraints
- The tree has between 0 and 100,000 nodes
- Each value is a 32-bit integer
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.