Loading...
Loading...
You are given the root of a binary tree. Return whether it is a binary search tree.
A binary tree is a binary search tree if, for every node, every value in its left subtree is smaller than the node's value, every value in its right subtree is bigger than the node's value, and both subtrees are themselves binary search trees.
Note that this rule is strict: if any value appears twice anywhere in the tree, the tree is not a binary search tree, even when the two occurrences are far apart.
Your function receives root as a TreeNode. The node type is provided for you, with val, left, and right fields.
The examples below write the tree as its level-order traversal, where null marks a missing child of a listed node and trailing nulls are omitted. That is only how the input is displayed; the decoding is done for you.
root.Node.val ≤109Every value in 4's left subtree (2, 1, 3) is less than 4 and every value in its right subtree (6, 5, 7) is greater than 4, and the same rule holds recursively at 2 and at 6.
3 sits in the right subtree of 5, so it must be bigger than 5, but 3 is smaller than 5 even though it is bigger than its own parent 4.
6 sits in the right subtree of 10, so it must be bigger than 10, but 6 is smaller than 10 even though it is smaller than its own parent 15.