Is it a binary search tree?
A binary search tree (BST) is a binary tree that keeps one promise at every node: every value in the node's left subtree is smaller than the node's value, and every value in its right subtree is larger. A node's subtree is that node and everything below it. Smaller and larger are strict, so a BST never holds a value twice.
You get the root of a binary tree, which may or may not keep that promise. Return True when every node keeps it, and False when any node breaks it. An empty tree (root is None) counts as a BST: it has no node that breaks the promise.
Trees in the examples are written in level order, the way build_tree reads them: the root, then each row from left to right, with None where a child is missing.
root = [5, 3, 8, 1, 4, None, 9]OutputTrueBelow 5, the left side holds 3, 1 and 4, all smaller than 5, and the right side holds 8 and 9, both larger. The same check passes at 3 and at 8.
root = [5, 3, 8, 1, 6]OutputFalse6 is the right child of 3, and 6 > 3 is fine there. But 6 is also in the left subtree of 5, where every value must be smaller than 5.
root = [6, 2, 6]OutputFalseThe right child equals the root. Values on the right must be strictly larger.
0 ≤ number of nodes ≤ 2 × 105
-231 ≤ node value ≤ 231 - 1
The tree is at most 600 levels deep, so a recursive solution fits under plain Python's default of about 1,000 nested calls.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.