357. Largest Value Below X
The tree is a binary search tree. Print the largest value STRICTLY less than
x, or None if every value is at least x.
The value x need not be present in the tree.
Walk down from the root keeping a best-so-far. At each node, if its value is less
than x it is a better candidate than anything recorded earlier, so remember it
and go right looking for something larger still. Otherwise the node and its whole
right subtree are too big, so go left.
That visits one path rather than the whole tree, which is the point of having a search tree.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value, x ≤ 1000000000` - All values are distinct and the tree is a valid search tree.
Input
The first line contains two integers n and x.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains the left and right child of node i,
using 0 for no child. Node 1 is the root, and the tree is a search tree.
Output
Print the largest value strictly less than x, or None.
Hints
Four rungs, in order. The last two open once you have submitted an attempt — a wrong one counts.