875. Search in Binary Search Tree

Given the root of a binary search tree and a target value, determine whether the target exists in the BST. Return true or false. Exploit the BST property to search in O(h) time. 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: Boolean — true or false.

Examples

Input: [8,3,10,1,6,null,14] | 6
Output: true
Explanation: 6 is present.

Input: [8,3,10,1,6,null,14] | 9
Output: false
Explanation: 9 is absent.

Input: [5] | 5
Output: true
Explanation: Single matching node.

Constraints

• 0<=nodes<=10^4
• valid BST
• -10^5<=value,target<=10^5

Asked by