Valid Search Tree

You are given the root of a binary tree. Return whether it is a binary search tree, which means that for every node:

  • every value in its left subtree is smaller than the node's value,
  • every value in its right subtree is larger than the node's value.

Equal values are not allowed anywhere in a search tree.

Trees in the examples are written level by level, left to right, with null where a child is missing: [1,null,2] is a root 1 with only a right child, 2. [] is an empty tree, with no root at all.

Constraints

  • 1 ≤ number of nodes ≤ 10,000
  • -2³¹ ≤ node value ≤ 2³¹ - 1 (the whole range of a 32-bit int)
  • The tree is at most 1,000 levels deep.

Example 1

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

1 is smaller than 2 and 3 is larger.

Example 2

Input
root = [5,1,4,null,null,3,6]
Output
false
Why:

4 is in the root's right subtree, but it is smaller than 5.

Example 3

Input
root = [10,5,15,null,null,6,20]
Output
false
Why:

6 is fine next to its parent 15, but it is in the right subtree of 10, so it must be larger than 10.

Hints

    Was this a good challenge?

    Solved by
    0
    Submissions
    0
    Accepted
    –