330. Is It a Search Tree
Print Yes if the tree is a binary search tree and No otherwise.
The rule is not about parents and children. It is about whole subtrees: every value in a node's LEFT subtree must be smaller than it, and every value in its RIGHT subtree must be larger. Values are all distinct here, so equal values do not arise.
The tempting solution compares each node with its two children and passes them all. It is wrong, and this tree is why:
5
/ \
3 7
/ \
4 8
Every parent beats its own children. And 4 sits somewhere in the right subtree of 5 while being smaller than 5, so the tree is not a search tree. Both of that shape's variants are tests here.
The fix is to carry a permitted RANGE down the tree. The root may hold anything; its left child is capped above by the root's value; its right child is bounded below by it; and each step narrows the range further.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - All values are distinct. - The input always forms a valid tree rooted at node 1.
Input
The first line contains an integer n, the number of nodes.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains two integers, the left and right child of
node i, using 0 for no child. Node 1 is the root.
Output
Print Yes or No on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.