Search in a Binary Search Tree

Given a binary search tree root and an integer val, determine whether val is in the tree.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Search-in-a-Binary-Search-Tree

Examples

Example 1

Input

• root =

• val = 4

Output

• answer = True

Example 2

Input

• root =

• val = 100

Output

• answer = False

Solution