Binary Search Tree Operations

Implement a binary search tree (BST) with the following requirements:

1. The BST must support insertion of integer values. Duplicate values should be inserted into the right subtree.

2. The BST must compute its depth. The depth is defined as the maximum number of nodes from the root to any leaf.

3. The BST must support search operations that return the number of comparisons made. The search starts at the root and, at each node, compares the target value. If the node's value is not equal, the search moves left (if the target is smaller) or right (if the target is greater or equal) and increments the comparison count, until the value is found or a null pointer is reached.

Input will consist of a sequence of operations provided via standard input. Each operation is one of the following:

• insert X: Insert the integer X into the BST.
• depth: Output the current depth of the BST.
• search X: Search for X in the BST and output the number of comparisons made.

For each depth or search operation, output the result on a new line to standard output.

Notes:

• The first line of input contains an integer N specifying the total number of operations.
• There is guaranteed to be at least one depth or search operation.

inputFormat

The input format is as follows:

The first line contains an integer N, the number of operations.

Each of the following N lines contains an operation in one of the three formats:

1. insert X — Insert integer X into the BST.
2. depth — Output the current depth of the BST.
3. search X — Search for integer X in the BST and output the number of comparisons performed.

All input is provided via standard input (stdin).

outputFormat

For each depth or search operation in the input, print the result on a separate line to standard output (stdout).## sample

7
insert 5
insert 3
insert 7
insert 3
depth
search 7
search 3

3
2
2