Binary Search Tree Operations

In this problem, you are required to implement a Binary Search Tree (BST) from scratch with support for insertion, duplicate-handling, search, and in-order traversal. Given a sequence of integers to insert into the BST (duplicates must be ignored), and a set of query integers, your task is to build the BST, perform in-order traversal, and answer each search query.

The BST must maintain the invariant that for any node, all elements in the left subtree are less than its value and all elements in the right subtree are greater. The in-order traversal of a BST results in a sorted sequence.

For search queries, output “True” if the element is in the BST and “False” otherwise.

Hint: The in-order traversal can be formally written as follows in LaTeX: (inorder(node) = inorder(node.left) ; \Vert ; [node.data] ; \Vert ; inorder(node.right)), where (\Vert) denotes concatenation.

inputFormat

Input is read from stdin and consists of three lines:

1. The first line contains space-separated integers representing the elements to be inserted into the BST.
2. The second line contains a single integer (M) representing the number of search queries.
3. The third line contains (M) space-separated integers representing the query values.

outputFormat

Output to stdout the in-order traversal of the BST on the first line (with elements separated by a single space), followed by (M) lines where each line contains either "True" or "False" corresponding to the result of each search query.## sample

20 10 30 5 15 25 35
3
15 100 5

5 10 15 20 25 30 35
True
False
True