Is It a Search Tree?

Medium

You are given the root of a binary tree. Check whether it is a binary search tree. A tree is a search tree when, for every node, all values in its left subtree are strictly smaller than the node's value and all values in its right subtree are strictly larger. Note that a node must be compared with all of its descendants, not just its direct children. Return True if the tree is a search tree and False otherwise.

Example 1

root=tree_node([10, 4, 15, 1, 7, 12, 20]) → True

Every node has only smaller values on its left and only larger values on its right, so this is a search tree.

Example 2

root=tree_node([10, 4, 15, None, 11]) → False

11 sits to the right of 4, which is fine locally, but it is in the left subtree of the root 10 and 11 > 10. The rule is broken.

Example 3

root=tree_node([6, 6]) → False

Values on the left must be strictly smaller, and here the left child equals the root.

Constraints

1 ≤ number of nodes ≤ 10⁴
-2³¹ ≤ Node.val ≤ 2³¹ − 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Binary Search Tree Binary Tree

Similar problems

Two Mixed-Up Nodes Medium K-th Smallest in a Search Tree Medium Biggest Search Subtree Medium Add Every Bigger Key Medium Keep Only a Range of a Search Tree Medium

Input

root=tree_node([10, 4, 15, 1, 7, 12, 20])

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 100 tests on the server, hidden ones included.