882. Inorder Predecessor in BST

Given the root of a binary search tree and a target value, return the in-order predecessor of the target — the largest key strictly smaller than the target. Return -1 if no predecessor exists. The target may or may not be present. The input gives a level-order BST array and the target separated by ' | '.

Input: A level-order BST array and the target, separated by ' | '.

Output: Integer — the predecessor value, or -1.

Examples

Input: [8,3,10,1,6,null,14] | 6
Output: 3
Explanation: Largest key smaller than 6.

Input: [8,3,10,1,6,null,14] | 1
Output: -1
Explanation: No predecessor for the minimum.

Input: [5] | 9
Output: 5
Explanation: 5 is the previous key.

Constraints

• 0<=nodes<=10^4
• valid BST

Asked by